Кіріспе

Стохастикалық оңтайландыру әдістерінің отбасы

Тарату алгоритмдерін бағалау (EDA), кейде ықтималдық модельдеу генетикалық алгоритмдері (PMBGA) деп аталады, – бұл оптималды іздеуді перспективті кандидаттық шешімдердің нақты ықтималдық модельдерін құру және олардан үлгі алу арқылы басқаратын стохастикалық оңтайландыру әдістері. Оптимизация – бұл ықтималдық модельдің кезеңді жаңартулар сериясы ретінде қарастырылады, ол қабылданған шешімдерге қатысты ақпараттандырылмаған бастапқы кодтаудан басталып, тек жаһандық оптималды шешімдерді ғана тудыратын модельмен аяқталады. EDA эволюциялық алгоритмдер класына жатады. EDA мен көптеген дәстүрлі эволюциялық алгоритмдер арасындағы басты айырмашылық – эволюциялық алгоритмдер жаңа кандидаттық шешімдерді бір немесе бірнеше өзгерту операторларымен анықталған жасырын үлестірімді пайдалана отырып жасайды, ал EDA Байес желісімен кодталған нақты ықтималдық үлестірімін, көпөлшемді қалыпты үлестірімді немесе басқа модель класын қолданады. Басқа эволюциялық алгоритмдер сияқты, EDA-ны векторлардан LISP стиліндегі S-өрнектерге дейінгі әртүрлі форматтарда берілген оңтайландыру мәселелерін шешу үшін пайдалануға болады, ал кандидаттық шешімдердің сапасы көбінесе бір немесе бірнеше мақсаттық функцияларды пайдалану арқылы бағаланады. EDA-ның жалпы процедурасы келесідей:

t := 0
модель M(0) -ді қабылданған шешімдердің біркелкі үлестірімін көрсететіндей бастамалау
while (тоқтату шарттары орындалмағанда) do
P := модель M(t) -дан үлгі алу арқылы N>0 кандидаттық шешімдерді жасау
F := P-дегі барлық кандидаттық шешімдерді бағалау
M(t + 1) := модельді реттеу(P, F, M(t))
t := t + 1

Оптимизацияда нақты ықтималдық модельдерді пайдалану EDA-ға көптеген дәстүрлі эволюциялық алгоритмдер мен дәстүрлі оңтайландыру техникалары үшін қиын болған оңтайландыру мәселелерін, мысалы, жоғары деңгейдегі эпистазға ие мәселелерді шешуге мүмкіндік берді. Дегенмен, EDA-ның артықшылығы сонымен қатар осы алгоритмдер оңтайландырушыға шешіліп жатқан мәселе туралы көптеген ақпаратты ашатын ықтималдық модельдердің сериясын ұсынады. Бұл ақпарат, өз кезегінде, жергілікті іздеу үшін мәселеге қатысты жаңа операторларды жобалауға, ұқсас мәселе бойынша EDA-ның келесі іске қосылуын бағыттауға немесе мәселенің тиімді есептеу моделін жасауға пайдаланылуы мүмкін. Мысалы, егер популяция 4 ұзындығындағы биттік тізбектермен бейнеленсе, EDA перспективті шешімдер популяциясын төрт ықтималдықтың (p1, p2, p3, p4) бір векторы арқылы бейнелей алады, мұнда p-ның әрбір компоненті сол позицияның 1 болу ықтималдығын анықтайды. Бұл ықтималдық векторын пайдаланып, кез келген сандағы кандидаттық шешімдерді жасауға болады.

Тарату алгоритмдерін бағалау (EDA)

Бұл бөлім әртүрлі күрделілік деңгейлеріндегі белгілі EDA-лар құрастырған модельдерді сипаттайды. Әрқашан бір буын популяциясы, таңдау операторы, модель құру операторы және үлгі алу операторы бар деп есептелінеді.

Біркелкі факторлау

Ең қарапайым ЭҚЖ шешімдік айнымалылар тәуелсіз деп есептейді, яғни. Сондықтан, бір айнымалы ЭҚЖ тек бір айнымалы статистикаға ғана сүйенеді, ал көп айнымалы таралымдар бір айнымалы ықтималдық таралымдарының көбейтіндісі түрінде жіктелуі тиіс. Мұндай жіктелулер көптеген түрлі ЭҚЖ-да қолданылады, ал кейбіреулерін төменде сипаттаймыз.

Халықтың өсуі бойынша оқыту (PBIL)

PBIL, өзінің моделі арқылы популяцияны жасырады, сол модельден жаңа шешімдер үлгі алынып, модель жаңартылады. Әр буын сайын жекелеген шешімдер үлгіленеді және іріктеледі. Осы шешімдер модельді келесідей жаңартуға қолданылады:

мұнда – оқыту жылдамдығын анықтайтын параметр, кішкентай мән жаңа үлгі алынған шешімдердің бұрынғы модельге аз өзгеріс енгізуін қамтамасыз етеді. PBIL былай сипатталуы мүмкін:

Компактты генетикалық алгоритм (cGA)

CGA, сонымен қатар, унивариантты үлестірімдермен анықталатын жасырын популяцияларға сүйенеді. Әр ұрпақта екі жеке тұлғадан үлгі алынады, содан кейін популяция жарамдылық деңгейі бойынша төмендеу ретімен сұрыпталады, мұнда ең жақсы, ал ең нашар шешім болып табылады. CGA унивариантты ықтималдықтарды келесідей бағалайды:

мұнда – оқыту жылдамдығын анықтайтын тұрақты шама, әдетте -ге тең. CGA келесідей анықталады:

Еківариантты факторлау

Бірөлшекті модельдерді тиімді есептеуге болысқанмен, көп жағдайда олар генетикалық алгоритмдерге қарағанда жақсы нәтижелерді қамтамасыз ете алмайды. Мұндай кемшілікті жою үшін EDA қауымдастығы екіөлшекті факторландыруды ұсынды, онда екі айнымалы арасындағы байланыстар модельделеді. Екіөлшекті факторландыруды былай анықтауға болады, мұнда - бұл айнымалына тәуелді болатын мүмкін айнымалы, яғни екіөлшекті және көпөлшекті таралымдар әдетте ықтималдық графикалық модельдер (графтар) түрінде көрсетіледі, онда қабырғалар статистикалық байланыстарды (немесе шартты ықтималдықтарды) білдіреді, ал төбелер айнымалыларды көрсетеді. PGM құрылымын деректерді байланыстыру арқылы үйренуге болады.

Кірісті кластерлеуді барынша арттыратын өзара ақпарат (MIMIC)

MIMIC біріккен ықтималдық үлестірімін өзгермелілер арасындағы тізбекті тәуелділікті көрсететін модельде факторлайды. Ол шешімді өзгергіштердің ретін өзгертеді, , осылайша нақты ықтималдық үлестіріміне қатысты Куллбек-Лейблер дивергенциясын ең төменгі деңгейге дейін азайтады, яғни MIMIC үлестірімді модельдейді.

Жаңа шешімдер сол жақтан оң жаққа қарай алынады, біріншісі тәуелсіз түрде, ал қалғандары шартты ықтималдықтар бойынша жасалады. Бағаланған үлестірім әр ұрпақта қайта есептелуі керек болғандықтан, MIMIC нақты популяцияларды келесідей пайдаланады.

Көпбұрышты факторлау

EDA-ны дамытудың келесі кезеңі көпөлшемді факторлауды пайдалану болды. Бұл жағдайда, бірлескен ықтималдық үлестірімі әдетте шектеулі өлшемдегі бірнеше компоненттерге жіктеледі. Көпөлшемді үлестірілімдерді кодтаушы PGM-дерді оқыту есептеу тұрғысынан күрделі міндет болып табылады, сондықтан EDA-лар көпөлшемді статистиканы екіөлшемді статистикадан бағалауға бейім. Мұндай жеңілдету PGM-ді полиномиалдық уақытта құруға мүмкіндік береді; алайда, бұл сондай-ақ мұндай EDA-лардың жалпылығын шектейді.

Бейес оптимизациялау алгоритмі (BOA)

BOA болашақ шешімдерді модельдеу және үлгілеу үшін Байес желілерін қолданады. Байес желілері – бағытталған ациклді графиктер, олардың түйіндері айнымалыларды, ал жиектері айнымалылар жұбы арасындағы шартты ықтималдықтарды көрсетеді. Айнымалының мәні ең көп дегенде басқа айнымалыларға байланысты шартты түрде анықталуы мүмкін. BOA құрамында факторланған бірлескен үлестіруді кодтайтын PGM құрылады, онда желі параметрлері, яғни шартты ықтималдықтар, ең жоғары ықтималдық бағалаушысын қолдана отырып, таңдалған популяциядан бағаланады. Ал Байес желісінің құрылымы итеративті түрде құрылуы керек (байланыс үйрену). Ол жиегі жоқ желіден басталады және әр қадамда белгілі бір бағалау метрикасын жақсартатын жиекті қосады (мысалы, Байес ақпараттық критерийі (BIC) немесе ықтималдық теңдестірілген Байес Дирихлет метрикасы (BDe)). Бағалау метрикасы желі құрылымын таңдалған популяцияны модельдеудегі дәлдігіне қарай бағалайды. Құрылған желіден BOA жаңа перспективалы шешімдерді келесідей үлгілейді: 1) ол әр айнымалы үшін ата-бабалар ретін есептейді, әр түйіннің алдында оның ата-аналары орналасады; 2) әр айнымалы ата-аналарына шартты түрде үлгіленеді. Мұндай жағдайда, әрбір BOA қадамын былай анықтауға болады: