Genetické algoritmy - Find Your Way

Find Your Way je aplikácia, ktorá ukazuje možnosti genetických algoritmov. Na hracom poli sa entity musí dostať zo štartu do cieľa okolo užívateľom vytvorených prekážok. Entity sú naprogramované pomocou genetického algoritmu, dokážu sa teda samé učiť.

Znamená to to, že entity sa pokúšajú dostať do cieľa najskôr úplne náhodným správaním, potom sa učia a preberajú vlastnosti tých entít, ktoré sa dostali najďalej. Akonáhle sa teda nejaká entita dostane dostatočne ďaleko, ostatní sa od nej začnú učiť. Vďaka tomuto učenie sa skôr či neskôr adaptujú na akúkoľvek trasu. Akonáhle sa naučí trasu prechádzať, užívateľ môže trasu kompletne zmeniť a entity sa přeučí na novú trať.

Môžete si to skúsiť sami, nižšie dávam program na stiahnutie. Keby niekoho zaujímali zdrojové kódy, dal som ich na GitHub.

Ovládanie

Každá generácia možno spustiť kliknutím na tlačidlo Next Generation, alebo sa bude spúšťať automaticky, keď je zaškrtnutý checkbox Automatically next gen.

Keď práve nebeží generácie, sú odomknutá ostatné tlačidlá. Po kliknutí na Set Obstacles sa užívateľ dostane do edit móde, kde užívateľ môže prekážku vymazať tým, že na ňu klikne. Novú vytvorí tak, že klikne na dve miesta na hracej ploche, kde sa vytvorí obdĺžniková prekážka.

Užívateľ ešte môže buď vymazať všetko, čo sa entity naučili, alebo uložiť (a v hlavnom menu znova načítať) stav aplikácie.

Draw: Move ratio je v podstate rýchlosť tickov, koľko ich ubehne na jedno vykreslenie. Delay between frames sú FPSky, od 15 do 100 (menej je viac FPS)

Ako to funguje?

Každá entita (ten červený štvorček) má genetickú informáciu (reprezentovaná poľom čísiel dlhým 2000). Táto genetická informácia určuje, ako sa bude entita správať. Každý tick (ktorých počet je obmedzený na 2000) sa entita podľa čísla v genetickej informácii buďto pootočí kúsok hore, dole, alebo sa o kúsok vyrovná.

Po uplynutí 2000 tickov, alebo keď všetky entity do niečoho narazí, skončí generácie. Entity sú zoradené podľa toho, ako dobré sú. Časť entít (napríklad polovica) je vymazaná, zatiaľ čo tie ostatné sa medzi sebou skrížia a vytvorí toľko potomkov, koľko entít bolo zničené. Kríženie sa deje týmto spôsobom: Vždy sa vyberú 2 rôzne entity (náhodne, a to pokiaľ možno tak, že lepšie entity majú väčšiu šancu byť vybrané). Následne sa vyberie náhodné číslo X, a to od 1 do (dĺžka genómu - 1). Nový potomok bude mať X génov od prvého rodiča, zvyšok od druhého. Pri každej prenesené časti genómu je šanca X% na mutáciu, teda na nahradenie génu náhodným.

Týmto spôsobom sa entity vyvíja a samostatne sa učí. Nezabudnite si stiahnuť program a vyskúšať si to

Galéria