Генетичний метод рішення задачі побудови оптимальної регресійної моделі

В статі розглядається задача побудови оптимальної регресійної моделі складної системи, яка характеризується n вхідними (незалежними) змінними та одною вихідною (залежною) зміною, що мають стохастичний характер.. Задача побудови оптимальної регресійної моделі полягає в виборі з всієї множини вхідн...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2008
1. Verfasser:	Мельник, І.М.
Format:	Artikel
Sprache:	Ukrainian
Veröffentlicht:	Міжнародний науково-навчальний центр інформаційних технологій та систем НАН і МОН України 2008
Online Zugang:	https://nasplib.isofts.kiev.ua/handle/123456789/11464
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Генетичний метод рішення задачі побудови оптимальної регресійної моделі / І.М. Мельник // Екон.-мат. моделювання соц.-екон. систем. — 2008. — Вип. 13. — С. 129-147. — Бібліогр.: 8 назв. — укp.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-11464
record_format	dspace
spelling	nasplib_isofts_kiev_ua-123456789-114642025-02-09T17:05:29Z Генетичний метод рішення задачі побудови оптимальної регресійної моделі Мельник, І.М. В статі розглядається задача побудови оптимальної регресійної моделі складної системи, яка характеризується n вхідними (незалежними) змінними та одною вихідною (залежною) зміною, що мають стохастичний характер.. Задача побудови оптимальної регресійної моделі полягає в виборі з всієї множини вхідних незалежних змінних підмножину, яка оптимізує заданий функціонал оцінки вибору моделі. В статі ця задача формулюється як задача дискретної оптимізація на спеціальному графі. Пропонуються методи розв’язання цієї задачі як задачі пошуку найкоротшого шляху на цьому графі. Особливу увагу приділяється використанню ідей генетичного алгоритму (як евристичного) пошуку глобального оптимуму для цієї складної задачі. 2008 Article Генетичний метод рішення задачі побудови оптимальної регресійної моделі / І.М. Мельник // Екон.-мат. моделювання соц.-екон. систем. — 2008. — Вип. 13. — С. 129-147. — Бібліогр.: 8 назв. — укp. XXXX-0009 https://nasplib.isofts.kiev.ua/handle/123456789/11464 519.8 uk application/pdf Міжнародний науково-навчальний центр інформаційних технологій та систем НАН і МОН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Ukrainian
description	В статі розглядається задача побудови оптимальної регресійної моделі складної системи, яка характеризується n вхідними (незалежними) змінними та одною вихідною (залежною) зміною, що мають стохастичний характер.. Задача побудови оптимальної регресійної моделі полягає в виборі з всієї множини вхідних незалежних змінних підмножину, яка оптимізує заданий функціонал оцінки вибору моделі. В статі ця задача формулюється як задача дискретної оптимізація на спеціальному графі. Пропонуються методи розв’язання цієї задачі як задачі пошуку найкоротшого шляху на цьому графі. Особливу увагу приділяється використанню ідей генетичного алгоритму (як евристичного) пошуку глобального оптимуму для цієї складної задачі.
format	Article
author	Мельник, І.М.
spellingShingle	Мельник, І.М. Генетичний метод рішення задачі побудови оптимальної регресійної моделі
author_facet	Мельник, І.М.
author_sort	Мельник, І.М.
title	Генетичний метод рішення задачі побудови оптимальної регресійної моделі
title_short	Генетичний метод рішення задачі побудови оптимальної регресійної моделі
title_full	Генетичний метод рішення задачі побудови оптимальної регресійної моделі
title_fullStr	Генетичний метод рішення задачі побудови оптимальної регресійної моделі
title_full_unstemmed	Генетичний метод рішення задачі побудови оптимальної регресійної моделі
title_sort	генетичний метод рішення задачі побудови оптимальної регресійної моделі
publisher	Міжнародний науково-навчальний центр інформаційних технологій та систем НАН і МОН України
publishDate	2008
url	https://nasplib.isofts.kiev.ua/handle/123456789/11464
citation_txt	Генетичний метод рішення задачі побудови оптимальної регресійної моделі / І.М. Мельник // Екон.-мат. моделювання соц.-екон. систем. — 2008. — Вип. 13. — С. 129-147. — Бібліогр.: 8 назв. — укp.
work_keys_str_mv	AT melʹnikím genetičnijmetodríšennâzadačípobudovioptimalʹnoíregresíjnoímodelí
first_indexed	2025-11-28T09:22:22Z
last_indexed	2025-11-28T09:22:22Z
_version_	1850025442488090624
fulltext	Економіко-математичне моделювання соціально-економічних систем Збірник наукових праць МННЦ ІТіС Київ – 2008, випуск 13 129 129 УДК 519.8 І. М. Мельник ГЕНЕТИЧНИЙ МЕТОД РІШЕННЯ ЗАДАЧІ ПОБУДОВИ ОПТИМАЛЬНОЇ РЕГРЕСІЙНОЇ МОДЕЛІ В статі розглядається задача побудови оптимальної регресійної моделі складної системи, яка характеризується n вхідними (незалежними) змінними та одною вихідною (залежною) зміною , що мають стохастичний характер.. Задача побудови оптимальної регресійної моделі полягає в виборі з всієї множини вхідних незалежних змінних підмножину, яка оптимізує заданий функціонал оцінки вибору моделі. В статі ця задача формулюється як задача дискретної оптимізація на спеціальному графі. Пропонуються методи розв’язання цієї задачі як задачі пошуку найкоротшого шляху на цьому графі. Особливу увагу приділяється використанню ідей генетичного алгоритму (як евристичного) пошуку глобального оптимуму для цієї складної задачі. Вступ. Задача побудови оптимальної регресійної моделі полягає у виборі з загальної множини незалежних змінних (регресорів) відповідної підмножини змінних для включення цих змінних у кінцеву регресійну модель. Задача є багатоекстремальною задачею дискретної оптимізації перебірного типу. На сьогодні достатньо ефективних алгоритмів розв’язання цієї задачі немає. В статті задача побудови оптимальної регресійної моделі формулюється як задача дискретної оптимізації на спеціальному графі. Пропонується методи розв’язання цієї задачі як спеціальної задачі пошуку найкоротшого шляху на графі. Особливу увагу приділяється використанню ідеї генетичного алгоритму (як евристичного) для пошуку глобального оптимуму для цієї складної задачі [1,2]. Постановка задачі. Розглядається складна система, яка характеризується n вхідними (незалежними) змінними ni xxx ...,,...,,1 та одною вихідною (залежною) зміною y , що мають стохастичний характер і задані вибіркою з m статистичних спостережень цих змінних. В процесі ідентифікації генеруються структури лінійних регресійних моделей, параметри яких оцінюються за методом найменших квадратів (МНК). Заданий деякий функціонал оцінки моделі F(.), тобто функціонал вибору оптимальної моделі. Цей функціонал може залежить від складності моделі (числа оцінюваних Економіко-математичне моделювання соціально-економічних систем Збірник наукових праць МННЦ ІТіС Київ – 2008, випуск 13 130 130 параметрів, які включаються в модель) та/або нев’язок рівняння регресії на деякої підмножині статистичних вибірок та інших параметрів моделі. Отже, задача побудови оптимальної регресійної моделі: необхідно з усієї множини вхідних змінних ni xxx ...,,...,,1 вибрати таку підмножину змінних, щоб регресійна модель, яка побудована на основі цієї підмножини, давала би оптимум (мінімум або максимум) заданого функціоналу оцінки моделі F(.). Відповідну регресійну модель, в яку включені тільки змінні (регресори) з вибраної таким чином підмножини змінних, будемо називати оптимальною моделлю. Вирішення задачі. Пропонується задачу вибору оптимальної регресійної моделі формулювати і розв’язувати як задачу дискретної оптимізації на спеціальному графі ),( UI . Множина вершин I цього графа формується так. Кожній незалежній змінній )...,,1( nixi = ставиться у відповідність вершина графа i . Додаються додатково ще дві вершини: 0 та 1+n . Множина дуг U будується таким чином. Вершина 0 з’єднується з кожною вершиною і )...,,1( ni = дугою ),0( i . Далі, кожна вершина і з’єднується з кожною вершиною ijj >, , дугою ),( ji . Трактується, що вершина ),,1( nii L= відповідає ситуації, коли незалежна змінна ix включається в регресійну модель. Тоді кожному шляху з вершини 0 у вершину 1+n відповідає певний варіант побудови регресійної моделі, а саме такої, в яку у вигляді регресорів включаються незалежні змінні ix , що відповідають вершинам графа ),( UI , через які проходить цей шлях. Кожному шляху µ з вершини 0 у вершину 1+n ставиться у відповідність його “довжина”, яка дорівнює значенню функціоналу вибору оптимальної моделі F(.). Отже, початкова задача побудови регресійної моделі (задача вибору набору регресорів) зводиться до знаходження найкоротшого шляху з вершини 0 у вершину 1+n на графі ),( UI . Економіко-математичне моделювання соціально-економічних систем Збірник наукових праць МННЦ ІТіС Київ – 2008, випуск 13 131 131 Граф ),( UI дозволяє послідовно, економним способом, організувати перебір варіантів розв’язання задачі вибору оптимальної регресійної моделі та їх співставлення між собою. Знаходження найкоротшого шляху на побудованому графі ),( UI і дає розв’язок основної задачі вибору оптимальної регресійної моделі. Пропонуються два методу точного розв’язання задачі побудови оптимальної регресійної моделі як задачі знаходження найкоротшого шляху на відповідному графі. Знаходження найкоротшого шляху на графі здійснюється процедурою послідовного відмічування вершин цього графа спеціальними позначками з можливим відсівом неперспективних варіантів на етапі конструювання варіантів рішення. У першому методу функціонал оцінки вибору регресійної моделі включає як оцінки складності моделі, так і квадрати нев’язок. рівняння регресійної моделі на всієї множині статистичних вибірок. У другому методі, з розбиттям всієї множини статистичної вибірки на дві підмножини (що є типовим для МГУА [3]), розв’язується мінімаксна задача дискретної оптимізації для квадратів нев’язок рівняння регресійної моделі на одної з підмножини статистичних вибірок . Перший варіант методу це метод розв’язання задачі побудови оптимальної регресійної моделі для функціоналу оцінки моделі, який залежить від складності моделі (числа оцінюваних параметрів, які включаються в модель, помножених на ваги, та квадратів нев’язок рівняння регресії на множині статистичних вибірок), тобто необхідно вибрати таку підмножину J з множини { }n...,,1 , що ∑ ∑∑ = ∈∈ ⇒−+ m k Ji k ii k Ji i xJayC 1 2 min))(( , (1) де через JiJai ∈),( , будемо позначати коефіцієнти регресійної моделі, які знайдені за МНК для набору регресорів J , { }1/ XxiJ i ∈= - підмножина множини номерів вхідних змінних { }n...,,1 та 1X відповідна підмножина вхідних змінних, а iC - “витрати” на отримання статистичної інформації про значення незалежної змінної ix )( Ji ∈ . Економіко-математичне моделювання соціально-економічних систем Збірник наукових праць МННЦ ІТіС Київ – 2008, випуск 13 132 132 Нехай маємо дві підмножині 1J і 2J з множини { }n...,,1 номерів незалежних змінних nixi ,...,1, = , тобто }.,...,1{},,...,1{ 21 nJnJ ⊆⊆ . Лема 1. Якщо маємо 21 JJ ⊆ , то для цих підмножин виконується таке співвідношення: 2 2 1 2 1 1 ))(())(( 21 k i Ji i m k kk i m k Ji i k xJayxJay ∑∑∑ ∑ ∈== ∈ −≥− (2) Будемо позначати варіант вибору регресійної моделі (варіант вибору сукупності незалежних змінних ix для моделі (1)), як вибір значення булевих змінних ,...,,1, nii =δ у векторі )...,,( 1 nδδδ = , де 1=iδ , якщо незалежна зміна ix включається в регресійну модель (тобто включається як регресор в модель (5)), та 0=iδ у протилежному випадку. Отже, задача (1) вибору варіанта регресійної моделі формулюється як задача дискретної оптимізації, або задачі цілочисельного булевого програмування: необхідно знайти мінімум функціоналу 2 11 ))(( i k i Ji i m k k i n i i xJayc δδ ∑∑∑ ∈== −+ (3) за умов { }1,0∈iδ , (4) де { }1\| == iiJ δ , а коефіцієнти ( )Jai , Ji ∈ , знаходяться за методом найменших квадратів. Ця задача і розв’язується як задача знаходження відповідного “найкоротшого” шляху з вершини 0 у вершину 1+n . Для варіанту функціоналу оцінки моделі (3) кожному шляху µ з вершини 0 у вершину 1+n будемо ставити у відповідність його “довжину”, яка дорівнює Економіко-математичне моделювання соціально-економічних систем Збірник наукових праць МННЦ ІТіС Київ – 2008, випуск 13 133 133 { } 2 1 111 ))...,,(( lll l l p i n k k p l i xiiayC ρ∑∑∑ =+= −+ (5) Якщо визначити, що “найкоротший” шлях з вершини 0 у вершину 1+n є таким, якому відповідає мінімальне значення функціоналу (5), то початкова задача побудови регресійної моделі (задача вибору регресорів) зводиться до находження “найкоротшого” шляху з вершини 0 у вершину 1+n на графі ),( UI . Як сказано вище, задачу знаходження найкоротшого шляху з вершини 0 у вершину 1+n на графі будемо здійснювати процедурою послідовного відмічання вершин цього графа спеціальними позначками - відмітками (тобто процедурою побудови цих відміток вершин) [4]. Для випадку функціоналу оцінки (1) (або (5)) кожна відмітка iP вершини Iii ∈, , якій відповідає шлях [ ]iiii === l ...,,,0 10µ з вершини 0 у вершину i, складається з чотирьох ознак, тобто =iP ),,,( 4321 iiii PPPP , де 1 iP - порядковий номер цієї відмітки в вершини i ; 2 iP - вершини з множини { }n...,,1 , через які проходить шлях [ ] l iiii ...,,, 10=µ , тобто { } l iiPi ...,,1 2 = , якщо 1+≠ ni l , та { }1 2 ...,,1 −= l iPi , якщо 1+= ni l ; ∑ = = l 1 3 r ii r CP - тобто ознака 3 iP дорівнює сумі C i для всіх вершин, через які проходить шлях µ ; { } 2 1 1 1 4 ))...,,(( k i m k r i k i rr xiiayP ∑ ∑ = = −= l l - тобто 4 iP дорівнює значенню квадратів суми нев’язок рівняння регресії в Економіко-математичне моделювання соціально-економічних систем Збірник наукових праць МННЦ ІТіС Київ – 2008, випуск 13 134 134 функціоналі (4) на множині вершин шляху iµ (на множині вершин { } l ii ...,1 ). Множину варіантів шляхів з вершини 0 у вершину 1+n на графі ),( UI (тобто множину варіантів рішення задачі вибору оптимальної моделі за функціоналом оцінки (1)) здійснюється спеціальною технологією (процедурою) послідовного відмічання вершин цього графа спеціальними позначками - відмітками (тобто процедурою побудови цих відміток вершин) [7] з відсівом, на етапі конструювання шляхів, завідомо неперспективних варіантів за допомогою твердження Леми 1(формули (2)). Процедура побудови множини відміток вершин графа ),( UI здійснюється у декілька етапів. Перший (початковий) етап полягає у призначенні початкових значень позначок для відміток вершин графа. Основний, другий етап, як раз і полягає в побудові всієї множини відміток вершин графа. Кожна відмітка вершини i графа – це відповідний шлях через вершини цього графа з вершин 0 в вершину i , та початковий відрізок шляху (шляхів) з вершин 0 в вершину 1+n . По кожні відмітки вершину i здійснюється продовження відрізку шляху з вершин 0 в вершину i в сусідні, з вершиною i , вершини. Це здійснюється процедурою присвоєння нових відміток цим сусіднім вершинам. Причому на цьому етапі суттєво використовується твердження Леми 1 для конструювання тільки „перспективних” продовжень шляху з вершини i в сусідні з нею вершини. Процедура породження нових відміток продовжується доти, доки з’являються нові відмітки, тобто до тої пори поки будуватися варіанти перспективних шляхів в вершину 1+n . Вершина 1+n помічається відмітками відповідно до вибраного правилу формування кінцевого набору варіантів рішення задачі побудови оптимальної регресійної моделі. В останньому, заключному етапі, по відмітки (відміткам) вершини 1+n визначаються номера вершин графа, через які проходе саме «найкоротший» шлях з вершин 0 в вершину 1+n . Ці Економіко-математичне моделювання соціально-економічних систем Збірник наукових праць МННЦ ІТіС Київ – 2008, випуск 13 135 135 номера вершин і дають множину номерів змінних, які необхідно включити в оптимальну регресійну модель як регресорів. Другий варіант методу розв’язання задачі побудови оптимальної регресійної моделі це метод рішення цієї задачі для минимаксного функціоналу оцінки моделі. Розглядається наступний критерій вибору регресійної моделі. Множина точок вибірки { }mS ...,,1= розбита на дві частини: 1S та 2S , що є типовим для МГУА [3]. На першій частині вибірки (підмножини) 1S будується регресійна модель, а на другі частині (підмножини) 2S як раз обчислюється значення функціоналу оцінки побудованої моделі ∑ ∈∈ −= Ji k ii k Sk xJayJF 2))((max)( 2 , (6) де { }1/ XxiJ i ∈= – підмножина з множини номерів незалежних змінних { }nI ...,,1= , а 1X - підмножина вхідних змінних, на яких будується регресійна модель. Значення функціоналу (6) обчислюється як максимальне значення квадрату нев”язок між статистичним значенням вихідної змінної y та значенням регресійної моделі по всім k - им, 1Sk ∈ , спостереженням значень вхідних змінних з 1X . Необхідно вибрати таку регресійну модель (тобто таку підмножину номерів незалежних змінних J з множини { }nI ...,,1= , для якої значення функціоналу (6) буде приймати мінімальне значення, тобто необхідно розв’язати задачу: IJ MIN ⊆ ∑ ∈ ∈ − Ji k ii k Sk xJay 2))((max 2 , (7) по всім підмножинам J з множини { }n...,,1 . Алгоритм розв’язання задачі (7) вибору оптимальної регресійної моделі як задачі дискретної оптимізації на графі ),( UI знаходження відповідного найкоротшого шляху, визначеного значеннями функціоналу (6), аналогічний алгоритму для Економіко-математичне моделювання соціально-економічних систем Збірник наукових праць МННЦ ІТіС Київ – 2008, випуск 13 136 136 першого варіанту, з деякими обчислювальними модифікаціями. Наприклад, буде відсутня ознака 3 iP , а ознака 4 iP буде обчислюватись відповідно до формули (6). Оскільки аналог Леми 1 для цього варіанта функціоналу вибору моделі можна брати як гіпотезу, то алгоритм забезпечує ефективне знаходження відповідного наближення до оптимального розв’язку початкової задачі. Зробимо таку ремарку. Що до функціоналу оцінки моделі (6) - він має детерменірованний (не стохастичний) характер, хоча сам економічний процес має стохастичний характер. Цікавим може бути представлення функціоналу оцінки моделі у стохастичному вигляді, Наприклад, з використанням вірогідних обмежень: min b при умові ∑ ⊆ ≥≤− IJ ii pbxJayP )))({( 2 , де b - і є оцінка значення квадратів нев’язок рівняння регресії на підмножині статистичних вибірок, на якої обчислюється значення функціоналу оцінки моделі, а p - відповідний поріг вірогідності для цієї оцінки. Розгляд та дослідження цього підходу буде окремою публікацію, але зауважимо, що алгоритмічний підхід для розв’язання цієї задачі є [ 3 ]. Але методи точного розв’язання задачі побудови оптимальної регресійної моделі ефективні для не надто значних розмірностей, тобто коли кількість всіх визначально заданих змінних (регресорів) не є великою. Для довільного, в тому числі для достатньо великого, числа первинних змінних (регресорів) пропонується спеціальний генетичний алгоритм розв’язання задачі вибору оптимальної регресійної моделі, який не гарантує точного розв’язання, але дає достатньо задовільне рішення. Ідеї класичного генетичного алгоритму, були запропоновані в Мічиганському університеті Дж. Холландом [6]. Цей алгоритм часто дозволяє найти задовільне розв’язання аналітично не вирішуваних (або важко вирішуваних) проблем засобом підбору та конструювання відповідних процедур обчислювального процесу цього алгоритму з використанням механізмів, які аналогічні генетичним процесам еволюції у світі живих організмів. Головна особливість генетичного алгоритму є в тому, що на кожному його кроці (ітерації) аналізується Економіко-математичне моделювання соціально-економічних систем Збірник наукових праць МННЦ ІТіС Київ – 2008, випуск 13 137 137 не одно рішення (хромосома), а деяка їх підмножина. Кожне рішення (хромосома) представляється у вигляді булевого вектора, компоненти якого приймають значення 0 або 1 і називаються генами. Ця підмножина (часто достатньо “добрих”) хромосом (хромосом) називається “популяцією”. На кожному циклі генетичного алгоритму на базі поточної популяції здійснюється за допомогою основних процедур алгоритму – кроссоверу (схрещування), мутації та селекції – процес генерування додатково нових хромосом, які називаються “нащадками”. При цьому ітераційний процес будується так, що кожна послідуюча популяція повинна бути “кращою” в порівнянні з попередньою. Отже, відповідно до термінології та визначень теорії генетичних алгоритмів [6,7], кожний шлях з вершини 0 в вершину 1+n на графі ),( UI (тобто відповідний варіант вибору регресійної моделі), якому відповідає булевий вектор розмірності n , є хромосома відповідної популяції (підмножини рішень), а кожний елемент цього булевого вектора – ген цієї хромосоми. Визначимо для кожної хромосоми µ , на основі значень цільових функції F(.) всіх хромосом популяції, функцію пристосовності (фітнесс – функція) P(µ ) таким способом: P(µ ) = F(µ ) / ((СУМА F(.) – F(µ ))), (6) де СУМА F(.) – оператор сумування по всіма хромосомам популяції. Лема 2. Якщо деяка хромосома дає локальний (глобальний) оптимум для основної задачі вибору оптимальної регресійної моделі (для цільової функції F(.)), то ця хромосома є локальним (глобальним) оптимумом для функції пристосовності P(.), і навпаки. Лема 3. Якщо µ 1 та µ 2 - хромосоми відповідної популяції та F(µ 1) < F(µ 2), то F( µ 1) / F( µ 2) < P ( µ 1) / P ( µ 2) . Визначимо, що тип популяції k -ого типу ( k -ий тип популяції) - ця множина хромосом (шляхів з вершини 0 в вершину 1+n ) які обов’язково містять вершину з номером k ( 0>k ) (тобто змінну kx ) , а також можливо ще вершини, номери яких більше k . Отже, загальна множина популяцій розбивається на n підмножин ( n типів популяцій), які не пересікаються і які в сумі дають множину загальної популяції. Це означає, що в графі ),( UI Економіко-математичне моделювання соціально-економічних систем Збірник наукових праць МННЦ ІТіС Київ – 2008, випуск 13 138 138 виділяються n частинних графів ),( kk UI ,,...,1 nk = де kI - підмножина вершин з множини вершин I основного графа ),( UI , kI = },,0{ kik > . А kU - підмножина дуг з множини дуг U основного графа ),( UI , kU = },,,),,(;,),,();,0{( jikiIjijikjIjjkk kk <>∈>∈ . Кожний шлях в графі ),( kk UI ),...,1( nk = з вершини 0 в вершину 1+n (він обов’язково проходе через вершину з номером k ) ) є деяка популяція (хромосома) з популяції k -ого типу та є відповідним рішенням (яке обов’язково включає змінну kx ) для основної задачі по вибору оптимальної регресійної моделі. Запропонований генетичний метод є ітераційним алгоритмічним процесом. На кожні поточні ітерації t ,..)1,0( =t поточна підмножина популяцій k – ого )(tWk піддається дій основних процедур генетичного алгоритму: кроссоверу – тобто виробленню нових популяцій k – ого типу шляхом схрещуванню, а також мутації та селекції, і додатково процедурі обміну (міграції) між підмножинами популяцій різних типів. В результаті одержується нова поточна підмножина популяцій k – ого типу )1( +tWk , яка, як правило, є “кращою” („ поліпшеною”) в порівнянні з попередньою )(tWk і яка, в свою чергу, в подальшому, піддається діям обчислювальних процедур запропонованого генетичного алгоритму на 1+t ітерації. Цей ітераційний процес продовжується до тих пір, поки поточна підмножина популяцій k – ого типу поліпшується. У цієї моделі генетичного алгоритму важливе місце займає процедура побудування початкової підмножини популяцій k – ого )0(kW ( nk ,...,1= ). Вибір початкової підмножини k – ого типу популяції здійснюється спеціальним варіантом метода міток на графі ),( kk UI . У кожної вершини i може бути одна або декілька міток. Кожна мітка вершини i має чотири ознаки (числа): Економіко-математичне моделювання соціально-економічних систем Збірник наукових праць МННЦ ІТіС Київ – 2008, випуск 13 139 139 ),,,( 21 iiii LPPN , де iN - номер попередній вершини , 1 iP - номер метки у попередній вершини, 2 iP - поточний номер цієї метки вершини i , iL - значення функціоналу оцінки відповідної регресійної моделі. Для кожної дуги kUji ∈),( графа ),( kk UI вводиться вірогідний датчик с значеннями 0 або 1 }1,0{=ijξ з дискретним розподілом вірогідностей )1,( ijijij ppP −= , де 10 ≤≤ ijp . ПРОЦЕДУРА визначення початкової підмножини популяцій k – ого типу )0(kW . Початковий (нульовий) етап. Вводимо лічильник lP поміток вершини l ( ,1,,...,1 ++= nnkl ), який буде визначати на кожні ітерації кількість вже зроблених поміток для цієї вершин. На початку покладаємо значення цих лічильників рівним 0. Вводимо для дуги kUji ∈),( ( nkki ,...,1, += ) вірогідний датчик }1,0{=ijξ з дискретним розподілом вірогідностей )1,( ijij pp − , де вірогідність 10 << ijp задається. Перший етап (помічування вершин 0 та k ). На цьому етапі помічуємо вершини 0 та k , які будуть мате тільки по одній помітки. Помічаємо вершину 0 поміткою 1 0R = )0,1,0,0( 00 2 0 1 0 ==== LPPN . По помітки 1 0R вершини 0 помічаємо вершину k поміткою 1 kR = ),1,1,0( 21 kkkk LPPN === , де kL = 2)(max 2 s kk s Ss xay −∈ , а ka визначено методом МНК, коли набір регресорів складається з одної змінної kx на статистичної вибірки 1S значень змінної kx . Економіко-математичне моделювання соціально-економічних систем Збірник наукових праць МННЦ ІТіС Київ – 2008, випуск 13 140 140 Основний етап помічування вершин графа ),( kk UI (помічування вершин 1+k , 2+k , …, n , а також 1+n ). Помічування вершин 1+k , 2+k , …, n , а також 1+n , виділено в окремий (основний) етап, тому що у них (крім вершини 1+k ) може бути більш чим одна помітка. Оскільки помічування цих вершин проводиться з урахуванням результатів „розиграшу” вірогідних датчиків }1,0{=ijξ , ,),( kUji ∈ то ці вершини можуть і не мати ні одної помітки. Відпрацювання вершини k з її поміткою 1 kR = ),1,1,0( 21 kkkk LPPN === . Здійснюємо по помітки 1 kR вершини k процедуру помічування для вершини 1+k . Для цього „розігруємо” для дуги ),( 1+kk ii вірогідний датчик }1,0{1, =+kkξ . Якщо при цьому „випало” значення датчика 1, +kkξ =1, то помічаємо вершину 1+k поміткою 1 1+kR = ),1,,( 11 2 1 21 11 +++++ +=== kkkkkk LPPPPkN , де ∑ + = ∈+ −= 1 2 1 )(max 2 k kl s ll s Ssk xayL . Коефіцієнти ka та 1+ka визначаються МНК для набору регресорів з kx та 1+kx на статистичної вибірки 1S значень цих змінних (регресорів). Збільшуємо значення лічильника 1+kP поміток вершини 1+k на 1. Покладаємо для лічильника 1, +kkξ новий розподіл вірогідностей )0,1( 1, =+kkp і переходимо до розгляду процедури помічування для вершини 2+k . А якщо, при розиграшу вірогідного датчика }1,0{1, =+kkξ „випало” значення 1, +kkξ рівне 0, то переходимо зразу до розгляду процедури помічування для вершини 2+k . Здійснюємо по помітки 1 kR вершини k процедури помічування для вершини 2+k . „Розігруємо” для дуги ),( 2+kk ii вірогідний датчик }1,0{2, =+kkξ з дискретним розподілом вірогідностей )1,( 2,2, ++ − kkkk pp . Якщо при цьому „випало” Економіко-математичне моделювання соціально-економічних систем Збірник наукових праць МННЦ ІТіС Київ – 2008, випуск 13 141 141 значення датчика 2, +kkξ рівне 1, то помічаємо вершину 2+k поміткою 1 2+kR = ),1,,( 22 2 2 21 22 +++++ +=== kkkkkk LPPPPkN , де 2 222 ))((max 2 s kk s kk s Ssk xaxayL ++∈+ +−= . Коефіцієнти ka та 2+ka визначаються МНК для набору регресорів з kx та 2+kx на вибірки 1S . Збільшуємо значення лічильника 2+kP поміток вершини 2+k на 1. Покладаємо для датчика 2, +kkξ новий розподіл вірогідностей )0,1( 2, =+kkp і переходимо до розгляду процедури помічування для вершини 3+k . А якщо, при розиграшу вірогідного датчика }1,0{2, =+kkξ „випало” значення 2, +kkξ рівне 0, то переходимо зразу до розгляду процедури помічування для вершини 3+k . Здійснюємо процедури помічування для вершини 3+k и т. д., поки не дійдемо до вершини n . „Розігруємо” для дуги ),( nik датчик }1,0{, =nkξ з дискретним розподілом вірогідностей )1,( ,, nknk pp − . Якщо при цьому „випало” значення датчика nk,ξ рівне 1, то по помітки 1 kR вершини k помічаємо вершину n поміткою 1 nR = ),1,,( 221 nnnknn LPPPPkN +=== , де 2))((max 2 s nn s kk s Ssn xaxayL +−= ∈ . Коефіцієнти ka та na визначаються МНК для набору регресорів з kx та nx на статистичної вибірки 1S значень kx та nx . Збільшуємо значення лічильника nP поміток вершини n на 1. Покладаємо для датчика nk,ξ новий розподіл вірогідностей )0;1( , =nkp . і переходимо до розгляду процедури помічування для вершини 1+n .А якщо, при “розиграшу” вірогідного датчика }1,0{, =nkξ „випало” значення nk,ξ рівне 0, то переходимо зразу, без помічування вершини n , до помічування вершини 1+n . Економіко-математичне моделювання соціально-економічних систем Збірник наукових праць МННЦ ІТіС Київ – 2008, випуск 13 142 142 По помітки 1 kR = ),1,1,0( 21 kkkk LPPN === вершини k помічуємо вершину 1+n поміткою 1 1+nR = ),1,,( 11 2 1 21 11 knnnknn LLPPPPkN =+=== +++++ . Збільшуємо значення лічильника 1+nP поміток вершини 1+n на 1. Отже, на цьому кроці основного етапу повністю провели використання помітки вершини k для процедурі помічування вершин 1+k , 2+k ,...,n , а також 1+n . Далі працюємо з вершиною 1+k з її поміткою (якщо вона є) 1 1+kR = ),,,( 1 2 1 1 11 ++++ kkkk LPPN (у цієї вершини може бути тільки одна помітка) для використання процедури помічування по неї для вершин 2+k , 3+k , ...,n , а також 1+n . „Розігруємо” для дуги ),( 21 ++ kk ii вірогідний датчик }1,0{2,1 =++ kkξ з дискретним розподілом вірогідностей )1,( 2,12,1 ++++ − kkkk pp . Якщо при цьому „випало” значення датчика 2,1 ++ kkξ рівне 1, то помічаємо вершину 2+k поміткою q kR 2+ = ),1,,1( 22 2 2 2 1 1 22 ++++++ +==+= kkkkkk LPPPPkN , де ∑ + += ∈+ −= 2 1 2 2 )(max 2 k kl s ll s Ssk xayL , а 12 += +kPq . Коефіцієнти 1+ka та 2+ka визначаються МНК для набору регресорів з 1+kx та 2+kx на статистичної вибірки 1S значень 1+kx та 2+kx . Збільшуємо значення лічильника 2+kP поміток вершини 2+k на 1. Покладаємо для датчика 2,1 ++ kkξ новий розподіл вірогідностей )0,1( 2,1 =++ kkp і переходимо до розгляду процедури помічування вершини 3+k . А якщо, при розиграшу вірогідного датчика }1,0{2,1 =++ kkξ „випало” значення цього датчика рівне 0, то переходимо зразу до розгляду вершини 3+k . Розглядаємо використовування помітки 1 1+kR вершини 1+k для процедуру помічування вершину 3+k и т. д., Економіко-математичне моделювання соціально-економічних систем Збірник наукових праць МННЦ ІТіС Київ – 2008, випуск 13 143 143 поки не дійдемо до вершини n . Розігруємо” для дуги ),( 1 nik+ її датчик }1,0{,1 =+ nkξ з дискретним розподілом вірогідностей )1,( ,1,1 nknk pp ++ − . Якщо при цьому „випало” значення датчика nk ,1+ξ рівне 1, то по помітки ),,,( 1 2 1 1 11 ++++ kkkk LPPN вершини 1+k помічаємо вершину n поміткою q nR = ),1,,1( 22 1 1 nnnknn LPPPPkN +==+= + , де 1+= nPq , а 2 11 ))((max 2 s nn s kk s Ssn xaxayL +−= ++∈ . Коефіцієнти 1+ka та na визначаються МНК для набору регресорів з 1+kx та nx на статистичної вибірки 1S . Збільшуємо значення лічильника nP поміток вершини n на 1. Покладаємо для датчиика nk ,1+ξ новий розподіл вірогідностей )0;1( ,1,1 == ++ nknk pP і переходимо до помічування вершини 1+n по помітки 1 1+kR вершини 1+k . А якщо, при “розиграшу” вірогідного датчика }1,0{,1 =+ nkξ „випало” значення рівне 0, то переходимо зразу, без помічування вершини n , до помічування вершини 1+n . Помічаємо по мітки ),,,( 1 2 1 1 11 ++++ kkkk LPPN вершини 1+k вершину 1+n поміткою ),1,,1( 11 2 1 2 1 1 11 ++++++ =+==+= knnnknn LLPPPPkN . Збільшимо значення спеціального лічильника 1+nP поміток вершини 1+n на 1. Далі працюємо з помітками вершини 2+k (якщо воне є) для використання процедури помічування по цим поміткам для вершин 3+k , 4+k , ...,n , а також 1+n . У цієї вершини можуть бути не більш двох поміток (одна по помітки ),,,( 21 kkkk LPPN вершини k , а друга по помітки ),,,( 1 2 1 1 11 ++++ kkkk LPPN вершини 1+k (якщо вершина 1+k була помічена). Беремо першу помітку вершини 2+k 1 2+kR = ),,,( 2 2 2 1 22 ++++ kkkk LPPN . По нї проводимо усі процедури помічування від вершини 3+k до вершини 1+n . Потім Економіко-математичне моделювання соціально-економічних систем Збірник наукових праць МННЦ ІТіС Київ – 2008, випуск 13 144 144 аналогічно працюємо з другою поміткою вершини 2+k (якщо воне є). Далі працюємо з помітками вершини 3+k (їх може бути не більш трёх) і так до тех пір, поки не дійдемо до розгляду вершини 1−n . По поміткам вершини 1−n (їх може бути не більш чім 1−− kn ), почергово у відповідності з „розіграшем” вірогідного датчика }1,0{,1 =− nnξ помічаємо (або не помічаємо) вершину n та обов’язково помічаємо вершину 1+n . Далі переходимо до розгляду поміток вершини n (їх може бути не більш чім kn− ). По її поміткам (якщо вони є) помічаємо почергово відповідними помітками вершину 1+n . Етап формування початкової підмножини популяцій k – ого типу )0(kW . Провіряємо по поміткам вершини 1+n : чи початкова підмножина популяцій k - ого типу містить відповідну кількість осіб? Якщо ні, то переходимо на начало ПРОЦЕДУРИ визначення початкової підмножини популяцій k – ого типу для отримання нових поміток вершини 1+n (а значить і нових популяцій k – ого типу). А якщо, вершина 1+n має відповідну кількість поміток, то, по суті, початкову підмножину популяцій k - ого типу побудовано. Кожні помітки вершини 1+n відповідає шлях в графі ),( kk UI з вершини 0 в вершину 1+n , який відповідає одному з рішень основної задачі вибору регресійної моделі. Кроки процесу обчислень одного циклу генетичного алгоритму для розв’язання задачі вибору оптимальної регресійної моделі. Великий цикл. Крок І. Вибір почергово номера типу популяції k (k = 1, … ,m). Крок ІІ. Малий цикл. Крок 1. Генерація направленим випадковим способом підмножини популяцій (рішень) для вибраного k – ого типу популяцій. Робиться це ПРОЦЕДУРОЮ визначення початкової підмножини популяцій k – ого типу )0(kW . Економіко-математичне моделювання соціально-економічних систем Збірник наукових праць МННЦ ІТіС Київ – 2008, випуск 13 145 145 Будемо вважати, що цей тип популяції повинен містити kN осіб, де kN визначається відповідним засобом. Крок 2. Обчислення значень цільової функції F(.) і функції пристосовності P(.) для всіх хромосом генерованої популяції. Крок 3. Вибір “батьків” з популяції хромосом типу k на основі поєднання двух принципів: інбридингу та аутбридингу, тобто на основі близької й далекої ”спорідненості” батьків. Крок 4. Кроссовер (схрещування) пар хромосом -“батьків” для генерації хромосом -“нащадків”. Крок 5. Обчислення значень цільової функції F(.) та функції пристосовності P (.) для хромосом - “нащадків”. Крок 6. Проведення процедури мутації для хромосом - “нащадків” для генерації хромосом - “мутантів”. Крок 7. Обчислення значень цільової функції F(.) і функції пристосовності P (.) для хромосом “мутантів”. Крок 8. Перевірка закінчення процесу обчислень для популяцій типу k. Якщо ні, то перехід до Кроку 3 малого циклу. А якщо так, то перехід до наступного кроку. Крок 9 . Проведення процедури міграції між підмножиною популяцією k - ого типу та підмножинами популяцій інших типів. Крок 10. Проведення процедури селекції для генерації наступної підмножини популяції k - ого типу. Крок 11. Перехід до Кроку І великого циклу для вибору наступного номера типу популяції (з перевіркою умови mk ≤ ). Якщо виконується умова mk = , то здійснюється перехід на проведення обчислювань великого циклу для наступної (t+1) - ой ітерації. Запропонована в статті модель генетичного алгоритму відноситься до, так званих, острівних моделей (island model) [8] – моделей паралельного генетичного алгоритму, в яких основна популяція розбивається на декілька різних типів (видів) популяцій. Кожна з типів популяції буде розвиватися окремо за допомогою деякого генетичного алгоритму (можливо що до різних типів популяцій можуть використовуватися різні варіанті цього алгоритму). Отже, можна образно сказати, що особі загальної популяції розселені, якщо загальна популяція відповідно до деякого правилу сегментовано на деяке число типів (видів) часткових популяцій, по декілька ізольованими островам. Зрідка може проходити міграція між островами – типи популяцій (острова) міняються деякими „добрими” Економіко-математичне моделювання соціально-економічних систем Збірник наукових праць МННЦ ІТіС Київ – 2008, випуск 13 146 146 особами. Оскільки у обчислювальному аспекти генетичний алгоритм має стохастичний характер, то при різних його запусках популяція може „сходитися” до різних добрих рішень. Острівна модель дозволяє паралельно запустити генетичний алгоритм зразу декілька раз и сумістити (співставити) „досягнення” на різних островах для отримання найліпшого загального рішення. Висновки. Представлення задачі побудови оптимальної регресійної моделі як задачі дискретної оптимізації пошуку найкоротшого шляху на спеціальному графі дозволяє плідно використовувати інструментарій технології рішення цієї задачі для вирішення початкової задачі. Розглядаються два критерії оцінки побудови оптимальної регресійної моделі, з яких мінімаксний критерій оцінки є найоригінальнішим і представляє значний практичний інтерес. Пропонуються методи розв’язання задачі побудови оптимальної регресійної моделі як спеціальної задачі пошуку найкоротшого шляху. Особливий інтерес з них представляє запропонований генетичний алгоритм для вирішення цієї спеціальної задачі пошуку найкоротшого шляху як метод вирішення початкової задачі. Література � І.М. Мельник, В.С. Степашко. Про один підхід по вибору оптимальної регресійної моделі методом дискретної оптимізації // Міжнародний семінар з індуктивного моделювання. Збірник праць. // Відповідальний редактор В.С.Степашко - Київ: МННЦ ІТС НАН та МОН України, 2005. – С. 223-229. � І.Мельник, Генетичний метод структурно-параметричної ідентифікації регресивної моделі складної системи //Матеріали XIV міжнародної з автоматичного управління (Автоматика – 2007), м. Севастополь,10-14 вересня 2007 року. – Ч.1 – Севастополь: СНУЯЄтаП, 2007, с. 80-82. � А. Г. Ивахненко, В.С. Степашко, Помехоустойчивость моделирования. - К.: Наукова думка, 1985. – 216 с. � Ю. М. Ермольев, И. М. Мельник, Экстремальные задачи на графах. – К.: Наукова думка, 1967. – 189. � Ю. М. Ермольев, И. М. Мельник, О методах стохастического программирования с конечним числом испытаний //журнал «Кибернетика», 1974, № 4, с. 82 – 84. � Holland J.H. Adaptation in Natural and Artificial Systems. Ann Arbor: The University of Michigan Press, 1975. Економіко-математичне моделювання соціально-економічних систем Збірник наукових праць МННЦ ІТіС Київ – 2008, випуск 13 147 147 � Goldberg D.S. Genetic algorithms in search, optimization, and machine learning. – Reading, MA: Addsson-Wesley.1989. � W.D. Whitley, S.B. Rana, and R.B. Heckendorn, “Island model genetic algorithms and linearly separable problems”, in Selected Papers from AISB Workshop on Evolutionary Computing. London, UK: Springer- Verlag, 1997, pp. 109-125.

Генетичний метод рішення задачі побудови оптимальної регресійної моделі

Institution

Ähnliche Einträge