{{SpecsPsy}
Genetický algoritmus (GA) je vyhledávací technika používaná v počítačové vědě k nalezení přibližných řešení optimalizačních a vyhledávacích problémů. Konkrétně spadá do kategorie lokálních vyhledávacích technik, a je tedy obecně neúplným vyhledáváním. Genetické algoritmy jsou zvláštní třídou evolučních algoritmů, které používají techniky inspirované evoluční biologií, jako je dědičnost, mutace, výběr a křížení (také nazývané rekombinace).
Genetické algoritmy jsou typicky implementovány jako počítačová simulace, ve které se populace abstraktních reprezentací (tzv. chromozomů) kandidátních řešení (tzv. jednotlivců) k optimalizačnímu problému vyvíjí směrem k lepším řešením. Tradičně jsou řešení reprezentována binárně jako řetězce 0s a 1s, ale různá kódování jsou také možná. Vývoj začíná u populace zcela náhodných jedinců a probíhá v generacích. V každé generaci je hodnocena kondice celé populace, více jedinců je stochasticky vybráno ze současné populace (na základě jejich kondice) a modifikováno (zmutováno nebo rekombinováno) k vytvoření nové populace. Nová populace je pak použita v další iteraci algoritmu.
Typický genetický algoritmus vyžaduje, aby byly definovány dvě věci: (1) genetická reprezentace řešení, (2) fitness funkce pro jejich vyhodnocení.
Standardní reprezentace je pole bitů. Pole jiných typů a struktur mohou být použity v podstatě stejným způsobem. Hlavní vlastností, která činí tyto genetické reprezentace výhodnými, je to, že jejich části jsou snadno zarovnány díky jejich pevné velikosti, což usnadňuje jednoduchou operaci křížení. Byly použity také reprezentace různých délek, ale implementace křížení je v tomto případě složitější. Stromové reprezentace jsou prozkoumány v Genetickém programování a volné reprezentace jsou prozkoumány v HBGA.
Funkce fitness je definována přes genetickou reprezentaci a měří kvalitu reprezentovaného řešení. Funkce fitness je vždy závislá na problému. Například v problému s batohem chceme maximalizovat celkovou hodnotu objektů, které můžeme dát do batohu o nějaké pevné kapacitě. Reprezentace řešení může být pole bitů, kde každý bit představuje jiný objekt a hodnota bitu (0 nebo 1) reprezentuje, zda objekt je nebo není v batohu. Ne každá taková reprezentace je platná, protože velikost objektů může překročit kapacitu batohu. Fitness řešení je součtem hodnot všech objektů v batohu, pokud je reprezentace platná, nebo 0 jinak. V některých problémech je těžké nebo dokonce nemožné definovat výraz fitness; v těchto případech se používají interaktivní genetické algoritmy.
Jakmile máme definovanou genetickou reprezentaci a fitness funkci, GA přistoupí k inicializaci populace řešení náhodně, pak ji vylepší opakovanou aplikací mutací, crossoverů a selekčních operátorů.
Zpočátku je náhodně generováno mnoho jednotlivých řešení, které tvoří počáteční populaci. Velikost populace závisí na povaze problému, ale obvykle obsahuje několik stovek nebo tisíců možných řešení. Tradičně je populace generována náhodně a pokrývá celou škálu možných řešení (vyhledávací prostor). Občas mohou být řešení „nasazena“ v oblastech, kde se pravděpodobně najdou optimální řešení.
Během každé následující epochy je vybrán určitý podíl stávající populace, která bude plodit novou generaci. Jednotlivá řešení jsou vybírána procesem založeným na kondici, kde je obvykle pravděpodobnější, že budou vybrána vhodnější řešení (měřeno funkcí fitness). Určité metody výběru hodnotí kondici každého řešení a přednostně vybírají nejlepší řešení. Jiné metody hodnotí pouze náhodný vzorek populace, protože tento proces může být velmi časově náročný.
Většina funkcí je stochastická a navržena tak, aby byla vybrána malá část méně vhodných řešení. To pomáhá udržet rozmanitost populace velkou a zabraňuje předčasné konvergenci ke špatným řešením. Mezi oblíbené a dobře studované metody výběru patří výběr ruletového kola a výběr turnaje.
Dalším krokem je generování druhé generace řešení z těch vybraných prostřednictvím genetických operátorů: crossover (také nazývaný rekombinace) a/nebo mutace.
Pro každé nové řešení, které má být vytvořeno, je vybrána dvojice „rodičovských“ řešení pro chov z dříve vybraného fondu. Vytvořením „dětského“ řešení pomocí výše uvedených metod křížení a mutace je vytvořeno nové řešení, které obvykle sdílí mnoho vlastností svých „rodičů“. Noví rodiče jsou vybráni pro každé dítě a proces pokračuje, dokud není vytvořena nová populace řešení vhodné velikosti.
Výsledkem těchto procesů je v konečném důsledku další generace populace chromozomů, která je odlišná od původní generace. Obecně se tímto postupem pro populaci zvýší průměrná kondice, protože pro chov jsou vybrány pouze ty nejlepší organismy z první generace, spolu s malým podílem méně vhodných roztoků, a to z důvodů již zmíněných výše.
Tento generační proces se opakuje, dokud není dosaženo podmínky ukončení. Běžné podmínky ukončení jsou
O generování řešení pomocí genetického algoritmu existuje několik obecných postřehů:
Nejjednodušší algoritmus představuje každý chromozom jako bitový řetězec. Typicky mohou být číselné parametry reprezentovány celými čísly, i když je možné použít reprezentace s plovoucí desetinnou čárkou. Základní algoritmus provádí křížení a mutaci na úrovni bitů. Jiné varianty zacházejí s chromozomem jako se seznamem čísel, které jsou indexy do instrukční tabulky, uzlů v propojeném seznamu, hashů, objektů nebo jiné představitelné datové struktury. Křížení a mutace jsou prováděny tak, aby respektovaly hranice datových prvků. Pro většinu datových typů lze navrhnout operátory specifických variací. Různé typy chromozomálních dat fungují lépe nebo hůře pro různé specifické problémové domény.
Při použití bitových řetězců reprezentace celých čísel se často používá Grayovo kódování. Tímto způsobem mohou být malé změny v integeru snadno provedeny pomocí mutací nebo crossoverů. Bylo zjištěno, že to pomáhá zabránit předčasné konvergenci u tzv. Hammingových stěn, ve kterých se musí vyskytnout příliš mnoho souběžných mutací (nebo crossoverových událostí), aby se chromozom změnil na lepší řešení.
Jiné přístupy zahrnují použití polí reálných čísel místo bitových řetězců pro reprezentaci chromozomů. Teoreticky, čím menší abeceda, tím lepší výkon, ale paradoxně, dobré výsledky byly získány použitím reálných chromozomů.
Mírnou, ale velmi úspěšnou variantou obecného procesu výstavby nové populace je umožnit některým lepším organismům ze současné generace přenést se do další, nezměněné. Tato strategie je známá jako elitářský výběr.
Paralelní implementace genetických algoritmů mají dvě příchutě. Hrubě zrnité paralelní genetické algoritmy předpokládají populaci na každém z počítačových uzlů a migraci jedinců mezi uzly. Jemně zrnité paralelní genetické algoritmy předpokládají jedince na každém procesorovém uzlu, který jedná se sousedními jedinci pro výběr a reprodukci.
Jiné varianty, jako genetické algoritmy pro online optimalizační problémy, zavádějí do fitness funkce časovou závislost nebo šum.
Problémy, které se zdají být zvláště vhodné pro řešení pomocí genetických algoritmů, zahrnují problémy s časovým rozvrhem a plánováním a mnoho programovacích softwarových balíčků je založeno na GA. GA byly také aplikovány na inženýrství. Genetické algoritmy jsou často používány jako přístup k řešení globálních optimalizačních problémů.
Jako obecné pravidlo palec genetické algoritmy by mohly být užitečné v problémových doménách, které mají komplexní fitness krajiny, protože rekombinace je navržen tak, aby přesunout populaci od místní optima, že tradiční horolezecký algoritmus by mohl uvíznout.
Genetické algoritmy vznikly ze studií buněčných automatů, které vedl John Holland a jeho kolegové z Michiganské univerzity. Výzkum v oblasti GA zůstal z velké části teoretický až do poloviny 80. let, kdy se na Illinoiské univerzitě konala první mezinárodní konference o genetických algoritmech. S rostoucím zájmem akademické obce umožnil dramatický nárůst desktopového výpočetního výkonu praktické využití nové techniky. V roce 1989 napsal spisovatel John Markoff z The New York Times o Evolveru, prvním komerčně dostupném desktopovém genetickém algoritmu. V široké škále oborů se začaly objevovat vlastní počítačové aplikace a tyto algoritmy dnes používá většina společností z žebříčku Fortune 500 k řešení obtížných plánovacích, datových spojů, problémů se sledováním trendů a rozpočtováním a prakticky jakéhokoli jiného typu kombinatorické optimalizace.
[Goldberg, 1989, strana 41], mluví o binárních bitových řetězcových genetických algoritmech, říká:
Poznámka [Goldberg, 1989] naznačuje, že stavební bloky jsou vysoce fit schémata pouze s několika definovanými bity (nízký řád), a že jsou blízko sebe (krátký).