Genetický algoritmus

Genetický algoritmus (GA) je heuristická optimalizační metoda, řadící se mezi tzv. evoluční algoritmy, inspirovaná přirozeným výběrem živočišných druhů, tj. evoluční biologií, užívaná k řešení složitých optimalizačních úloh, které nelze řešit konvenčními metodami jako např. metoda Lagrangeových multiplikátorů, lineární programování, kvadratické programování atd.

Evoluční algoritmy 
Evoluční algoritmy se užívají k nalezení dostatečně kvalitního řešení optimalizačních úloh v dostatečně krátkém čase. Mezi evoluční algoritmy inspirované přírodou se zahrnuje celé spektrum optimalizačních heuristických technik, např. genetické algoritmy či simulované žíhání. Heuristiky můžeme popsat jako zkratkovitý postup prohledávání prostoru řešení bez záruky správného výsledku, nicméně jsou zbaveny celé řady neduhů konvenčních optimalizačních metod, jako např. požadavek spojitosti či diferencovatelnosti objektivní resp. vazební funkce, respektování omezujících podmínek, uvíznutí v mělkém lokálním minimu atd. Na druhou stranu však je při jejich aplikaci zapotřebí nastavení jistých volných parametrů, které je nutné „naladit“ v závislosti na konkrétním optimalizačním problému.

Genetický algoritmus

Pojmy 
 Chromozom – řetězec nezávisle proměnných optimalizované funkce, neboli řešení optimalizační úlohy (stavební plán jedince)

 Fitness funkce – optimalizovaná funkce (ohodnocení schopnosti jedince přežít v okolním prostředí)

 Generace – soubor řetězců nezávisle proměnných optimalizované funkce (jedinců) "stejného věku"

 Reprodukce – tvorba nové generace jedinců pomocí křížení a mutace jedinců staré generace

 Křížení – výměna podřetězců nezávisle proměnných optimalizované funkce mezi dvěma řetězci (výměna genetické informace)

 Mutace – přepsání podřetězce nezávisle proměnných optimalizované funkce (poškození genetické informace)

Princip 
Princip genetického algoritmu je postupná tvorba na sebe navazujících generací různých řešení optimalizační úlohy vždy o stejném počtu jedinců. Jak populace probíhá evolucí (střídání generací), řešení se zlepšují. Tradičně je řešení reprezentováno řetězcem celých nebo binárních čísel , nicméně používají se i jiné reprezentace (pole, matice, strom, …). První generace je na začátku algoritmu složena z náhodně vygenerovaných jedinců. Během přechodu od předchozí generace (rodičů) k následující generaci (potomků) jsou jedinci předchozí generace pomocí křížení a mutací stochasticky reprodukováni v modifikované jedince následující generace. Tento postup se iterativně opakuje. Algoritmus během iterací konverguje k homogenizaci populace ve smyslu schopnosti přežití jejích jedinců, jedinci se již optimálně přizpůsobili svému prostředí a algoritmus lze zastavit.

Algoritmus 
Dnes již existuje celá škála různých variant genetického algoritmu. Proto zde nelze podat vyčerpávající popis všech variant. Ani následující schéma klasického algoritmu tohoto druhu nelze vztáhnout na všechny aplikace, ale může sloužit pochopení principu metody.

Algoritmus lze slovy zapsat takto:

 Inicializace algoritmu – tvorba první generace složené z náhodně vygenerovaných jedinců (např. 100 až 1000 jedinců)
 Začátek iteračního cyklu – jedince z aktuální generace značíme po řadě jako potenciální rodiče (ano–ne) s pravděpodobností závislé na hodnotě fitness funkce (viz pozn.)
 Reprodukce křížením a mutacemi – z náhodně vybíraných dvou potenciálních rodičů aktuální generace generujeme jejich dva potomky do nové generace do té doby, než nová generace dosáhne stejného počtu jedinců jako ta aktuální
 Konec iteračního cyklu – pokud není splněna zastavovací podmínka, jdi na bod 2, jinak na bod 5
 Výsledek algoritmu – jedinec poslední generace s nejvyšší hodnotou fitness funkce reprezentuje optimální řešení

pozn.:
 kde  je pravděpodobnost označení jedince  jako rodiče a  hodnota fitness funkce jedince .

Příklad algoritmu

Inicializace 
Mějme první generaci tvořenou množinou náhodně vygenerovaných řetězců (bajtů) jako množinu čtyř individuí reprezentovaných chromozomem délky 8.

 (1,0,1,0,1,1,0,0)
 (0,1,1,1,1,1,0,1)
 (0,0,0,1,0,0,0,1)
 (1,1,0,0,1,1,0,0)

Začátek 
Definice fitness funkce je dána konkrétním problémem, protože cílem je najít takové individuum nebo individua, která mají z hlediska příslušného problému optimální vlastnosti. Předpokládejme, že v našem příkladu je fitness funkce dána počtem jedničkových bitů v chromozomu:

Výběr rodičů 
Výběr rodičů by měl respektovat pravidla přirozeného výběru dle Darwinovy teorie o původu druhů. To znamená, že zdatnější jedinci mají větší šanci se prosadit v konkurenci jiných, lépe překonávat překážky a žít déle. Jedinci s vyšším ohodnocením mají větší pravděpodobnost výběru partnera. Výběr se dá přirovnat k ruletě, kde je obvod rulety rozdělen do oblastí různých velikostí podle hodnocení jedince. Náhodné číslo má pak vyšší pravděpodobnost, že dopadne zrovna do části, která patří jedinci s vyšší fitness, nežli do oblasti jedince s nižší fitness, protože jeho oblast na obvodu rulety je menší.

Pravděpodobnost výběru -tého partnera dána je vztahem . Byla vygenerována čtyři pseudonáhodná čísla  a tímto vybrána čtyři individua pro reprodukci.

Reprodukce

Křížení 
Existuje řada technik křížení, ale vždy dochází k výměně částí chromozomů. V tomto příkladu použijeme nejjednodušší jednobodové křížení. Náhodně zvolíme místo v chromozomu, od kterého počínaje vyměníme zbylé části chromozomu mezi oběma rodiči. Tím vzniknou dva noví jedinci, z nichž každý má část genetické výbavy po obou rodičích. V některých případech může být užitečné zachovat kopie rodičů pro příští generace beze změny.

Mutace 
Na výsledné potomstvo se aplikuje ještě mutace. Ta s malou pravděpodobností jednoduchým způsobem náhodně mění hodnotu jednotlivých bitů. V náhodně vybraných chromozomech tedy změníme hodnotu bitu:

 (0,1,0,0,1,1,0,0)  ⇒  (0,1,0,1,1,1,0,0)	
 (1,1,1,1,1,1,0,1)  ⇒  (1,1,1,1,1,1,0,1)
 (0,0,0,1,1,1,0,1)  ⇒  (0,0,0,1,1,1,0,1)
 (0,1,1,1,0,0,0,1)  ⇒  (0,0,0,1,1,1,0,0)

Zatímco křížení nastává s pravděpodobností obvykle 0,75–0,95 a do značné míry ovlivňuje efektivnost genetického algoritmu, mutace nastávají s pravděpodobností 0,001–0,05 a brání příliš rychlé homogenizaci vlastností v populaci, ztrátě potenciálně užitečného genetického materiálu a předčasné konvergenci populace.

Konec 
Právě vytvořené potomstvo se stává novou generací a starou generaci již nebereme v úvahu. Jedná se o nejjednodušší generační strategii, při které původní populace zcela vymře. Tím byl dokončen přechod od jedné populaci k druhé a celý cyklus se bude opakovat dokud nebude splněna ukončovací podmínka. Podmínkou pro ukončení algoritmu může být například maximální počet generací, po který je populaci umožněn její vývoj, nalezení uspokojivého řešení, nedostatečná změna nejlepšího dosud nalezeného řešení v posledních generacích atd.

Genetické programování 
Počítačové programy pro genetické programování mohou být napsány v nejrůznějších programovacích jazycích. V nejstarších implementacích byly instrukce programu a datové hodnoty organizovány ve stromových strukturách, což upřednostňovalo jazyky, které přirozeně zahrnují tyto struktury (např. Lisp). Později byly navrženy a úspěšně realizovány také jiné typy implementace, jako např. s lineární reprezentací jedinců, která více vyhovuje klasickým imperativním jazykům.

Vzhledem k velkému počtu iterací genetického algoritmu, které musí proběhnout pro nalezení dostatečně kvalitního řešení optimalizační úlohy, je výpočet velmi náročný na výpočetní čas (dobu výpočtu). Jelikož genetický algoritmus lze z principu rozsáhle paralelizovat (s každým jedincem lze pracovat v samostatném výpočetním vlákně), je tedy vhodné optimalizovat spolupráci softwaru a hardwaru, např. prostřednictvím spolupráce tzv. CUDA platformy s grafickou kartou počítače: Graphics Processing Unit (GPU) je systém procesorů implementovaných na grafické kartě, původně určený především pro běh počítačových her, kladoucích velké nároky na výpočetní výkon. Na rozdíl od CPU majících k dispozici maximálně 8 nebo 16 výpočetních vláken, GPU jich může využívat až např. 2 048. Pro algoritmizaci se pak může užít CUDA platforma, umožňující programovat v jazicích C++ resp. Fortran, která umožní díky velkému počtu dostupných výpočetních vláken vysoký stupeň paralelizace výpočtu, čímž zvýší výpočetní výkon a zkrátí dobu výpočtu.

Příklad 
Předpokládejme funkci dvou proměnných . Hledáme maximum funkce na množině .
Předpokládáme, že požadovaná přesnost je 4 místa za desetinnou čárkou. Potom je nezbytné rozdělit interval alespoň na:  stejných dílů. To znamená použít binární vektor délky 42 bitů (21 bitů pro proměnnou , a stejný počet pro proměnnou ). Tímto byla vyřešena otázka zakódování jedinců, kterého je možné kdykoliv převést na hodnoty proměnných  a . Jako ohodnocující funkce je možné použít vlastní funkci , která je nezáporná a má dostatečnou rozlišovací schopnost. Protože cílem je najít její maximum, není nutné ji ani nijak modifikovat (jinak by bylo nutné provést její transformaci). K ohodnocení individuí je nutné pouze dekódovat hodnoty proměnných  a  a pro každé individuum spočítat hodnoty funkce . Dále už může algoritmus pokračovat základními genetickými operátory křížení a mutace uvedenými výše. Je samozřejmě také nutné zvolit velikost počáteční populace (např. ) a pravděpodobnosti křížení (např. ) a mutací (např. ).

Reference

Literatura 
 Koza, J.R., Bennett, F. H., Andre, D., and Keane, M.A. (1999), Genetic Programming III: Darwinian Invention and Problem Solving, Morgan Kaufmann
 Koza, J.R., Keane, M. A., Streeter, M. J., Mydlowec, W., Yu, J., Lanza, G. (2003), Genetic Programming IV: Routine Human-Competitive Machine Intelligence, Kluwer Academic Publishers
 Smith, S.F. (1980), A Learning System Based on Genetic Adaptive Algorithms, PhD dissertation (University of Pittsburgh)
 Cramer, N. L. (1985), „A representation for the Adaptive Generation of Simple Sequential Programs“ in Proceedings of an International Conference on Genetic Algorithms and the Applications, Grefenstette, John J. (ed.), CMU
 Langdon, W. B., Poli, R. (2002), Foundations of Genetic Programming, Springer-Verlag
 Langdon, W. B., Poli, R., McPhee, N. F. (2008), A Field Guide to Genetic Programming, Lulu.com, freely available from the internet 
 Mařík V., Štěpánková O., Lažanský J. a kol: Umělá inteligence 4, Academia, Praha, 2003, 
 Jiří Šíma, Roman Neruda: Teoretické otázky neuronových sítí (oddíly 14.3 a 14.4 se zabývají genetickými algoritmy)

Související články 
 Simulované žíhání

Externí odkazy 
 Petr Luner: Jemný úvod do genetických algoritmů
 RNDr. Jaroslav Teda, Ph.D.: Genetické algoritmy a jejich aplikace v praxi
 Marek Obitko: Introduction to Genetic Algorithms, s interaktivními Java applety (anglicky)
 Weise, T., Global Optimization Algorithms – Theory and Application  (anglicky)
 Genetic Programming FAQ
 The Hitch-Hiker's Guide to Evolutionary Computation
 John Koza's Genetic Programming Site
 Juergen Schmidhuber's GP Site, s články o GP napsanými před Kozovým článkem z roku 1987
 Bill Langdon's GP bibliography
 Meta-Genetic Programming Site
 Markus Brameier: On linear genetic programming, 1/2005
 ADT – nový způsob reprezentace jedince v populaci 

Umělá inteligence
Evoluční algoritmy