[CZ] Genetické programování

Ve všech předchozích cvičeních jsme používali jedince s relativně jednoduchým zakódování - většinou to byly pole s nějakými hodnotami. Nejsložitější kódování jsme používali u evoluce pravidel - mohla být dálka pole u každého jedince jiná. Existují ale i evoluční algoritmy, kde je kódování jedince mnohem složitější, příkladem je například stromové genetické programování.

Jedinci a fitness

V genetickém programování jedinci kódují syntaktické stromy, které lze interpretovat jako jednoduché programy, nebo které mohou kódovat složitější strukturu (jako elektronický obvod). V nejjednodušším případě je strom jen jeden výraz (například aritmetický). V tomto případě lze genetické programování použít k vyřešení problému symbolické regrese. Dostáváme soubor vstupů a výstupů a cílem je najít výraz, který při použití na vstupy vytvoří správné výstupy. Kvalita výrazu se obvykle měří střední čtvercovou chybou výstupů pro dané vstupy (průměr čtverců rozdílů mezi požadovaným výstupem a skutečným výstupem).

Terminály a neterminály

Jedinci (stromy) se skládají z tzv. terminálů a neterminálů. Terminály jsou listy stromu a obsahují vstupy nebo konstanty. Neterminály jsou naopak vnitřní uzly a obsahují funkce. Pro symbolickou regresi budeme mít obvykle běžné matematické operace jako sčítání, odčítání, násobení atd. a v některých případech i jiné zajímavé funkce (sinus, kosinus, exponenciál, ...). Můžeme však mít i jiné funkce, jako jsou podmínky (např. "menší než", "menší než 0" atd.). Funkce používané jako terminály a neterminály jsou specifické pro daný problém. Pokud neuvedeme všechny potřebné funkce, GP nemusí být schopno najít rozumné řešení, na druhou stranu použití více funkcí, než je potřeba, optimalizaci ztěžuje.

Inicializace a genetické operátory

Se složitějšími jedinci přicházejí složitější metody inicializace a složitější (a rozmanitější) genetické operátory. V GP jsou náhodní počáteční jedinci náhodné stromy. Pro jejich vytvoření existují dvě základní metody - buď se vygeneruje náhodný strom s daným počtem uzlů ("grow"), nebo se vygeneruje náhodný strom s danou hloubkou ("full"). Nejběžnější metodou je však kombinace těchto dvou - polovina populace je generována "grow" a polovina "full". Tato metoda se nazývá "ramped half-and-half".

V genetickém programování obvykle používáme relativně velký počet genetických operátorů. Nejčastější křížení prohazuje náhodné podstromy mezi jedinci. Existuje několik variant tohoto operátoru - jedna z nich například zajišťuje, aby vyměněné podstromy měly podobnou velikost nebo hloubku, což zajišťuje, že výsledné stromy nebudou příliš velké. Existuje také poměrně velké množství různých mutací běžně používaných v GP. Často se mění uzel ve stromu za jiný uzel (musíme být opatrní a měnit neterminály pouze na neterminály se stejným počtem argumentů). Další možností je odebrat podstrom a místo něj vygenerovat nový náhodný. Jedním z cílů mutace může být také zmenšení výrazu - v takovém případě může být podstrom nahrazen menším podstromem nebo dokonce terminálem.

Implementace v deap

Knihovna deap má řadu užitečných metod pro implementaci genetického programování, všechny výše uvedené techniky inicializace a všechny zmíněné genetické operátory jsou implementovány v deapu. Abychom mohli aplikovat GP v deapu, musíme specifikovat  množinu primitiv (terminály a neterminály). Zde můžeme specifikovat jakékoliv funkce jako neterminály, dokonce i naše vlastní. Musíme však být opatrní, funkce musí být definovány pro všechny vstupy. Pokud například chceme použít dělení, musíme nějak zajistit, co by se mělo stát, pokud je dělitel 0. Zbytek implementace GP v deapu je podobný jako jiné implementace v deap, které jsem vám ukazovat minul. Většina nástrojů pro GP je v modulu deap.gp. Příklad GP implementovaného v deap je v souboru  deap_gp.py v repozitáři ke cvičení.

Posledních pár řádek souboru ukazuje, jak extrahovat logy ze struktury, kterou vrací deap a převést je do formátu, který jsme používali na cvičení. Upravil jsem také trochu soubor utils, aby fungoval i v případě, že počet vyhodnocení fitness je v každé generaci jiný (deap vyhodnocuje pouze jedince, kteří se změnili).