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)^[1]

• 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 ^[2], 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:

1. Inicializace algoritmu – tvorba první generace složené z náhodně vygenerovaných jedinců (např. 100 až 1000 jedinců)
2. 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.)
3. 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í
4. Konec iteračního cyklu – pokud není splněna zastavovací podmínka, jdi na bod 2, jinak na bod 5
5. Výsledek algoritmu – jedinec poslední generace s nejvyšší hodnotou fitness funkce reprezentuje optimální řešení

pozn.:

${\displaystyle P(x)={F(x) \over \max(F(x))}}$ kde ${\displaystyle P(x)}$ je pravděpodobnost označení jedince ${\displaystyle x}$ jako rodiče a ${\displaystyle F(x)}$ hodnota fitness funkce jedince ${\displaystyle x}$.

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 ${\displaystyle i}$-tého partnera dána je vztahem ${\displaystyle p_{i}={\frac {f_{i}}{\sum _{j=1}^{N}f_{j}}}}$. Byla vygenerována čtyři pseudonáhodná čísla ${\displaystyle r\in \langle 0,1\rangle }$ 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^[3] 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^[4][5]). 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^[6].

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 ${\displaystyle f(x,y)}$. Hledáme maximum funkce na množině ${\displaystyle \{[x,y]|x,y\in \langle -100,100\rangle \}}$. Předpokládáme, že požadovaná přesnost je 4 místa za desetinnou čárkou. Potom je nezbytné rozdělit interval alespoň na: ${\displaystyle (100-(-100))\times 10\,000=2\,000\,000}$ stejných dílů. To znamená použít binární vektor délky 42 bitů (21 bitů pro proměnnou ${\displaystyle x}$, a stejný počet pro proměnnou ${\displaystyle y}$). 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 ${\displaystyle x}$ a ${\displaystyle y}$. Jako ohodnocující funkce je možné použít vlastní funkci ${\displaystyle f(x,y)}$, 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 ${\displaystyle x}$ a ${\displaystyle y}$ a pro každé individuum spočítat hodnoty funkce ${\displaystyle f(x,y)}$. 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ř. ${\displaystyle N=100}$) a pravděpodobnosti křížení (např.${\displaystyle 0,9}$ ) a mutací (např. ${\displaystyle 0,01}$).

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 ISBN 978-1-4092-0073-4
• Mařík V., Štěpánková O., Lažanský J. a kol: Umělá inteligence 4, Academia, Praha, 2003, ISBN 80-200-1044-0
• 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 Archivováno 11. 9. 2008 na Wayback Machine. (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 Archivováno 30. 9. 2007 na Wayback Machine.