Genetické algoritmy - Find Your Way

Find Your Way je aplikace, která ukazuje možnosti genetických algoritmů. Na hracím poli se entity musí dostat ze startu do cíle kolem uživatelem vytvořených překážek. Entity jsou naprogramované pomocí genetického algoritmu, dokáží se tedy samy učit.

Znamená to to, že entity se pokoušejí dostat do cíle nejdříve naprosto náhodným chováním, poté se učí a přejímají vlastnosti těch entit, které se dostaly nejdále. Jakmile se tedy nějaká entita dostane dostatečně daleko, ostatní se od ní začnou učit. Díky tomuto učení se dříve či později adaptují na jakoukoli trasu. Jakmile se naučí trasu procházet, uživatel může trasu kompletně změnit a entity se přeučí na novou trať.

Můžete si to zkusit sami, níže dávám program ke stažení. Kdyby někoho zajímaly zdrojové kódy, dal jsem je na GitHub.

Ovládání

Každá generace lze spustit kliknutím na tlačítko Next Generation, nebo se bude spouštět automaticky, když je zaškrtnutý checkbox Automatically next gen.

Když zrovna neběží generace, jsou odemčená ostatní tlačítka. Po kliknutí na Set Obstacles se uživatel dostane do edit módu, kde uživatel může překážku vymazat tím, že na ni klikne. Novou vytvoří tak, že klikne na dvě místa na hrací ploše, kde se vytvoří obdélníková překážka.

Uživatel ještě může buďto vymazat vše, co se entity naučily, nebo uložit (a v hlavním menu znovu načíst) stav aplikace.

Draw : Move ratio je v podstatě rychlost ticků, kolik jich uběhne na jedno vykreslení. Delay between frames jsou FPSka, od 15 do 100 (méně je více FPS)

Jak to funguje?

Každá entita (ten červený čtvereček) má genetickou informaci (reprezentována polem čísel dlouhým 2000). Tato genetická informace určuje, jak se bude entita chovat. Každý tick (jejichž počet je omezen na 2000) se entita podle čísla v genetické informaci buďto pootočí kousek nahoru, dolů, nebo se o kousek vyrovná.

Po uplynutí 2000 ticků, nebo když všechny entity do něčeho narazí, skončí generace. Entity jsou seřazeny podle toho, jak dobré jsou. Část entit (třeba polovina) je vymazána, zatímco ty ostatní se mezi sebou zkříží a vytvoří tolik potomků, kolik entit bylo zničeno. Křížení se děje tímto způsobem: Vždy se vyberou 2 různé entity (náhodně, a to pokud možno tak, že lepší entity mají větší šanci být vybrány). Následně se vybere náhodné číslo X, a to od 1 do (délka genomu - 1). Nový potomek bude mít X genů od prvního rodiče, zbytek od druhého. U každé přenesené části genomu je šance X% na mutaci, tedy na nahrazení genu náhodným.

Tímto způsobem se entity vyvíjí a samostatně se učí. Nezapomeňte si stáhnout program a vyzkoušet si to

Galerie