Kurz

logo

Evoluční algoritmy


Evoluční algoritmy (EA) jsou založeny na dvou velmi známých tezích. První je Mendelův koncept genetické dědičnosti, druhou Darwinův pud po přežití:

Dědičné faktory jsou přeneseny z rodiče na potomka.

G. J. Mendel

Organismy s příznivými rysy mají větší šanci na přežití a reprodukci.

Ch. Darwin

Genetické algoritmy (GA), které se řadí mezi EA, využívají těchto dvou myšlenek následujícím způsobem. Základní koncept řešení k danému problému je nahrazen tzv. individuálem. Idividuál se skládá z chromozomu a míry jeho kvality, tzv. fitness. Zatímco chromozom popisuje (kóduje) řešení problému, fitness se vztahuje k optimalizačnímu kritériu, jež se GA snaží optimalizovat (tj. minimalizovat či maximalizovat). Geny jsou základní jednotky, z nichž je chromozom složen. Posledním dodatkem k terminologii je rozlišní dvou termínů. Genotypem rozumíme to, co je ve skutečnosti na chromozomu zapsáno, kdežto fenotyp nám říká, co to znamená v kontextu našeho problému.

individuál
(chromozom + fitness) = popis řešení problému
chromozom
celková reprezentace řešení problému řešení problému
fitness
kvalitativní míra přiřazená individuálovi - popis míry adaptace k prostředí
gen
elementární jednotka, ze které je složen chromozom
genotyp
informace zapsaná na chromozomu
fenotyp
význam informace na chromozomu z hlediska problému

Jako příklad se podívejme na problém nalezení minima funkce $f(x,y) = x^2 + y^2$ (tj. dvojici $(x,y)$, pro kterou je $f$ nejmenší), kde pro jednoduchost uvažujme $x,y \in [0..31]$. Graf této funkce je zobrazen níže. Problém budeme modelovat tak, že chromozom našeho individuála se bude sestávat z binárně zakódovaných dvojic $(x,y)$ a $f$ bude naší fitness mírou. Pro jasnou představu, jak náš model může vypadat, se podívejme na následující tabulku. Jednotlivé řádky zde představují jednotlivé individuály (řešení problému) a zvýrazněn je nejlepší individuál - opravdu, $(0,0)$ je minimum funkce $f$.

graf funkce f(x,y) = x^2 + y^2 pro x, y z <0,31>
Příklady individuálů pro problém minimalizace $f(x,y) = x^2 + y^2$
#genotyp $(x,y)_2$fenotyp $(x,y)$fitness $f(x,y) = x^2+y^2$
1(0 0 0 0 0, 0 1 0 1 0)(0, 10)0 + 100 = 100
2(0 0 0 0 1, 1 1 0 0 1)(1, 25)1 + 625 = 626
3(0 1 0 1 1, 0 0 0 1 1)(11, 3)121 + 9 = 130
4(0 0 0 0 0, 0 0 0 0 0)(0, 0)0 + 0 = 0
5(1 1 0 1 1, 1 0 0 1 0)(27, 18)729 + 324 = 1053

Máme již slušnou představu o tom, jak modelovat problém pomocí individuálů pro GA. Nyní se podívejme na samotný algoritmus (postup řešení problému). Na začátku procedury GA inicializujeme tzv. populaci individuálů. Jak si tento krok představit? Jednoduše vytvoříme určitý počet náhodných řešení našeho problému a ty ohodnotíme pomocí naší kriteriální funkce (fitness). V kontextu našeho příkladu lze tento krok realizovat např. vybráním 100 náhodných dvojic $(x,y) \in [0..31]^2$, převedením do binární reprezentace a ohodnocemím.

Jakmile nainicializujeme počáteční populaci, zacne typický generační cyklus. Ten se může opakovat do předem daného počtu generací nebo do dosažení určité podmínky, např. kvalita jedinců v populaci. Z populace vybereme několik individuálů jako rodiče a aplikujeme na ně operátor křížení, který zkombinuje jejich genetickou informaci a vytvoří potomky. Variant tohoto operátoru může být mnoho, uvedeme pouze tu nejjednodušší - chromozomy rodičů přerušíme na stejném, přesto náhodném, místě a vzniklé části křížem zkombinujeme. Ilustrujme si tento postup na našem příkladu. Na diagramu níže jsme vybrali individuály č. 1 a 3 jako rodiče a zkombinovali je do potomků A a B (oba chromozomy byly rozděleny za 3. pozicí a jejich části křížem zaměněny).

diagram generačního cyklu GA diagram operátoru křížení v GA

Pokud by byl pro vytvoření nové generace GA použit pouze operátor křížení, lehce by se mohlo stát, že po několika cyklech naše generace zdegeneruje k určitým individuálům (tj. jejich genetická informace, řešení problému, bude téměř totožná). Pro udržení diversity (a zvýšení šance dosažení kvalitního řešení) použijeme další paralelu z přírody kolem nás, operátor mutace. Opět uveďme nejjednodušší variantu - s určitou pravděpodobností zaměníme hodnotu na jednom místě potomkova chromozomu. Postup si ilustrujeme na posledním diagramu, kde jsme bitově zaměnili obsah chromozomu potomka B na 2. pozici. Vzniknul potomek B', kterého spolu s ostatními již jen ohodnotíme, tj. přiřadíme mu jeho fitness.

diagram operátoru mutace v GA

Ještě než se podíváme na poslední část GA, musíme uvést jeden důležitý technický detail. Po aplikaci rekombinačního a mutačního operátoru se může stát, že vzniklí potomci nejsou v kontextu našeho problému validní řešení. Tyto případy je nutné buď ošetřit nebo jim vhodnou volbou reprezentace a operátorů zamezit.

Posledním krokem řádného generačního cyklu GA je zpětné uvedení potomků do populace. V principu existují dva způsoby, jak tuto proceduru realizovat. Krátce si je představme.

generační nahrazení (angl. generational replacement)
po každém cyklu GA je nahrazena celá předchozí populace - analogie krátkodobě žijících druhů
částečné nahrazení (angl. steady state replacement)
po každém cyklu GA jsou nahrazeni pouze někteří jedinci předchozí populace - analogie dlouhodobě žijících druhů

Závěrem uveďme, že GA, jak byl popsán v tomto kurzu, je základní stavební rámec evolučních postupů. I přes množství implementačních i teoretických detailů, jež zůstaly nevyřčeny, se jedná o jednoduchý postup. Genetickou informaci jsme si představili jako pouhý řetězec nul a jedniček, což z teoretického pohledu je elegantní záležitost, ovšem jak počítačová věda tak příroda nám ukazují více. Uveďme několik dalších možných reprezentací:

Oblast EA, která se zabývá těmito nadstandardními reprezentacemi, se nazývá genetické programování (GP, po vzoru posledně uvedeného). Uplatněním těchto technik se budou zabývat i další kurzy sekce biologicky inspirovaných výpočtů.

Test znalostí