Genetický algoritmus

princip, základní pojmy

Genetický algoritmus 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. Existuje velké množství algoritmů, které lze označit za genetické algoritmy.

Co je to evoluční algoritmus?

V přírodě biologičtí jedinci jedné populace mezi sebou soutěží o přežití a možnost reprodukce na základě toho, jak dobře jsou přizpůsobeni prostředí. V průběhu mnoha generací se struktura dané populace vyvíjí na základě Darwinovy teorie o přirozeném výběru a přežívání jen těch jedinců, kteří mají největší sílu (schopnost přežít).

Evoluční algoritmy se snaží využít modelů evolučních procesů, aby tak nalezly řešení náročných a rozsáhlých úloh. Veškeré takové modely mají několik společných rysů:

  • pracují zároveň s celou skupinou (množinou) možných řešení zadaného problému místo hledání jednotlivého řešení
  • vygenerovaná řešení postupně vylepšují zařazováním nových řešení, získaných kombinací původních
  • kombinace řešení jsou následovány náhodnými změnami a vyřazováním nevýhodných řešení

Genetický algoritmus - pojmy

  • Populace
    • soubor jedinců
    • na začátku máme soubor, jež se nazývá výchozí populace
  • Jedinec
    • člen populace popsaný chromozomem
    • potenciální řešení optimalizační úlohy
  • Chromozom
    • řetězec nezávisle proměnných optimalizované funkce, neboli řešení optimalizační úlohy (stavební plán jedince), chromozom jedince nemusí být nejlepší řešení optimalizační úlohy
    • chromozom některého jedince může vypadat následovně: (1, 0, 1, 0, 1, 1, 0, 0)
  • Fitness funkce
    • optimalizovaná funkce (ohodnocení schopnosti jedince přežít v okolním prostředí)
    • fitness funkce může být dána například počtem 1 v chromozomu
  • Generace
    • soubor řetězců nezávisle proměnných optimalizované funkce (jedinců) "stejného věku"
    • například tedy platí, že Výchozí populace je nultá generace
  • Reprodukce
    • tvorba nové generace jedinců pomocí křížení a mutace jedinců staré generace
    • jedinci s nejvyšší fitness funkcí vytvářejí nového potomka
  • 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)
    • spojení chromozomu dvou rodičů
    • nový jedinec bude mít chromozom vytvořený z částí chromozomů jeho rodičů
  • Mutace
    • přepsání podřetězce nezávisle proměnných optimalizované funkce (poškození genetické informace)
    • dá se implementovat jako náhodná změna v chromozomu jedince
    • neděje se tak často, jako křížení

Princip genetického algoritmu

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.

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í reprodukováni v modifikované jedince následující generace. Tento postup se iterativně opakuje. Nejjednodušší verze tohoto algoritmu starou generaci zahazuje a pracuje jen s tou novou.

Existuje velké množství způsobů - algoritmů, kterými lze tento princip uplatnit.

Příklad algoritmu

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)

Poté je třeba jedince ohodnotit pomocí fitness funkce. Definice této funkce je dána konkrétním problémem kde se snažíme najít jedince, jež mají z hlediska našeho problému optimální vlastnosti. Řekněme že naše definice je počet 1 v chromozomu jedince.

Ohodnocení jedinců
obr. 1: Ohodnocení jedinců
dostupné z: https://cs.wikipedia.org/wiki/Genetick%C3%BD_algoritmus

Další následuje výběr rodičů, kteří se budou podílet na nové generaci. 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 probíhá povětšinou náhodně s tím, že jedinec s vyšší hodnotou fitness má větší šanci na to být vybraný.

Vybraní rodiče
obr. 2: Vybraní rodiče
dostupné z: https://cs.wikipedia.org/wiki/Genetick%C3%BD_algoritmus

Nyní následuje reprodukce, tedy vytváření jedinců nových, za pomocí křížení. Existuje spousty technik křížení, ale tady si ukážeme tzv jednobodové křížení. Každému páru vybereme bod a nový jedinec dostane levou část jednoho rodiče, a pravou část druhého.

Výsledek křížení
obr. 3: Výsledek křížení
dostupné z: https://cs.wikipedia.org/wiki/Genetick%C3%BD_algoritmus

Nové chromozomy reprezentují další generaci.

Na novou generaci je možnost aplikovat mutaci. Dává se většinou malá šance (v řádech setin procent) že se mutace aplikuje, aby populace nezdegradovala. Mutace totiž změní v každém chromozomu náhodně jednu hodnotu.

Výsledek mutace na nové generaci
obr. 4: Výsledek mutace na nové generaci
dostupné z: https://cs.wikipedia.org/wiki/Genetick%C3%BD_algoritmus

Nyní se vrátíme do kroku jedna, tedy znovu ohodnotíme jedince, vybereme rodiče a provedeme reprodukci. Toto se může dít tak dlouho, dokud se nám neobjeví optimální jedinec, nebo alespoň téměř optimální, nebo dokud změna fitness funkce skrze několik generací nebude blízká 0. Účelem je mít po konečném počtu generací jedince s co nejlepší fitness funkcí.

Příklady aplikace genetických algoritmů

  • nejpoužívanější jsou pro optimalizační úlohy (např. plánování, navrhování obvodů VLSI) a pro strojové učení (klasifikace, predikce, učení neuronových sítí)
  • byly použity pro "automatické programování" (např. vývoj buněčných automatů, genetické programování)
  • chemie (určování struktury složitých molekul)
  • ekonomie (predikce, hledání parametrů ekonomických modelů)
  • biologie a medicína (modelování imunitního systému, modelování ekologického systému)
  • sociologie (modelování sociálního systému)

Zdroje