IV. Genetický algoritmus

Základní popis

Genetické algoritmy jsou inspirovány Darwinovou teorií evoluce. Řešení problému se přímo nenavrhuje, ale vyvíjí.

Algoritmus začíná s množinou řešení (reprezentovaných chromozomy) nazvanou populace. Řešení z jedné populace se vybírají a použijí k vytvoření nové populace. Myšlenka je taková, že nová populace bude lepší než ta stará. Řešení vybraná k vytváření nových řešení (potomků) se volí podle jejich kvality: čím jsou vhodnější, tím větší mají šanci rozmnožit se.

Tento proces se opakuje, dokud není splněna nějaká podmínka, například dokud není dosaženo maximálního počtu generací nebo se nejlepší řešení přestane zlepšovat.

Příklad
Jak už víte z kapitoly o prohledávacím prostoru, řešení problému lze často vyjádřit jako hledání extrému funkce. Právě takový problém je zde ukázán. Je zadána funkce a genetický algoritmus (GA) se snaží najít její minimum.
Můžete si vyzkoušet spustit genetický algoritmus v demonstraci níže stisknutím tlačítka Start. Graf představuje prohledávací prostor a svislé čáry představují řešení (body v prohledávacím prostoru). Červená čára je nejlepší řešení, zelené čáry jsou ostatní.
Start spustí algoritmus, Step provede jeden krok (tedy vytvoří jednu novou generaci), Stop algoritmus zastaví a Reset obnoví původní populaci.

Schéma základního genetického algoritmu

  1. [Start] Vygeneruj náhodnou populaci n chromozomů (vhodných řešení problému)
  2. [Vyhodnocení] Vyhodnoť hodnotu účelové funkce f(x) pro každý chromozom x v populaci
  3. [Nová populace] Vytvoř novou populaci opakováním následujících kroků, dokud není nová populace úplná
    1. [Selekce] Vyber dva rodičovské chromozomy z populace podle jejich kvality (čím lepší kvalita, tím větší pravděpodobnost výběru)
    2. [Křížení] S pravděpodobností křížení křiž rodiče a vytvoř nové potomky. Pokud ke křížení nedojde, je potomek přesnou kopií rodičů.
    3. [Mutace] S pravděpodobností mutace mutuj nové potomky v každém lokusu (pozici v chromozomu).
    4. [Přijetí] Umísti nové potomky do nové populace
  4. [Nahrazení] Použij nově vytvořenou populaci pro další běh algoritmu
  5. [Test] Je-li splněna ukončovací podmínka, zastav a vrať nejlepší řešení v aktuální populaci
  6. [Smyčka] Jdi na krok 2

Několik poznámek

Jak vidíte, schéma základního GA je velmi obecné. Existuje mnoho věcí, které lze u různých problémů implementovat odlišně.

První otázkou je, jak vytvořit chromozomy a jaký typ kódování zvolit. S tím úzce souvisí křížení a mutace, dva základní operátory GA. Kódování, křížení a mutace jsou představeny v další kapitole.

Další otázkou je, jak vybírat rodiče pro křížení. To lze dělat různými způsoby, ale hlavní myšlenkou je zvýhodnit lepší rodiče v naději, že vytvoří lepší potomky. Možná si také všimnete, že vytváření nové populace pouze z potomků může způsobit ztrátu nejlepšího chromozomu z předchozí populace. To je pravda, a proto se často používá takzvaný elitismus. To znamená, že alespoň jedno nejlepší řešení se beze změny zkopíruje do nové populace, takže nejlepší nalezené řešení přežije až do konce běhu.

O některých z těchto otázek bude řeč později.

Možná vás také napadá, proč genetické algoritmy fungují. Část tohoto jevu lze vysvětlit Hollandovým teorémem schémat, i když byl tento teorém v posledních letech také kritizován. Pokud se chcete dozvědět víc, podívejte se do dalších zdrojů.