Genetický algoritmus

Co je to

Přirozenou evoluci lze modelovat jako hru, v níž odměnou pro organismus, který hraje dobrou hru života, je předávání genetického materiálu jeho následovníkům a jeho další přežití.^[2] V přirozené evoluci závisí to, jak dobře si jedinec vede, na tom, s kým spolupracuje a s kým soupeří, a také na prostředí. Genetické algoritmy jsou simulací přirozeného výběru na populaci kandidátů na řešení optimalizačního problému (chromozomů, jedinců, tvorů nebo fenotypů).

Kandidáti jsou hodnoceni a kříženi ve snaze vytvořit dobrá řešení. Taková řešení mohou zabrat mnoho času a pro člověka nejsou zřejmá. Evoluční fáze je zahájena populací náhodně vygenerovaných bytostí. V každé generaci se vyhodnocuje fitness každého jedince v populaci. Někteří z nich jsou náhodně vybráni z aktuální populace (na základě jejich fitness) a upraveni (rekombinováni a případně náhodně zmutováni), aby vytvořili novou populaci. Cyklus se opakuje s touto novou populací. Algoritmus končí buď po uplynutí stanoveného počtu generací, nebo po dosažení dobré úrovně fitness populace. Pokud algoritmus skončil z důvodu dosažení maximálního počtu generací, nemusí to nutně znamenat, že bylo dosaženo dobré úrovně fitness.

Programování na počítači

Pseudokód je následující:

1. Inicializace: Vytvoří se několik možných řešení; velmi často budou mít náhodné hodnoty.
2. Hodnocení: Skóre je číslo, které udává, jak dobře toto řešení řeší problém.
3. Následující kroky se provádějí, dokud není splněn požadavek na zastavení:
1. Výběr: Výběr řešení/jednotlivců pro další iteraci
2. Rekombinace: Zkombinujte vybraná řešení
3. Mutace: Náhodně změňte nově vytvořená řešení
4. Hodnocení: Použijte fitness funkci, viz krok 2.
5. Pokud není splněn požadavek na zastavení, začněte znovu krokem výběru.

Příklad

Výše uvedený popis je abstraktní. Pomůže konkrétní příklad.

Aplikace

Obecně

Genetické algoritmy jsou vhodné pro řešení problémů, které zahrnují sestavování rozvrhů a plánování. Byly použity také ve strojírenství. Často se používají k řešení globálních optimalizačních problémů.

Obecně platí, že genetické algoritmy mohou být užitečné v problémových oblastech, které mají složité fitness prostředí, protože míchání je navrženo tak, aby posunulo populaci pryč od lokálních optim, ve kterých by tradiční algoritmus hill climbing mohl uvíznout. Běžně používané operátory křížení nemohou změnit žádnou jednotnou populaci. Samotná mutace může zajistit ergodicitu celého procesu genetického algoritmu (chápaného jako Markovův řetězec).

Příklady problémů řešených pomocí genetických algoritmů: zrcadla navržená tak, aby směřovala sluneční světlo do slunečního kolektoru, antény navržené k zachycení rádiových signálů ve vesmíru, metody chůze pro počítačové postavy, optimální návrh aerodynamických těles ve složitých proudových polích.

Skiena ve své Příručce pro návrh algoritmů nedoporučuje používat genetické algoritmy pro jakékoli úlohy: "Je zcela nepřirozené modelovat aplikace pomocí genetických operátorů, jako jsou mutace a křížení, na bitových řetězcích. Pseudobiologie přidává další úroveň složitosti mezi vás a váš problém. Za druhé, genetické algoritmy potřebují u netriviálních problémů velmi dlouhou dobu. [...] Analogie s evolucí - kde významný pokrok vyžaduje [sic] miliony let - může být zcela na místě. [...] Nikdy jsem se nesetkal s problémem, u kterého by mi genetické algoritmy připadaly jako správný způsob, jak na něj zaútočit. Dále jsem nikdy neviděl žádné výsledky výpočtů oznámené pomocí genetických algoritmů, které by na mě příznivě zapůsobily. Pro potřeby heuristického vyhledávání voodoo se držte simulovaného žíhání."

Deskové hry

Deskové hry jsou velmi důležitou součástí oblasti genetických algoritmů aplikovaných na problémy teorie her. Velká část raných prací v oblasti výpočetní inteligence a her byla zaměřena na klasické deskové hry, jako je například tic-tac-toe,^[3] šachy a dáma.^[4] Deskové hry dnes může počítač ve většině případů hrát na vyšší úrovni než nejlepší člověk, a to i při použití technik slepého vyčerpávajícího vyhledávání. Výjimkou z tohoto trendu je hra Go, která dosud odolávala útokům strojů. Nejlepší počítačoví hráči Go nyní hrají na úrovni dobrého začátečníka.^[5][6] Strategie hry Go údajně do značné míry závisí na rozpoznávání vzorů, a ne pouze na logické analýze jako v šachu a jiných hrách, které jsou více závislé na figurách. Obrovský efektivní faktor větvení potřebný k nalezení kvalitních řešení silně omezuje pohled dopředu, který lze použít v rámci hledání posloupnosti tahů.

Počítačové hry

Genetický algoritmus lze použít v počítačových hrách k vytvoření umělé inteligence (počítač hraje proti vám). To umožňuje realističtější herní zážitek; pokud lidský hráč dokáže najít posloupnost kroků, které vždy vedou k úspěchu, i když se opakují v různých hrách, nemůže už být žádná výzva. Naopak pokud se technika učení, jako je genetický algoritmus pro stratéga, dokáže vyhnout opakování minulých chyb, hra bude mít větší hratelnost.

Genetické algoritmy vyžadují následující části:

• Metoda reprezentace úkolu z hlediska řešení (např. směrování vojáků při útoku ve strategické hře).
• fitness nebo hodnotící funkce pro určení kvality instance (např. měření poškození způsobeného protivníkovi při takovém útoku).

Funkce fitness přijímá zmutovanou instanci entity a měří její kvalitu. Tato funkce je přizpůsobena problémové doméně. V mnoha případech, zejména těch, které se týkají optimalizace kódu, může být fitness funkce jednoduše funkcí časování systému. Jakmile jsou definovány genetická reprezentace a fitness funkce, genetický algoritmus vytvoří počáteční kandidáty, jak bylo popsáno dříve, a poté je zlepšuje opakovaným použitím operátorů mutace, křížení, inverze a výběru (definovaných podle problémové domény).

Omezení

Použití genetického algoritmu má ve srovnání s alternativními optimalizačními algoritmy určitá omezení:

• Opakované vyhodnocování fitness funkcí pro složité problémy je často nejvíce omezujícím segmentem umělých evolučních algoritmů. Nalezení optimálního řešení složitých problémů často vyžaduje velmi nákladné vyhodnocení funkce fitness. V reálných problémech, jako jsou problémy strukturální optimalizace, může jedno vyhodnocení funkce vyžadovat několik hodin až několik dní kompletní simulace. Typické optimalizační metody si s takovými typy problémů neporadí. Často je nutné použít aproximaci, protože výpočet přesného řešení trvá příliš dlouho. Genetické algoritmy někdy kombinují různé aproximační modely pro řešení složitých reálných problémů.
• Genetické algoritmy nelze dobře škálovat. To znamená, že pokud je počet prvků, které jsou vystaveny mutaci, velký, dochází často k exponenciálnímu nárůstu velikosti prohledávaného prostoru. To velmi ztěžuje použití této techniky na problémy, jako je návrh motoru, domu nebo letadla. Aby bylo možné genetické algoritmy u takových problémů použít, je třeba je rozložit na co nejjednodušší reprezentaci. Z tohoto důvodu se setkáváme s evolučními algoritmy, které kódují návrhy lopatek ventilátorů místo motorů, tvary budov místo podrobných stavebních plánů a křídla letadel místo návrhů celých letadel. Druhým problémem složitosti je otázka, jak ochránit části, které se vyvinuly tak, aby reprezentovaly dobrá řešení, před další destruktivní mutací, zejména pokud jejich hodnocení fitness vyžaduje, aby se dobře kombinovaly s jinými částmi.
• "Lepší" řešení je pouze ve srovnání s jinými řešeními. V důsledku toho není kritérium zastavení v každém problému jednoznačné.
• V mnoha problémech mají genetické algoritmy tendenci konvergovat spíše k lokálnímu optimu nebo dokonce k libovolným bodům než ke globálnímu optimu problému. To znamená, že algoritmus "neumí" obětovat krátkodobou vhodnost pro získání dlouhodobé vhodnosti. Pravděpodobnost, že k tomu dojde, závisí na tvaru fitness funkce: některé problémy usnadňují nalezení globálního optima, u jiných může být pro funkci snazší najít lokální optima. Tento problém lze zmírnit použitím jiné fitness funkce, zvýšením míry mutace nebo použitím selekčních technik, které udržují rozmanitou populaci řešení. Běžnou technikou pro udržení rozmanitosti je použití "trestu za niku": jakékoli skupině jedinců s dostatečnou podobností (poloměrem niky) se přidá trest, který sníží zastoupení této skupiny v následujících generacích, což umožní ponechat v populaci jiné (méně podobné) jedince. Tento trik však nemusí být účinný v závislosti na krajině problému. Další možnou technikou by bylo jednoduše nahradit část populace náhodně vygenerovanými jedinci, když je si většina populace příliš podobná. Diverzita je v genetických algoritmech (a genetickém programování) důležitá, protože křížením homogenní populace se nezískávají nová řešení. V evolučních strategiích a evolučním programování není diverzita podstatná, protože se více spoléhá na mutaci.
• Práce s dynamickými soubory dat je obtížná, protože genomy začínají brzy konvergovat k řešením, která již nemusí být platná pro pozdější data. Bylo navrženo několik metod, jak to napravit tím, že se nějakým způsobem zvýší genetická rozmanitost a zabrání se brzké konvergenci, a to buď zvýšením pravděpodobnosti mutace při poklesu kvality řešení (tzv. spouštěná hypermutace), nebo občasným zavedením zcela nových, náhodně generovaných prvků do genofondu (tzv. náhodní přistěhovalci). Evoluční strategie a evoluční programování lze opět realizovat pomocí tzv. čárkové strategie, při níž se rodiče neudržují a noví rodiče se vybírají pouze z potomků. To může být efektivnější u dynamických problémů.
• Genetické algoritmy nemohou efektivně řešit problémy, u nichž je jediným měřítkem vhodnosti jediné správné/špatné měřítko (jako jsou rozhodovací problémy), protože neexistuje způsob, jak konvergovat k řešení (neexistuje žádný kopec, na který by bylo třeba vylézt). V těchto případech může náhodné vyhledávání najít řešení stejně rychle jako GA. Pokud však situace umožňuje opakování pokusu o úspěch/neúspěch, který dává (možná) různé výsledky, pak poměr úspěchů a neúspěchů poskytuje vhodnou míru vhodnosti.
• Pro konkrétní optimalizační problémy a případy problémů mohou být jiné optimalizační algoritmy z hlediska rychlosti konvergence efektivnější než genetické algoritmy. Mezi alternativní a doplňkové algoritmy patří evoluční strategie, evoluční programování, simulované žíhání, Gaussova adaptace, lezení do kopce a inteligence roje (např.: optimalizace mravenčí kolonie, optimalizace roje částic) a metody založené na celočíselném lineárním programování. Vhodnost genetických algoritmů závisí na množství znalostí o problému; dobře známé problémy mají často lepší, specializovanější přístupy.

Historie

V roce 1950 Alan Turing navrhl "učící se stroj", který by fungoval paralelně s principy evoluce. Počítačová simulace evoluce začala již v roce 1954 prací Nilse Aalla Barricelliho, který používal počítač v Institutu pro pokročilá studia v Princetonu ve státě New Jersey. Jeho publikace z roku 1954 se nesetkala s velkým ohlasem. Od roku 1957 publikoval australský kvantitativní genetik Alex Fraser řadu prací o simulaci umělého výběru organismů s více lokusy řídícími měřitelný znak. Od těchto počátků se počítačová simulace evoluce prováděná biology rozšířila počátkem 60. let a metody byly popsány v knihách Frasera a Burnella (1970) a Crosbyho (1973). Fraserovy simulace obsahovaly všechny podstatné prvky moderních genetických algoritmů. Kromě toho Hans-Joachim Bremermann publikoval v 60. letech 20. století řadu prací, které rovněž přejímaly populaci řešení optimalizačních problémů, procházející rekombinací, mutací a selekcí. Bremermannův výzkum rovněž zahrnoval prvky moderních genetických algoritmů. K dalším pozoruhodným průkopníkům z počátku patří Richard Friedberg, George Friedman a Michael Conrad. Mnoho raných prací přetiskuje Fogel (1998).

Ačkoli Barricelli ve své práci z roku 1963 simuloval vývoj schopnosti hrát jednoduchou hru, umělá evoluce se stala široce uznávanou optimalizační metodou díky práci Ingo Rechenberga a Hanse-Paula Schwefela v 60. a počátkem 70. let - Rechenbergova skupina dokázala pomocí evolučních strategií řešit složité inženýrské problémy. Dalším přístupem byla technika evolučního programování Lawrence J. Fogela, která byla navržena pro generování umělé inteligence. Evoluční programování původně používalo konečné stavové automaty pro predikci prostředí a k optimalizaci predikčních logik využívalo variaci a selekci. Genetické algoritmy se staly populární zejména díky práci Johna Hollanda na počátku 70. let 20. století, a zejména jeho knize Adaptation in Natural and Artificial Systems (1975). Jeho práce vycházela ze studií buněčných automatů, které Holland a jeho studenti prováděli na Michiganské univerzitě. Holland zavedl formalizovaný rámec pro předpovídání kvality příští generace, známý jako Hollandův teorém schématu. Výzkum v oblasti GA zůstal převážně teoretický až do poloviny 80. let, kdy se v Pittsburghu v Pensylvánii konala první mezinárodní konference o genetických algoritmech.