Genetický algoritmus

Genetický algoritmus (GA) je heuristický postup, který se snaží aplikací principů evoluční biologie nalézt řešení složitých problémů, pro které neexistuje použitelný exaktní algoritmus. Genetické algoritmy, resp. všechny postupy patřící mezi tzv. evoluční algoritmy, používají techniky napodobující evoluční procesy známé z biologie – dědičnost, mutace, přirozený výběr a křížení – pro „šlechtění“ řešení zadané úlohy.

Princip práce genetického algoritmu je postupná tvorba generací různých řešení daného problému. Při řešení se uchovává tzv. populace, jejíž každý jedinec představuje jedno řešení daného problému. Jak populace probíhá evolucí, řešení se zlepšují. Tradičně je řešení reprezentováno binárními čísly, řetězci nul a jedniček, nicméně používají se i jiné reprezentace (strom, pole, matice, …). Typicky je na začátku simulace (v první generaci) populace složena z naprosto náhodných členů. V přechodu do nové generace je pro každého jedince spočtena tzv. fitness funkce, která vyjadřuje kvalitu řešení reprezentovaného tímto jedincem. Podle této kvality jsou stochasticky vybráni jedinci, kteří jsou modifikováni (pomocí mutací a křížení), čímž vznikne nová populace. Tento postup se iterativně opakuje, čímž se kvalita řešení v populaci postupně vylepšuje. Algoritmus se obvykle zastaví při dosažení postačující kvality řešení, případně po předem dané době.

Obecné schéma genetického algoritmu

Algoritmus lze slovy zapsat takto:

(Inicializace) Vytvoř nultou populaci (obvykle složenou z náhodně vygenerovaných jedinců)
(Začátek cyklu) Pomocí určité výběrové metody (zpravidla zčásti náhodné) vyber z populace několik jedinců s vysokou zdatností
Z vybraných jedinců vygeneruj nové použitím následujících metod (operátorů), čímž vznikne další generace:
- křížení - „prohoď“ části několika jedinců mezi sebou
- mutace - náhodně změň část jedince
- reprodukce - kopíruj jedince beze změny
Vypočti zdatnost těchto nových jedinců
(Konec cyklu) Pokud není splněna zastavovací podmínka, tak pokračuj od bodu 2
(Konec algoritmu) Jedinec s nejvyšší zdatností je hlavním výstupem algoritmu a reprezentuje nejlepší nalezené řešení.

Pojmy

Pro jedince se používá označení fenotyp a pro jeho reprezentaci se používá termín genotyp, genom nebo chromozom.^[1]

Chromozom se dělí na jednotlivé geny, které jsou lineárně uspořádány. To znamená, že i-tý gen chromozomů stejného typu reprezentuje stejnou charakteristiku. Gen nabývá různých hodnot, kterým se říká alely.^[2]

Individua mohou být zakódována (geneticky popsána) různým způsobem. To, jakým způsobem jsou popsána, může být důležité pro úspěch či neúspěch řešení konkrétní úlohy. Jedním z jednoduchých způsobů může být například binární řetězec dané délky.^[3]

Příklad genetického algoritmu

Vytvoření počáteční generace

Předpokládejme, že je počáteční generace tvořena množinou náhodně vygenerovaných řetězců dané délky. Například 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)

Ohodnocení individuí

Definice ohodnocující (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 ohodnocující funkce dána počtem jedničkových bitů v chromozomu.

číslo	chromozom	ohodnocení	podíl celkového	kumulativně
#1	`(1,0,1,0,1,1,0,0)`	4	0,250	0,250
#2	`(0,1,1,1,1,1,0,1)`	6	0,375	0,625
#3	`(0,0,0,1,0,0,0,1)`	2	0,125	0,750
#4	`(1,1,0,0,1,1,0,0)`	4	0,250	1,000

Tvorba potomků

K vytvoření potomků jsou používány dva základní genetické operátory – mutace a křížení.

U křížení vzniká v nové generaci potomek (či několik potomků současně) na základě dvou vybraných rodičů z generace předchozí. Nejprve se zvolí dvojice individuí, na kterou se poté aplikuje operátor křížení, čímž vznikne potomek či potomci.

Výběr dvojic individuí

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ší.

V tomto příkladu je pravděpodobnost výběru $i$ -tého partnera dána vztahem $p_{i}={\frac {f_{i}}{\sum _{j=1}^{N}f_{j}}}$ . Byla vygenerována čtyři pseudonáhodná čísla $r\in \langle 0,1\rangle$ a tímto vybrána čtyři individua pro reprodukci.

	$r$	individuum	chromozom
1. pár	0,340	#2	`(0,1,1,1,1,1,0,1)`
1. pár	0,975	#4	`(1,1,0,0,1,1,0,0)`
2. pár	0,705	#3	`(0,0,0,1,0,0,0,1)`
2. pár	0,409	#2	`(0,1,1,1,1,1,0,1)`

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.

	individuum	původní chromozom	nový chromozom
1. pár	#2	`(0,1 \| 1,1,1,1,0,1)`	`(0,1 \| 0,0,1,1,0,0)`
1. pár	#4	`(1,1 \| 0,0,1,1,0,0)`	`(1,1 \| 1,1,1,1,0,1)`
2. pár	#3	`(0,0,0,1 \| 0,0,0,1)`	`(0,0,0,1 \| 1,1,0,1)`
2. pár	#2	`(0,1,1,1 \| 1,1,0,1)`	`(0,1,1,1 \| 0,0,0,1)`

Mutace

Na výsledné potomstvo se aplikuje ještě další genetický operátor – mutace. Ta s malou pravděpodobností jednoduchým způsobem náhodně mění hodnotu jednotlivých genů. V náhodně vybraných chromozomech tedy změníme hodnotu genu:

(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^[4] 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ému zjednotvárnění vlastností v populaci, ztrátě potenciálně užitečného genetického materiálu a předčasné konvergenci populace.^[2]

Opakování cyklu

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.

Ukončení algoritmu

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 $k$ generacích atd.

Optimalizační úloha

Genetické algoritmy jsou často v praxi využívány k řešení rozmanitých optimalizačních úloh. Přestože uvedený postup řešení genetického algoritmu je čistě ilustrativní, lze tento postup aplikovat s drobnými úpravami např. na řešení extremálních úloh.

Předpokládejme funkci dvou proměnných $f(x,y)$ . Hledáme maximum funkce na množině $D=(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: $(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 x, a stejný počet pro proměnnou 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 x a y.

Jako ohodnocující funkce je možné použít vlastní funkci $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 x a y a pro každé individuum spočítat hodnoty funkce $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ř. N=100) a pravděpodobnosti křížení (např. 0,9) a mutací (např. 0,01).

Odkazy

Reference

↑ Mitchell, M.: An Introduction to Genetic Algorithms. Cambridge, MA: MIT Press 1996
↑ ^a ^b Hynek, Josef: Genetické algoritmy a genetické programování. Grada: Praha 2008
↑ Holland, J. H.: Adaptation in Natural and Artificial Systems. The University of Michigan Press, Ann Arbor, Michigan, 1975
↑ Schaffer, J. D., Caruana, R. A. Eschelman, L. J., Das, R.: A Study of Control Parameters Affecting Online Performance of Genetic Algorithms for Function Optimization.

Externí odkazy

Petr Luner: Jemný úvod do genetických algoritmů
RNDr. Jaroslav Teda, Ph.D.: Genetické algoritmy a jejich aplikace v praxi
Jiří Šíma, Roman Neruda: Teoretické otázky neuronových sítí (oddíly 14.3 a 14.4 se zabývají genetickými algoritmy)
Marek Obitko: Introduction to Genetic Algorithms, s interaktivními Java applety (anglicky)
Poli, R., Langdon, W. B., McPhee, N. F. (2008), A Field Guide to Genetic Programming (anglicky)
Weise, T., Global Optimization Algorithms - Theory and Application (anglicky)

[1] Mitchell, M.: An Introduction to Genetic Algorithms. Cambridge, MA: MIT Press 1996

[hynek-2] Hynek, Josef: Genetické algoritmy a genetické programování. Grada: Praha 2008

[3] Holland, J. H.: Adaptation in Natural and Artificial Systems. The University of Michigan Press, Ann Arbor, Michigan, 1975

[4] Schaffer, J. D., Caruana, R. A. Eschelman, L. J., Das, R.: A Study of Control Parameters Affecting Online Performance of Genetic Algorithms for Function Optimization.

[1]

[2]

[3]

[4]