Генетски алгоритам

У области вештачке интелигенције генетски алгоритам (ГА) је претраживачка хеуристика која опонаша процес природне селекције. Ова хеуристика (такође понекад називана метахеуристика) се рутински користи да генерише корисна решења за оптимизацију и проблеме претраге. Генетски алгоритми припадају већој класи еволуционих алгоритама (ЕА) који генеришу решења за оптимизацију проблема коришћењем техника инсприсаних природном еволуцијом, као што су наслеђивање, мутација, селекција и кросинг-овер.

Принцип рада

Рад ГА се може описати у осам односно седам корака:

1. Дефинисање свих потребних параметара проблема и ГА
2. Формирање почетне популације
3. Декодирање хромозома — овај корак се јавља само код бинарних ГА
4. Одређивање цена хромозомима (фитнес функцијом)
5. Одабир селекције хромозома који ће опстати за парење
6. Парење — обично се из бољег дела популације одабиру родитељи који ће на неки начин укрстити свој генетски материјал и дати једног или више потомака који обично замене неког од лошијих хромозома
7. Мутације, при којима се мења генетски садржај хромозома
8. Испитивање конвергенције, да би се утврдило да ли има основа да се ток алгоритма прекине. Уколико није испуњен услов конвергенције, вратити се на корак 3 односно 4.

Методологија

Проблеми оптимизације

У генетском алгоритму, популација решења кандидати (тзв. појединаца, бића или фенотипа) проблема оптимизације еволуира ка бољим решењима. Свако решење кандидат има скуп особина (својих хромозома или генотипа) који може да буде мутиран или измењен; традиционално решења су представљена бинарно, као низови нула и јединица, али и друга кодирања су такође могућа.

Еволуција обично почиње од популације насумично генерисаних појединаца, и то је процес који се понавља, са популацијом која се у свакој итерацији зове генерација. У свакој генерацији фитнес сваког појединца у популацији се оцењује; фитнес је обично вредност објектне функције у проблему оптимизације који се решава. Што више фит (здрави) појединци су стохастички селектовани из тренутне популације, и геном сваке идивидуе се мења (комбинован и евентуално случајно мутиран) како би се формирала нова генерација. Нова генерација добијених решења кандидата се затим користи у следећој итерацији алгоритма. Углавном, алгоритам се завршава или када је произведен максимални број генерација или је достигнут задовољавајући ниво фитнеса за популацију.

Типичан генетски алгоритам захтева:

1. Генетски приказ домена решења
2. Функцију фитнес за процену домена решења

Стандардна репрезентација сваког решења кандидата је низ битова.Низови других типова и структура се у суштини могу користити на исти начи. Главна особина који чини ове генетске репрезентације погодне је да су њихови делови јако усклађени због фиксне величине што олакшава једноставне опереције кросинг-овера. Променљива дужина репрезентације се такође може користити, али је имплементација кросинг-овера у овом случају сложенија. Репрезентације попут стабла су истражене у генетском програмирању и репрезентације форме графа су истражене у еволуционом програмирању; мешавина оба, линеарних хромозома и стабала је истражена у програмирању заснованом на приказу гена.

Када су генетска репрезентација и фитнес функција дефинисани, ГА наставља да покреће популацију решења и побољшава је периодично применом мутација, кросинг-овера, инверзија и селекције.

Иницијализација

Величина популације зависи од природе проблема, али обично садржи неколико стотина или хиљада могућих решења. Често се почетна популација генерише насумично, чиме се омогућава читав низ могућих решења (простор претраге). Повремено, решења могу бити „посејана“ у областима где је могуће наћи оптимална решења.

Селекција

Током сваке следеће генерације део постојеће популације је изабран да одгоји нову генерацију. Индивидуална решења су изабрана помочу процеса базираног на фитнесу(здрављу), где више фит(здравија, са бољом кондицијом) решења(мерена фитнес функцијом) имају веће шансе да буду изабрана. Одређене методе селекције оцењују кондицију сваког решења и првенствено ће изабрати најбоља решења.

Функција фитнес је дефинисана у генетској репрезентацији и мери квалитет прдстављеног решења. Функција фитнес увек зависи од проблема. На пример у проблему ранца, неко жели највећу укупну вредност предмета која се може ставити у ранац фиксног капацитета. Репрезентација решења може бити низ битова, где ће сваки бит представљати други предмет, и вредност бита (0 или 1) да ли је или не предмет у ранцу. Није свака оваква репрезентација добра, јер величина предмета може бити већа од капацитета ранца. Фитнес решење је збир вредности свих објеката у ранцу уколико је репрезентација валидна, или 0 у супротном.

У неким случајевима, тешко је или немогуће одредитити фитнес. Ако је тако, може се искористити симулација да одреди вредност фитнес функције за фенотип (нпр. Рачунарска динамика флуида се користи да се утврди отпор ваздуха аутомобила чији је облик кодиран као фенотип) или се чак користи интерактивни генетички алгоритам.

Генетски оператори

Следећи корак је генерисати другу генерацију популације решења од оних изабраних кроз комбинацију генетских оператора: кросинг-овера(назива се и рекомбинација) и мутације.

За свако ново решење које ће се произвести, бира се пар „родитељских“ решења за размножавање из базена претходно изабраних.

Стварањем решења „детета“ коришћењем горе наведених метода кросинг-овера и мутације креирано је ново решење које обично има многе караткеристике својих „родитеља“. За свако ново дете се бирају нови родитељи и процес се наставља све док нова популација решења не достигне одговарајућу величину. Иако су методи репродукције који се заснивају на коришћењу два родитеља „биолошки подстакнути“ нека истраживања сугеришу да се коришћењем више од два „родитеља“ генерише квалитетније хромозоме.

Ови процеси на крају дооде до следеће генерације популације хромозома која се разликује од почетне генерације. Генерално, просечна кондиција ће порасти овим процесима за популацију, јер су изабрани само најбољи организми из прве генерације за размножавање, заједно са малим процентом мање подобних решења. Ова мање фит решења гарантују генетску разноликост унутар генетског базена родитеља и стога гарантују генетску разноликост наредних генерација деце.

Мишљење је подељено око важности кросинг-овера наспрам мутација. Постоје многе референце у Фогеловом раду (2006) које подржавају значај претрага базираних на мутацијама.

Иако су кросинг-овери и мутације познати као главни генетски оператори, могуће је користити и друге операторе као што су прегруписање, колонизације-истребљења или миграције у генетским алгоритмима.

Вреди подесити параметре као што су вероватноћа мутације, вероватноћа кросинг-овера и величина популација да би се пронашла разумна подешавања за класу проблема на којој се ради. Веома мала стопа мутација води до генетичког дрифта (који није равномерно распоређен у природи). Стопа рекомбинације која је превисока може довести до преране конвергенције генетског алгоритма. Стопа мутација која је превисока може довести до губитка добрих решења, осим ако је искоришћен елитистички избор.

Завршетак

Овај генерацијски процес се понавља све док се не постигне услов прекида. Општи услови завршетка су:

• Решење које је пронађено задовољава минималне критеријуме
• Достигнут је фиксиран број генерација
• Додељен буџет (изрчунава се време / новац) је потрошен
• Фитнес решења које је највише ранкирано достиже или је достигао плато такав да узастопне итерације не дају боље резултате
• Ручно проверавање
• Комбинација наведених услова

Хипотеза градивног блока

Генетички алгоритми су једноставни за имплементацију али њихово понашање је тешко разумети. Тачније, тешко је разумети зашто ови алгоритми често успевају да генеришу решења високог фитнеса када се примене на одређен проблем. Хипотеза градивног блока (енг: буилдинг блоцк хyпотхесис, ББХ) се састоји од:

1. Опис хеуристике која обавља адаптацију тако што идентификује и комбинује градивне блокове, нпр. схема ниског реда са фитнесом изнад просека.
2. Хипотеза којом генетички алгоритам врши имплицитну адаптацију и ефикасно имплементира ову хеуристику.

Голдберг описује хеуристику на следећи начин:

„Кратке схеме ниског реда и са високим фитнесом се узоркују (узимају узорци), кобинују и поново узоркују како би направили стрингове потенцијално већег фитнеса. Радећи са овим схемама (тј. градивним блоковима), смањили смо сложеност нашег проблема; уместо да правимо врло ефикасне стрингове покашавајући са сваком могућом комбинацијом, ми правимо све боље и боље стрингове користећи најбоља парцијална решења претходног узорковања.“

"Како кратке схеме ниског реда са високог фитнеса играју веома битну улогу у генетским алгоритмима, дали смо им специјално име: градивни блокови. Баш као што дете прави величанствене тврђаве слажући једноставне блокове дрвета, тако и генетски алгоритам постиже скоро оптималне перформансе слажући крате схеме ниског реда и високих перформанси, тј. градивне блокове."

Ограничења

Постоје ограничења употребе генетског алгоритма у односу на алтернативне алгоритме за оптимизацију:

• Поновљена процена фитнес функције за сложене проблеме је заштитнички и ограничавајући сегмент вештачких еволуционих алгоритама. Проналажење оптималног решења за сложене високо-димензионе, мултимодалне проблеме често захтева веома скупе процене фитнес функција. У реалном свету проблемни као што су структурни проблеми оптимизације евалуација једне функције може да захтева од неколико сати до неколико дана потпуне симулације. Типични методи оптимизације не могу да се баве таквим врстама проблема. У овом случају може бити неопходно да се одрекну тачне процене и користе приближну фитнес која је рачунски ефикасна. Очигледано је да спој прибижних модела може бити један од најперспективнијих приступа да се убедљиво користе ГА за решавање комплексних проблема из реалног живота.

• Генетски алгоритми не раде добро сразмерно сложености. То јест, када је број елемената који су изложени мутацији велики често постоји експоненцијални пораст у величини простора за претрагу. Због тога је изузетно тешко користити технику на проблемима као што су пројектовање мотора, куће или авиона. Како би такви проблеми били поводљиви еволуционој потрази они морају бити разбијени на што једноставније могуће репрезентације. Стога обично видимо еволуционе алгоритме за кодирање дизајна за лопатице вентиатора уместо мотора, моделовање облика уместо детаљних планова конструкције, крила авиона уместо дизајна читавих авиона. Други проблем комплексности је како заштитити делове који су еволуирали да представљају добра решења од даљих деструктивних мутација, нарочито када њихова процена фитнеса захтева да се комбинује са другим деловима.

• „Боље“ решење је само у поређењу са другим решењима. Као резултат, критеријум заустављања није јасан у сваком проблему,

• У многим проблемима, ГА-ми имају тенденцију да се прилагоде према локалним оптимумима или чак произвољним тачкама, пре него глобалним оптимумима проблема. Ово значи да оно не „зна како“ да жртвује краткорочну кондицију да стекне дугорочну кондицију. Вероватноћа да се то дешава зависи од облика фитнес пејзажа: одређени проблеми мофу да обезбеде лак успон ка глобалном оптимуму, други могу олакшати функцији да пронађе локалне оптимуме. Овај проблем се може ублажити коришћењем друге фитнес функције, повећањем стопе мутација или помоћу техника селекције које одржавају разноликост популације решења, иако „Нема бесплатног ручка“ теорема доказује да не постоји опште решење овог проблема. Уобичајена техника за одржавање разноликости је да наметне „казну“ где било која група појединаца са довољно сличности добију казну, што ће смањити застубљеност те групе у наредним генерацијама, омогућавајући другим (мање сличним) појединцима да опстану у популацији. Овај трик, међутим, можда неће бити ефикасан, у зависности од предела проблема. Још једна могућа техника би била да се једноставно замене делови популације са случајно генерисаним појединцима, када је већина популације превише слична једна другима. Разноликост је важна у генетским алгоритмима (и генетском програмирању) јер прелазак преко хомогене популације не даје нова решења. У еволуционим стратегијама и еволуционом програмирању, разноликост није од суштинског значаја због већег ослањања на мутације.

• Рад на динамичком сету података је тежак, како геноми почну да конвергирају рано према решењима која можда више нече важити за касније податке. Неколико метода је предложено да се поправи ово повечањем генетске разноликости некако и спречавањем ране конвергенције, било повећањем вероватноће мутације када је решење квалитет капи (називано започета хипермутација), или повремено увођењем поптуно нових, случајно генерисаних елемеанта у геному (називају се и случајни имигранти). Еволуционе стратегије и еволуционо програмирање могу се имплементирати са такозваном „зарез стратегијом“ у којој родитељи нису одржавани и нови родитељи се бирају само од потомства. Ово може бити ефикасније на динамичким проблемима.

• Генетски алгоритми не могу ефикасно решити проблеме у којима је једина мера за фитнес тачно/нетачно (као проблеми одлуке), како не постоји начин да се концентришу на решења (нема брда да се попне). У овим случајевима, случајна претрага може наћи решење брзо као и генетски алгоритам. Међутим, ако ситуација дозвољава успех/неуспех суђење да се понови, давајућу (евентуално) различити резултат, онда однос успеха неуспеха пружа одређену меру фитнеса.

• За специфичне проблеме оптимизације и инстанце проблема, други алгоритми оптимизације могу бити ефикаснији од генетских алгоритама у погледу брзине конвергенције. Алтернативни и комплементарни алгоритми укључују еволуционе стратегије, еволуционо програмирање, Гаусову адаптацију, претраживање успоном и интелигенцију јата (нпр. оптимизација колоније мрава, оптимизација честица роја) методи базирани на целобројном линеарном програмирању. Погодност генетских алгоритама зависи од количине знања о проблему; добро познати проблеми често имају боље, специјализованије приступе.

Варијанте

Репрезентација хромозома

Најједноставнији алгоритам представља сваки хромозом као низ битова. Нумерички параметри се углавном могу представити целим бројевима (енг. интегер), али је могуће корисити и репрезентацију у покретном зарезу. Репрезентација у покретном зарезу је природна за еволуционе стратегије и еволуционо програмирање. Појам генетских алгоритама реалних вредности је био предложен, али је то погрешан назив, јер не презентује теорију градивног блока коју је предложио Јохн Хенрy Холланд 1970их. Ова теорија има подршку, засновану на теоретским и експерименталним резултатима. Основни алгоритам извршава прелазак (цроссовер) и мутацију на нивоу битова. Друге варијанте третирају хромозоме као листу бројева који су показивачи на повезане листе, асоцијативне низове, објекте или било које друге замисливе структуре података. Кросинг-овер и мутација се извршаваја тако да поштују границе типа елемента. За већину типова података се могу конструисати оператори за варијације. Различити типови података којима се представљају хромозоми раде боље или лошије за различите домене проблема.

Када се корсите репрезентације у виду низова битова, често се примењује Грејев код. На овај начин, мале промене у броју могу бити проузроковане мутацијама и преласцима. Овако се спречава превремена конвергенција ка такозваним Хаминговим зидовима (енг. Хамминг wаллс), где се врло много симултаних мутација (или прелазака) мора десити да би се хромозом променио на боље.

Други приступи укључују коришћење низова реалних бројева уместо низова битова за репрезентацију хромозома. Резултати теорије схема предлажу да што је мањи алфабет, боље су перформансе, али је на почетку истраживачима било врло необично да су добијали добре резултате корстећи овакав приказ хромозома. Ово је објашњено скупом реалних вредности у коначној популацији хромозома који формира виртуелни алфабет (када су селекција и комбинација доминантне) са мањом кардиналности од оне очекиване од репрезентације у покретном зарезу.

Проширење приступачног домена проблема Генетског Алгоритма се може постићи кроз комплексно кодирање скупа решења надовезивањем неколико типова хетерогено кодираних гена у један хромозом. Овај приступ дозвољава решавање проблема оптимизације који захтевају веома различите дефиниције домена за параметре проблема.

Елитизам

Практична варијанта процеса конструисања нове популације је дозволити да се најбољи организам (тј. организми) тренутне генерације пренесе у следећу, непромењен. Ова стратегија је позната као елитистичка селекција и осигруава да се квалитет решења добијеног генетским алгоритмом неће смањивати из генерације у генерацију.

Паралелна имплементација

Паралелне имплементације генетских алгоритама долазе у две врсте. „Крупнозрнасти“ (енг. цоарсе-граинед) паралелни генетски алгоритми претпостављају да постоји популација на сваком чвору и миграција појединаца између чворова. „Ситнозрнасти“ (енг. фине-граинед) паралелни генетски алгоритми претпостављају да постоји појединац на сваком чвору који интерагује са суседним појединцима ради селекције и репродукције. Друге варијанте, као на пример генетски алгоритми за онлине проблеме оптимизације, уводе зависност од времена или „буку“ у фитнес функцији.

Прилагодљиви Генетски Алгоритми

Генетски алгоритми са прилагодљивим параметрима (прилагодљиви генетски алгоритми, ПГА-ми) су још једна важна и обећавајућа варијанта генетских алгоритама. Вероватноћа преласка и мутације значајно утичу на прецизност решења и брзину конвергенције коју алгоритми могу да постигну. Уместо да користе фиксне вредности за ове вероватноће, ПГА-ми користе информације о популацији у свакој генерацији и прилагодљиво подешавају вероватноће преласка и мутације како би задржали разноликост популације али и одржали капацитет конвергенције. У ПГА-мима подешевања вероватноћа зависе од вредности фитнеса решења. У ПГА-мима заснованим на груписању (енг. цлустеринг-басед адаптиве генетиц алгоритхм), кроз коришћење анализе груписања ради процене стања оптимизације популације, подешавања вероватноћа преласка и мутације зависе од ових стања оптимизације. Комбиновање генетског алгоритма са другим методама оптимизације може бити врло ефикасно. Генетски алгоритам је врло добар за проналажење добрих глобалних решења, али исто тако врло неефикасан у проналажењу последњих неколико мутација ради проналажења апсолутног оптимума. Друге технике (као на пример претраживање успоном (енг. хилл цлимбинг)) су врло добре у проналажењу апсолутног оптимума у ограниченом интервалу. Мешање генетског алгоритма и претраге успоном може побољшати ефикасност генетског алгоритма и смањити грубост претраге успоном.

Ово значи да правила генетске варијације могу имати другачија значења у природи. На пример - ако су кораци сачувани узаступно - прелазак може да сумира број корака мајчине ДНК додајући кораке очеве ДНК итд. Штавише, инверзни оператор има прилику да сложи кораке узаступно или у неком другом погодном поретку, ради преживљавања или ефикасности. (Видети на пример или пример у проблему трговачког путника, а посебно коришћење оператора комбинације).

Варијанта, где популација као целина еволуира уместо њених појединачних припадника, је позната као комбинација генетског базена.

Развијен је велики број варијанти како би се побољшале перформансе генетских алгоритама који раде на проблемима са високим степеном епистазе фитхенса, нпр. када се фитнес решења састоји од подскупова варијабли који међусобно интерагују. Ови алгоритми теже томе да прво науче а тек онда искористе понашање ових корисних фенотипских интеракција. Као такви, слажу се са хипотезом градивног блока у прилагодљивом смањивању лоших комбинација. Истакнути примери овог приступа су мГА, ГЕМГА и ЛЛГА.

Домени проблема

Проблеми које је врло прикладно решавати генетским алгоритмом су проблеми прављења распореда и многи софттвер који ради на прављењу распореда је заснован на генетским алгоритмима. Генетски алгоритми се могу применити и на инжењерство. Генетски алгоритми се често примењују за решавање проблема глобалне оптимизације.

Као генерално правило, генетски алгоритми могу бити корисни у домену проблема који имају комплексан пејзаш фитнеса, како је мешање, на пример мутација и прелазака, створено да би се популација померила од локалног оптимума, на коме се алгоритам претраге успоном може заглавити. Може се приметити да се оператори преласка који се често користе не могу променити униформну популацију.

Примери проблема које решава генетски алгоритам су: огледала која су направљена да скупља сунчеву светлост у соларни колектор, антене направљене да примају радио сигнале у свемиру, и методи за ходање код компјутерских фигура.

У свом Алгоритхм Десигн Мануал, Скиена је против коришћења генетских алгоритама у било које сврхе:

„Неприродно је моделовати апликације у погледу генетских оператора као што су мутације или кросинг-овер низова битова. Псеудобиологија додаје још један ниво комплексности између тебе и твог проблема. Такође, генетски алгоритми се дуго извршавају над нетривијалним проблемима. [...] Аналогија са еволуцијом — где значајан напредак захтева милионе година — може бити врло прикладна.

Никада нисам наишао на проблем за који су ми генетски алгоритми изгледали као прави начин за решавање. Такође, никада нисам видео неке резултате који су добијени генетским алгоритмима који су ме одушевили.“

- Стевен Скиена

Комерцијални производи

Касних 1980их, Генерал Елецтриц су почели са продајом првог генетског алгоритма, алат базиран на маинфраме-у направљен за потребе индустриједе. 1989, Аxцелис Инц. шаљу на тржиште Еволвер, први комерцијални софтвер који користи генетски алгоритам за десктоп рачунаре. Јохн Маркофф, колумниста Тхе Неw Yорк Тимес-а задужен за технологије, је писао о Еволверу, 1990., и Еволвер је био једини интерактивни комерцијални генетски алгоритам све до 1995. Еволвер је купио Палисаде 1997. године, преведен је на неколико језика, и тренутно је у својој шестој верзији..

Сродне технике

Родитељске области

Генетски алгоритми су подобласт:

• Еволуционих алгоритама
• Еволуционог рачунарства
• Метахеуристике
• Стохастичке оптимизације
• Оптимизације

Сродне области

Еволуциони алгоритми

Еволуциони алгоритми су подобласт еволуционог порграмирања.

• Еволуционе стратегије развијају појединце средствима за мутацију и путем посредне или дискретне рекомбинације. Ови алгоритми су посебно дизајнирани да реше проблеме у домену реалних вредности. Користе самосталну адаптацију да прилагоде параметре претраге. Смањивање самосталне адаптације је довело до савремене еволуционе стратегије адаптације ковариационих матрица (ЦМА-ЕС).

• Еволуционо програмирање обухвата популацију решења са првенствено мутацијом и селекцијом и произвољном репрезентацијом. Они користе самосталну адаптацију да прилагоде параметре, и могу да укјуче друге варијације операција као што је комбиновање операција од више родитеља.

• Програмирање засновано на приказу гена такође користи популације компјутерских програма. Ови комплексни компјутерски програми су кодирани једноставнијим линеарним хромозомима фиксне дужине, који су касније изражена као стабла израза. Стабла израза компјутерског програма се развијају зато што хромозоми пролазе мутацију и рекомбинацију на начин сличан каконском ГА. Захваљујући специјалној организацији ГЕП хромозома, ове генетске модификације увек као резултат дају валидне компјутерске програме.

• Генетско програмирање је сродна техника коју је учинио популарном Џон Коза (енг. Јохн Коза) у којој су компјутерски програми, уместо параметара функције, оптимизовани. Генетско програмирање често користи структуре података базиране на стаблима за представљање компјутерских програма за адаптацију уместо структуру листи типичну за генетске алгоритме.

• Интерактивни еволуциони алгоритми су еволуциони алгоритми који користе људску еволуцију. Често су примењени у доменима где је тешко дизајнирати рачунску фитнес функцију, на пример, развијање слика, музика, уметнички дизајн и облици који ће се уклопити у естетски укус корисника.

Интелигенција роја

Интелигенција роја је подобласт еволуционог програмирања.

• Оптимизација колоније мрава користи много мрава да пролазе кроз простор решења и пронађу локалне продуктивне области. Иако је иначе лошији у односу на генетске алгоритме и друге облике локалне претраге, у стању је да произведе решења за проблеме за које не може да се постигне ни глобална ни најновија перспектива, па самим тим ни друге методе не могу бити примењене.

• Оптимизација роја честица (ПСО) је рачунска метода за оптимизацију више параметара који се корити у приступу заснованом на популацији. Популација (јато) кандидатских решења (честица) се креће у потрази за простором, и на кретање честица утичу и њихова најбоља позиција и најбоља позиција јата. Као и генетски алгоритам, овај метод зависи од информација које се деле између чланова популације. Код неких проблема ПСО је често рачунски ефикаснији од ГА-а, поготово код неконстантних проблема са сталним променљивама.

Други еволуциони компјутерски алгоритми

Еволутивно израчунавање је подобласт метахеуристичких метода

• Хармонијска претрага (ХС) је алгоритам који опонаша понашање музичара у процесу импровизације.

• Бактериолошки алгоритми (БА) су инспирисани еволутивном екологијом и, још прецизније, бакериолошком адаптацијом. Еволутивна екологија је област проучавања живих организама у смислу њиховог окружења са циљем да открије како се они прилагођавају. Основни концепт је да у хетерогеној средини се не може пронаћи једна јединка која се уклапа у целу околину. Дакле, треба да се размишља на нивоу целе популације. Такође се верује да се БА-и могу успешно применити на сложене проблеме позиционирања(антена за мобилне телефоне, урнбанистички планови итд.) или дата мининг.

• Диференцијални алгоритам за претрагу (ДС) је инспирисан миграцијом суперорганизама.

Друге методе метахеуристике

Метахеуристичке методе широко спадају у стохастичке методе за оптимизацију

• Табу претрага: прелази по пољу решења тестирањем мутација појединачног решења. Генерише много мутираних решења и прелази на решње најмање енергије од свих генерисаних. Како би се избегло вртење у круг и подржала што разноврсније кретање кроз простор решења, чува се табу листа парцијалних или комплетних решења. Забрањено је прећи у решење које садржи елементе из листе, која се редовно мења и допуњује.

• Оптимизација екстремума: За разлику од генетских алгоритама, који раде са популацијом решења кандидата, овај алгоритам развија јединствено решење и прави модификације над најгорим компонентама. Главни принцип иза овог алгоритма је побољшавање кроз селективно уклањање компоненти лошег квалитета и мењање истих насумично изабраним компонентама. Ово је дефинитивно супротно од генетског алгоритма који бира добра решења и покушава да направи још боља.

Друге стохастичке методе оптимизације

• Метод унакрсне ентропије генерише решења кандидате преко параметризоване расподеле вероватноће. Параметри се ажурирају путем минимизације унакрсном ентропијеом, како би се генерисали бољи узорци у следећој итерацији.

• Реактивна оптимизација претраге (енг. реацтиве сеарцх оптимизатион (РСО)) подржава интеграцију техника машинског учења у хеуристику претраге за решавање комплексних проблема оптимизације. Реч „реактивна“ наговештава постојање спремног одговора на догађаје током претраге кроз петљу интерних онлине повратних информација ради самоподешавања критичних параметара. Методологије од интереса за реактивну претрагу укључују машинско учење и статистику.

Види још

• Метахеуристика
• Генетско програмирање
• Оптимизација ројењем честица
• Оптимизација симулирањем колоније мрава

Спољашње везе

Ресурси

• Генетиц Алгоритхмс Индеx Листа ресурса на пољу генетских алгоритама

Приручници

• Генетиц Алгоритхмс Цомпутер "еволве" ин wаyс тхат ресембле натурал селецтион цан солве цомплеx проблемс евен тхеир цреаторс до нот фуллy ундерстанд Увод у генетске алгоритме Џона Холанда (енг. Јохн Холланд)
• Ан онлине интерацтиве ГА туториал фор а реадер то працтисе ор леарн хоw а ГА wоркс: Учење корак по корак, мењање величине популације, стопе кросинг-овера и мутација.
• А Генетиц Алгоритхм Туториал бy Даррелл Wхитлеy Цомпутер Сциенце Департмент Цолорадо Стате Университy Приручник уз много теорије
• "Ессентиалс оф Метахеуристицс", 2009 (225 п).
• Глобал Оптимизатион Алгоритхмс - Тхеорy анд Апплицатион Архивирано на сајту Wayback Machine (11. септембар 2008)