Genetický algoritmus

Čo je to

Prirodzenú evolúciu možno modelovať ako hru, v ktorej odmenou pre organizmus, ktorý hrá dobrú hru života, je odovzdávanie genetického materiálu jeho nasledovníkom a jeho ďalšie prežitie.^[2] V prirodzenej evolúcii to, ako dobre jedinec funguje, závisí od toho, s kým spolupracuje a s kým súperí, ako aj od prostredia. Genetické algoritmy sú simuláciou prirodzeného výberu na populácii kandidátskych riešení optimalizačného problému (chromozómy, jedinci, tvory alebo fenotypy).

Kandidáti sa hodnotia a krížia v snahe vytvoriť dobré riešenia. Takéto riešenia môžu zabrať veľa času a pre človeka nie sú zrejmé. Evolučná fáza sa začína s populáciou náhodne vygenerovaných bytostí. V každej generácii sa vyhodnocuje fitness každého jedinca v populácii. Niektoré z nich sa náhodne vyberú z aktuálnej populácie (na základe ich fitness) a modifikujú sa (rekombinujú a prípadne náhodne mutujú), aby sa vytvorila nová populácia. Cyklus sa opakuje s touto novou populáciou. Algoritmus sa skončí buď po uplynutí stanoveného počtu generácií, alebo po dosiahnutí dobrej úrovne fitness populácie. Ak algoritmus skončil z dôvodu dosiahnutia maximálneho počtu generácií, nemusí to nevyhnutne znamenať, že sa dosiahla dobrá úroveň fitness.

Programovanie na počítači

Pseudokód je:

1. Inicializácia: Vytvorí sa niekoľko možných riešení; veľmi často majú náhodné hodnoty.
2. Hodnotenie: Výsledkom hodnotenia je číslo, ktoré hovorí o tom, ako dobre toto riešenie rieši problém.
3. Nasledujúce kroky sa vykonávajú, kým sa nesplní požiadavka na zastavenie:
1. Výber: Výber riešení/jednotlivcov pre ďalšiu iteráciu
2. Rekombinácia: Kombinujte vybrané riešenia
3. Mutácia: náhodne mení novovytvorené riešenia
4. Hodnotenie: Použite funkciu fitness, pozri krok 2.
5. Ak nie je splnená požiadavka na zastavenie, znovu začnite s výberovým krokom.

Príklad

Uvedený opis je abstraktný. Pomôže konkrétny príklad.

Aplikácie

Vo všeobecnosti

Genetické algoritmy sú dobré pri riešení problémov, ktoré zahŕňajú plánovanie a rozvrhovanie. Uplatňujú sa aj v strojárstve. Často sa používajú na riešenie globálnych optimalizačných problémov.

Všeobecne platí, že genetické algoritmy môžu byť užitočné v problémových oblastiach, ktoré majú komplexné fitness prostredie, pretože miešanie je navrhnuté tak, aby posunulo populáciu preč od lokálnych optim, v ktorých by tradičný algoritmus kopcovitého lezenia mohol uviaznuť. Bežne používané operátory kríženia nemôžu zmeniť žiadnu jednotnú populáciu. Samotná mutácia môže zabezpečiť ergodicitu celkového procesu genetického algoritmu (vnímaného ako Markovov reťazec).

Príklady problémov riešených genetickými algoritmami zahŕňajú: zrkadlá navrhnuté na usmernenie slnečného svetla do slnečného kolektora, antény navrhnuté na zachytávanie rádiových signálov vo vesmíre, metódy chôdze pre počítačové postavy, optimálny návrh aerodynamických telies v zložitých prúdových poliach

Skiena vo svojej Príručke návrhu algoritmov neodporúča genetické algoritmy pre akúkoľvek úlohu: "Je celkom neprirodzené modelovať aplikácie v zmysle genetických operátorov, ako sú mutácia a kríženie na bitových reťazcoch. Pseudobiológia pridáva ďalšiu úroveň zložitosti medzi vás a váš problém. Po druhé, genetické algoritmy potrebujú na netriviálne problémy veľmi veľa času. [...] Analógia s evolúciou - kde si významný pokrok vyžaduje [sic] milióny rokov - môže byť celkom vhodná. [...] Nikdy som sa nestretol so žiadnym problémom, pri ktorom by sa mi genetické algoritmy zdali správnym spôsobom, ako naň zaútočiť. Ďalej som nikdy nevidel žiadne výsledky výpočtov oznámené pomocou genetických algoritmov, ktoré by na mňa urobili priaznivý dojem. Pre potreby heuristického vyhľadávania voodoo sa držte simulovaného žíhania."

Stolové hry

Stolové hry sú veľmi dôležitou súčasťou oblasti genetických algoritmov aplikovaných na problémy teórie hier. Veľká časť ranej práce v oblasti výpočtovej inteligencie a hier bola zameraná na klasické stolové hry, ako napríklad tic-tac-toe,^[3] šach a dáma.^[4] Stolové hry dnes vo väčšine prípadov dokáže počítač hrať na vyššej úrovni ako najlepší ľudia, a to dokonca aj pomocou techník slepého vyčerpávajúceho vyhľadávania. Hra Go je v tomto smere výnimkou a doteraz odolávala útokom strojov. Najlepší počítačoví hráči Go hrajú v súčasnosti na úrovni dobrého začiatočníka.^[5][6] Hovorí sa, že stratégia hry Go sa vo veľkej miere spolieha na rozpoznávanie vzorov, a nie len na logickú analýzu ako v šachu a iných hrách, ktoré sú viac závislé od figúr. Obrovský efektívny faktor vetvenia potrebný na nájdenie kvalitných riešení výrazne obmedzuje pohľad dopredu, ktorý možno použiť v rámci hľadania postupnosti ťahov.

Počítačové hry

Genetický algoritmus možno použiť v počítačových hrách na vytvorenie umelej inteligencie (počítač hrá proti vám). To umožňuje realistickejší zážitok z hry; ak ľudský hráč dokáže nájsť postupnosť krokov, ktoré vždy vedú k úspechu, aj keď sa opakujú v rôznych hrách, nemôže zostať žiadna výzva. Naopak, ak sa technika učenia, napríklad genetický algoritmus pre stratéga, dokáže vyhnúť opakovaniu minulých chýb, hra bude mať väčšiu hrateľnosť.

Genetické algoritmy vyžadujú tieto časti:

• Metóda reprezentácie úlohy z hľadiska riešenia (napr. smerovanie vojakov pri útoku v strategickej hre)
• Fitness alebo hodnotiaca funkcia na určenie kvality inštancie (napr. meranie poškodenia spôsobeného súperovi pri takomto útoku).

Funkcia fitness akceptuje zmutovanú inštanciu entity a meria jej kvalitu. Táto funkcia je prispôsobená problémovej doméne. V mnohých prípadoch, najmä tých, ktoré zahŕňajú optimalizáciu kódu, môže byť fitness funkcia jednoducho funkciou časovania systému. Po definovaní genetickej reprezentácie a fitness funkcie genetický algoritmus inštanciuje počiatočných kandidátov, ako bolo opísané predtým, a potom ich zlepšuje opakovaným použitím operátorov mutácie, kríženia, inverzie a výberu (definovaných podľa problémovej oblasti).

Obmedzenia

Použitie genetického algoritmu má v porovnaní s alternatívnymi optimalizačnými algoritmami určité obmedzenia:

• Opakované vyhodnocovanie fitness funkcie pre komplexné problémy je často najobmedzenejším segmentom umelých evolučných algoritmov. Nájdenie optimálneho riešenia zložitých problémov si často vyžaduje veľmi nákladné vyhodnotenia funkcie fitness. V reálnych problémoch, ako sú napríklad problémy štrukturálnej optimalizácie, môže jedno vyhodnotenie funkcie vyžadovať niekoľko hodín až niekoľko dní kompletnej simulácie. Typické optimalizačné metódy si s takýmito typmi problémov nevedia poradiť. Často je potrebné použiť aproximáciu, pretože výpočet presného riešenia trvá príliš dlho. Genetické algoritmy niekedy kombinujú rôzne aproximačné modely na riešenie zložitých reálnych problémov.
• Genetické algoritmy sa nedajú dobre škálovať. To znamená, že ak je počet prvkov, ktoré sú vystavené mutácii, veľký, často dochádza k exponenciálnemu nárastu veľkosti prehľadávacieho priestoru. To mimoriadne sťažuje použitie tejto techniky na problémy, ako je návrh motora, domu alebo lietadla. Aby sa genetické algoritmy mohli použiť pri takýchto problémoch, musia sa rozložiť na čo najjednoduchšiu reprezentáciu. Z tohto dôvodu sa stretávame s evolučnými algoritmami, ktoré kódujú návrhy lopatiek ventilátorov namiesto motorov, tvary budov namiesto podrobných stavebných plánov a krídla lietadiel namiesto návrhov celých lietadiel. Druhým problémom zložitosti je otázka, ako ochrániť časti, ktoré sa vyvinuli tak, aby reprezentovali dobré riešenia, pred ďalšou deštruktívnou mutáciou, najmä keď si ich hodnotenie fitness vyžaduje, aby sa dobre kombinovali s inými časťami.
• "Lepšie" riešenie je len v porovnaní s inými riešeniami. V dôsledku toho nie je kritérium zastavenia v každom probléme jednoznačné.
• V mnohých problémoch majú genetické algoritmy tendenciu konvergovať skôr k lokálnemu optimu alebo dokonca k ľubovoľným bodom než ku globálnemu optimu problému. To znamená, že algoritmus "nevie" obetovať krátkodobú vhodnosť na získanie dlhodobejšej vhodnosti. Pravdepodobnosť, že k tomu dôjde, závisí od tvaru fitness funkcie: niektoré problémy uľahčujú nájdenie globálneho optima, iné môžu uľahčovať nájdenie lokálneho optima. Tento problém sa dá zmierniť použitím inej fitness funkcie, zvýšením miery mutácie alebo použitím selekčných techník, ktoré udržiavajú rôznorodú populáciu riešení. Bežnou technikou na zachovanie rozmanitosti je použitie "trestu za výklenok": každej skupine jedincov s dostatočnou podobnosťou (polomer výklenku) sa pridá trest, ktorý zníži zastúpenie tejto skupiny v nasledujúcich generáciách, čo umožní ponechať v populácii iných (menej podobných) jedincov. Tento trik však nemusí byť účinný v závislosti od krajiny problému. Ďalšou možnou technikou by bolo jednoducho nahradiť časť populácie náhodne vygenerovanými jedincami, keď je väčšina populácie príliš podobná jeden druhému. Rozmanitosť je v genetických algoritmoch (a genetickom programovaní) dôležitá, pretože kríženie homogénnej populácie neprináša nové riešenia. V evolučných stratégiách a evolučnom programovaní nie je rozmanitosť nevyhnutná, pretože sa viac spolieha na mutácie.
• Práca s dynamickými súbormi údajov je náročná, pretože genómy začínajú skoro konvergovať k riešeniam, ktoré už nemusia byť platné pre neskoršie údaje. Bolo navrhnutých niekoľko metód, ako to napraviť tým, že sa nejakým spôsobom zvýši genetická diverzita a zabráni sa skorému zbližovaniu, a to buď zvýšením pravdepodobnosti mutácie pri poklese kvality riešenia (tzv. spustená hypermutácia), alebo občasným zavedením úplne nových, náhodne generovaných prvkov do genofondu (tzv. náhodní prisťahovalci). Aj v tomto prípade možno evolučné stratégie a evolučné programovanie realizovať pomocou takzvanej "čiarkovej stratégie", pri ktorej sa rodičia neudržiavajú a noví rodičia sa vyberajú len z potomkov. To môže byť efektívnejšie pri dynamických problémoch.
• Genetické algoritmy nedokážu efektívne riešiť problémy, v ktorých jedinou mierou vhodnosti je jediná správna/nesprávna miera (ako sú rozhodovacie problémy), pretože neexistuje spôsob, ako konvergovať k riešeniu (neexistuje kopec, na ktorý by sa dalo vystúpiť). V týchto prípadoch môže náhodné vyhľadávanie nájsť riešenie rovnako rýchlo ako GA. Ak však situácia umožňuje opakovanie pokusu o úspech/neúspech, ktorý (možno) poskytuje rôzne výsledky, potom pomer úspechov a neúspechov poskytuje vhodnú mieru vhodnosti.
• Pre špecifické optimalizačné problémy a prípady problémov môžu byť iné optimalizačné algoritmy z hľadiska rýchlosti konvergencie efektívnejšie ako genetické algoritmy. Medzi alternatívne a doplnkové algoritmy patria evolučné stratégie, evolučné programovanie, simulované žíhanie, Gaussova adaptácia, lezenie po kopcoch a inteligencia roja (napríklad: optimalizácia mravčích kolónií, optimalizácia roja častíc) a metódy založené na celočíselnom lineárnom programovaní. Vhodnosť genetických algoritmov závisí od množstva znalostí o probléme; dobre známe problémy majú často lepšie, špecializovanejšie prístupy.

História

V roku 1950 Alan Turing navrhol "učiaci sa stroj", ktorý by fungoval paralelne s princípmi evolúcie. Počítačová simulácia evolúcie sa začala už v roku 1954 prácou Nilsa Aalla Barricelliho, ktorý používal počítač v Inštitúte pre pokročilé štúdie v Princetone v New Jersey. Jeho publikácia z roku 1954 sa nestretla s veľkým ohlasom. Od roku 1957 austrálsky kvantitatívny genetik Alex Fraser publikoval sériu prác o simulácii umelého výberu organizmov s viacerými lokusmi kontrolujúcimi merateľný znak. Od týchto začiatkov sa počítačová simulácia evolúcie biológmi stala bežnejšou začiatkom 60. rokov a metódy boli opísané v knihách Frasera a Burnella (1970) a Crosbyho (1973). Fraserove simulácie obsahovali všetky podstatné prvky moderných genetických algoritmov. Okrem toho Hans-Joachim Bremermann uverejnil v 60. rokoch 20. storočia sériu prác, v ktorých tiež prijal populáciu riešenia optimalizačných problémov, ktorá prechádza rekombináciou, mutáciou a selekciou. Bremermannov výskum obsahoval aj prvky moderných genetických algoritmov. K ďalším významným priekopníkom z raného obdobia patria Richard Friedberg, George Friedman a Michael Conrad. Mnohé rané práce sú preložené v publikácii Fogel (1998).

Hoci Barricelli v práci, o ktorej informoval v roku 1963, simuloval evolúciu schopnosti hrať jednoduchú hru, umelá evolúcia sa stala všeobecne uznávanou optimalizačnou metódou vďaka práci Inga Rechenberga a Hansa-Paula Schwefela v 60. a začiatkom 70. rokov 20. storočia - Rechenbergova skupina dokázala pomocou evolučných stratégií riešiť zložité inžinierske problémy. Ďalším prístupom bola technika evolučného programovania Lawrenca J. Fogela, ktorá bola navrhnutá na generovanie umelej inteligencie. Evolučné programovanie pôvodne používalo na predpovedanie prostredia stroje s konečnými stavmi a na optimalizáciu predpovedných logík využívalo variácie a výber. Genetické algoritmy sa stali populárne najmä vďaka práci Johna Hollanda na začiatku 70. rokov 20. storočia a najmä jeho knihe Adaptation in Natural and Artificial Systems (1975). Jeho práca vznikla na základe štúdií bunkových automatov, ktoré Holland a jeho študenti uskutočnili na Michiganskej univerzite. Holland zaviedol formalizovaný rámec na predpovedanie kvality nasledujúcej generácie, známy ako Hollandova veta o schéme. Výskum v oblasti GA zostal prevažne teoretický až do polovice 80. rokov, keď sa v Pittsburghu v Pensylvánii konala prvá medzinárodná konferencia o genetických algoritmoch.