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

Идеја о генетским алгоритмима (ГА) појавила се прилично давно (1950–1975), али су постали стварни предмет истраживања тек у последњим деценијама. Д. Холланд се сматрао пиониром у овој области, који је позајмио много генетике и прилагодио их компјутерима. ГА се широко користе у системима вештачке интелигенције, неуронским мрежама и проблемима оптимизације.

Еволуцијска претрага

Модели генетичких алгоритама креирани су на основу еволуције у дивљини и методама случајног претраживања. Истовремено, насумична претрага је имплементација најједноставније функције еволуције - случајних мутација и накнадне селекције.

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

Зашто су нам потребни генетски алгоритми

ГА има следеће циљеве:

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

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

Карактеристике ГА

Навешћемо главне разлике ГА од већине других метода проналажења оптималног решења.

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

Критеријуми учинка

Генетски алгоритми израђују прорачуне на основу два услова:

1. Извршите одређени број итерација.
2. Квалитет пронађеног рјешења задовољава захтјеве.

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

Основна терминологија

Због чињенице да се ГА заснива на генетици, већина терминологије одговара томе. Сваки генетски алгоритам функционише на основу иницијалних информација. Сет почетних вредности је популација ^{т т} = {н ₁ , н ₂ , ..., н _н }, где је н _и = {р ₁ , ..., р _в }. Детаљније ћемо испитати:

• т је број итерације. т ₁ , ..., т _к - означава итерацију алгоритма од броја 1 до к, при чему се при свакој итерацији ствара нова популација рјешења.
• н је величина популације П ^т .
• ₁ , ..., п _i - хромосома, особь, или организм. н ₁ , ..., н _и - хромозом, појединац или организам. Хромозом или ланац је кодирана секвенца гена, од којих сваки има секвенцијски број. Треба имати у виду да хромозом може бити посебан случај појединца (организма).
• р _в су гени који су део кодираног решења.
• Локус је секвенцијски број гена у хромозому. Алел је вредност гена која може бити и нумеричка и функционална.

Шта значи "кодиран" у контексту ГА? Обично се свака вредност кодира на основу абецеде. Најједноставнији пример је конверзија бројева из децималног система бројева у бинарну репрезентацију. Дакле, абецеда је представљена као скуп {0, 1}, а број 157 ₁₀ ће бити кодиран хромозомом 10011101 ₂ , који се састоји од осам гена.

Родитељи и потомци

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

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

Функција фитнесса

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

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

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

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

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

У корацима разложимо најједноставније (класичне) ГА.

1. Иницијализација почетних вриједности, тј. Дефиниција примарне популације, скуп појединаца с којима ће се одвијати еволуција.
2. Утврђивање примарне способности сваког појединца у популацији.
3. Проверите услове завршетка за итерације алгоритма.
4. Коришћење функције избора.
5. Употреба генетских оператора.
6. Стварање нове популације.
7. Кораци 2-6 се понављају у циклусу све док се не испуни неопходни услов, након чега долази до одабира најприлагођеније особе.

Идемо укратко кроз мале очигледне делове алгоритма. Постоје два услова за раскид:

1. Број понављања.
2. Квалитет решења.

Генетски оператори су оператор мутације и оператер скретнице. Мутација мења случајне гене са одређеном вероватноћом. По правилу, вероватноћа мутације има ниску нумеричку вредност. Разговарајмо више о процедури генетског алгоритма "крижање". То се дешава према следећем принципу:

1. За сваки пар родитеља који садржи Л гене, тачку укрштања Тск _{и је} насумично одабрана.
2. Први потомак је састављен спајањем [1; Тск _и ] гени првог родитеља [Тск _{и + 1} ; Л] гени другог родитеља.
3. Други потомак је састављен на обрнути начин. Сада на гене другог родитеља [1; Тск _и ] додаје гене првог родитеља на позиције [Тск _{и + 1} ; Л].

Тривиални пример

Рјешавамо проблем генетичким алгоритмом на примјеру тражења појединца с максималним бројем јединица. Нека се појединац састоји од 10 гена. Примарну популацију додељујемо у осам особа. Очигледно, најбољи појединац би требао бити 1111111111. Надокнадимо одлуку ГА.

• Инитиализатион. Изабери 8 случајних појединаца:

• Процена способности. Очигледно, у нашем генетском алгоритму, фитнес функција Ф броји број јединица у сваком појединцу. Дакле, имамо:

Из табеле је видљиво да појединци 3 и 7 имају највећи број јединица, те су стога најприкладнији чланови популације за рјешавање проблема. Пошто тренутно не постоји решење потребног квалитета, алгоритам наставља са радом. Потребно је извршити избор појединаца. Ради лакшег објашњења, нека селекција буде случајна, и добијемо узорак појединаца (н ₇ , н ₃ , н ₁ , н ₇ , н ₃ , н ₇ , н ₄ , н ₂ ) - то су родитељи за нову популацију.

• Употреба генетских оператора. Опет, за једноставност, претпостављамо да је вероватноћа мутација 0. Другим речима, свих 8 појединаца прелазе своје гене као што су они. За укрштање, правимо парове појединаца насумице: (н ₂ , н ₇ ), (н ₁ , н ₇ ), (н ₃ , н ₄ ) и (н ₃ , н ₇ ). На исти насумичан начин, одабрани су прелази за сваки пар:

• Компилација нове популације која се састоји од потомака:

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

Даље акције су очигледне. Најинтересантнија ствар у ГА је, ако проценимо просечан број јединица у свакој популацији. У првој популацији, у просјеку, било је 5.375 јединица за сваког појединца, у популацији потомака - 6.25 јединица по појединцу. И таква особина ће се посматрати чак и ако се током мутација и преласка особе са највећим бројем јединица у првој популацији изгуби.

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

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

1. Дефиниција репрезентације (абецеда).
2. Дефиниција оператора случајне промене.
3. Дефиниција преживљавања појединаца.
4. Генерација примарне популације.

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

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

Избор метода преживљавања може бити изузетно варљив. Постоји много начина у генетском алгоритму за узгој. И, како пракса показује, правило "опстанка најспособнијих" није увек најбоље. Код рјешавања сложених техничких проблема, често се испоставља да је најбоље рјешење из мноштва средњих или још горег. Стога је често прихваћено да се користи пробабилистички приступ, који каже да најбоље рјешење има боље шансе за преживљавање.

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

Ефективност

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

1. Стварање комплетне популације која ће укључити све врсте опција за појединце у датој области.
2. Насумично креирање појединаца на основу свих важећих вриједности.
3. Дот случајно креирање појединаца, када је међу прихватљивим вредностима изабран опсег за генерисање.
4. Комбинујући прва три начина за стварање популације.

Дакле, можемо закључити да ефикасност генетских алгоритама у великој мери зависи од искуства програмера у овом питању. То је и недостатак генетских алгоритама и њихова предност.