Háztáji evolúciószimulátor

Nemrég egy fórumon akadtam egy programra, ami elsőre mellbevágott, ez tulajdonképpen egy házi készítésű evolúciószimulátor, ráadásul nyílt forráskódú, egyszerű webes felülettel, így bárki könnyedén játszhat vele. A kezelése egyszerű, a jobb oldali panelen beállítható, hogy milyen kis arcocska legyen a legelőnyösebb, majd a bal oldali ablakban végigkövethetjük, ahogy egy populáció egyedei evolválnak. Annyira megtetszett, hogy mindenképpen szerettem volna róla írni, így megkerestem a szerzőt, sajnos_kacatot, hogy válaszoljon pár kérdésre, magyarázza el, hogyan is működik a program! Az ő válaszai olvashatók alább.

Nemrég egy fórumon akadtam egy programra, ami elsőre mellbevágott, ez tulajdonképpen egy házi készítésű evolúciószimulátor, ráadásul nyílt forráskódú, egyszerű webes felülettel, így bárki könnyedén játszhat vele. A kezelése egyszerű, a jobb oldali panelen beállítható, hogy milyen kis arcocska legyen a legelőnyösebb, majd a bal oldali ablakban végigkövethetjük, ahogy egy populáció egyedei evolválnak. Annyira megtetszett, hogy mindenképpen szerettem volna róla írni, így megkerestem a szerzőt, sajnos_kacatot, hogy válaszoljon pár kérdésre, magyarázza el, hogyan is működik a program! Az ő válaszai olvashatók alább.

Azt szeretném kérdezni, hogy mostanra már jónak tartod a programot? Készen állsz a kérdésekre?

Jónak éppen nem mondanám, mivel Explorerben 8-as és az alatti verziókkal nem működik, Safarival sem teszteltem, tableteken és okostelefonokon sem teszteltem, szóval a működés feltétele Firefox vagy Chrome, és ez nem egy túl elegáns megoldás. Persze összerakhatnék egy exploreres verziót is, de attól félek a sebességével gondok lennének…
Mindenesetre amit bele akartam írni, az már benne van.

Honnan jött az ötlet? Miért kezd el egy programozó evolúciós algoritmusokat fejleszteni?

Én konkrétan azért kezdtem el ezt a projektet, mert visszataláltam egy korábban olvasott cikkhez az AI blogon. Valamelyik evolúciótagadó oldalon közben ismét rátaláltam a jól ismert mantrára, hogy véletlenszerű változtatásokkal nem lehet előállítani értelmes mondatot egy karaktersorozatból. Szóba került Dawkins ősrégi weasel programja is, én meg örömmel vettem észre, hogy erre nekem is van egy megoldásom, de tulajdonképpen lehetne azt másra is használni, akár az AI blogon látott ábrák evolúcióját is szimulálhatnám vele.

Felhasználtál a programhoz korábbi algoritmusokat?

Volt egy olyan programom, ami a Shakespeare szonettet írógépen előállító majmokat modellezte. Persze genetikus algoritmust használva, hogy a végén a majmokból igazi Shakespeare-t tenyésszünk ki. Ez a szoftver annyit tudott, hogy létrehozott egy csomó véletlen karaktersorozatot, majd ezekből kiszelektálta azokat, amik a beírt szöveghez legjobban hasonlítottak, ezeket kombinálta, és apró változtatásokat eszközölt rajta. Néhány száz generáció alatt eljutott a populáció az előre beírt szöveghez.
Ezt a programot még akkor csináltam, amikor anno 2009-ben ID_EGEN terrorizálta a szkeptikusokat a régi fórumon. Saját gépemen jól működött, de a freeweb akkori szerverén valami korlátozás volt beállítva a php futtatásra, és néhány generáció után mindenféle hibaüzenetekkel elszállt. Már akkor gondoltam rá, hogy át kellene írnom tisztán javascript alapúra, hogy ne függjön semmilyen szervertől, de betemetett a céges munka, és félbemaradt a megvalósítás, aztán motiváció hiányában egy darabig nem foglalkoztam vele.

Visszatérve az előző kérdésre: miért kezd el egy programozó evolúciós algoritmusokat fejleszteni?
Olyan mérnöki problémák megoldására, amik túl sok változó paramétert tartalmaznak, nem lehet őket egyértelműen megoldani, és a numerikus számítási módszerek is túl sokáig tartanának.
Ezek a genetikus algoritmusok lényegében egy minimumkeresési problémát oldanak meg. Ha n darab szempont alapján értékelsz egy modellezett rendszert, és a kiértékelést úgy választod meg, hogy a 0 érték jelenti az optimális értéket, akkor a paraméterek alapján fel tudsz “rajzolni” egy olyan n dimenziós felületet, aminek a lokális minimumhelyei közelítőleg jó paraméterek reprezentálnak. Ha sikerül megtalálnod a globális minimumhelyeket, akkor az ott leolvasott n darab paraméter alapján le tudod a valóságban is gyártani a modellezett rendszer optimális változatát.
A genetikus algoritmusok úgy végzik a keresést, hogy az elején a teljes felületen véletlenszerűen szétszórsz egy nagy számú populációt, majd minden lépésben azokat szelektálod ki, amelyek közelebb vannak a 0-hoz. Persze előfordulhat, hogy hosszabb időre is beragad egy lokális minimumhelyre a keresés, ennek kivédésére vannak olyan trükkök, hogy minden egyed bitenként invertált változatát is hozzáadják a populációhoz, vagy az, hogy a nagyon gyenge fitneszű egyedek is kapnak esélyt a szaporodásra (ez utóbbit használtam én is).

Ha jól látom tulajdonképpen egy evolúciószimulátorról van szó, ahol előre beállíthatod az előnyös fenotípust, majd figyelheted hogyan evolvál egy populáció.

Igazából két program van itt egybeépítve. Van egy alap genetikus algoritmus, ami az aktuális populációt, és az egyedekhez tartozó fitnesseket tárolja, létrehozza a következő generációt, és végrehajtja a szelekciót.
A másik rész, amit a felhasználástól függően kell megírni, az tartalmazza a “DNS” előállításához szükséges funkciókat, a mutációs operátort, a fitnesst kiértékelő függvényt, és a megjelenítést. (Van egy harmadik rész is ami a paraméterek beállítását lehetővé tevő felhasználói felület.)
Az oldal alján van egy demo1 feliratú link, ami ugyanazt az alap algoritmust használja egy értelmes mondat előállításához.

Látni csak annyit lehet, hogy minden egyed egy arcocska. Milyenek belülről, milyen a genotípusuk, azaz mi határozza meg egy egyed fenotípusát? Haploidok? Diploidok?

A “DNS” egy bináris számsorozat, jelen esetben egy byte-okból álló tömb. Az első byte a formát határozza meg, a következő három a színt, a következő négy meg a vigyor formáját. 0-tól 255-ig terjedő egész számok írnak le minden “gént”, de a fenotípus előállításakor ezek átalakításra kerülnek. A színeknél nem kell konvertálni, de pl a vigyor az egy Bezier görbe, aminek van 4 fix paramétere, és 4 változó, amit a gének határoznak meg, itt a “gént” szorzom 10-el, osztom 255-el, hogy egy 10 pixeles sávon belül változzon a Bezier görbe kontrollpontjának helyzete.

A haploid-diploid fogalomnak utána kellett néznem. Mivel csak egyetlen “kromoszóma” van, minden gén csak egyszer szerepel az egyed “DNS“-ében, ezért azt kell mondjam, hogy haploidok. A diploid, vagy poliploid kromoszómák implementálása nagyon elbonyolítaná az algoritmust, és nem járna túl sok előnnyel. Lenne recesszív meg domináns öröklődés, ami a természetben jó dolog, biztosítja, hogy bizonyos gének akkor is továbbadódjanak, ha esetleg nem jelennek meg a fenotípusban. És esetleg ennek a recesszív génnek a mutációja fog valami előnyös tulajdonságot létrehozni. Szerintem a recesszív géneket helyettesíti az, hogy kellően nagy a populáció mérete, kellően sok utód jön létre, és a legrosszabb fitneszű egyednek is van esélye a szaporodásra, így nem láttam szükségesnek túlbonyolítani a szimulációt.

Hogyan örökítik a tulajdonságaikat az utódaikra?

Nem örökítik. :-)
Erről vitáztunk is jó hosszan vaskalapossal, hogy az autókra vajon érvényes-e az evolúció algoritmusa vagy sem, ő azt mondja, hogy mivel nem önmagukat másolják, ezért nem örökítik semmilyen tulajdonságukat az utódgenerációra (akár az autókat akár az autók tervrajzát nézzük). Én meg azt mondom, hogy ez nem az evolúcióhoz tartozik, ez a mi számít élőnek/élettelennek című vita tárgya lenne.
Szerintem olyan genetikus algoritmust még senki nem írt, ahol maga a gének másolása és az utód létrehozása magukba az egyedekbe lenne kódolva. Ez egy külön függvény, ami veszi a mama génjeit, a papa génjeit, kijelöl egy véletlen pontot a bináris sorozatban, ott elvágja, keresztezi a két “DNS“-t, és máris kész az új egyed.
Ez a kérdés rávilágított egy hibára a programban. Minden új egyedben a DNS első fele biztosan a mamától, a második fele pedig biztosan a papától származik, pedig ezt randomizálni kellene…

Röviden: ivaros szaporodást modellez a program (minden egyed hermafrodita), egyetlen ponton keresztezve a DNS-t. De az utód létrehozása sem része az alap programnak, ezt is a felhasználó írhatja meg, ha csak a mama “DNS“-ét használja fel akkor lényegében az osztódásos szaporodást lehet modellezni.

Hogyan mutálnak?

A beállított mutációs ráta a “DNS” minden bitjére vonatkozik. Végigmegy a függvény minden biten, generál egy véletlen számot 0 és 1 között, ha ez kisebb mint a mutációs ráta, akkor invertálja az adott bitet.
Új egyed létrehozásakor a crossover után hívódik meg a mutációs függvény.

Hogyan hat rájuk a szelekció?

Súlyozott rulettkerék szelekciót használtam. Van többféle megoldás is, például kiválogathatnám mindig az első 10 legjobb egyedet, és csak azoknak engedném meg a szaporodást, ez lenne az elitista stratégia. Ez gyorsabban konvergál, de nagyobb eséllyel ragad be lokális minimumhelyre.
A súlyozott rulettkerék szelekció úgy működik, hogy minden egyed a fitneszével súlyozva kap esélyt a szaporodásra. Ha mondjuk 4 egyednél a fitneszek összege 1, és egyedenként: 0.4, 0.3, 0.25, 0.05, akkor az első egyednek 40% esélye van a szaporodásra, az utolsónak meg 5%. Generálok egy véletlen számot 0 és 1 között, ha a 0-0.4 intervallumba esik, akkor az első egyedet választom mamának, ha a 0.4-0.7 intervallumba akkor a másodikat, stb. stb. (Arra nem figyelek, hogy ne legyen vérfertőzés, tehát lehet hogy ugyanaz az egyed lesz a mama és a papa is.)

Van egy kapcsoló, ami a ragadozót kapcsolja be. Hogyan működik a ragadozó, mi alapján ejt zsákmányt?

Ez egy túlegyszerűsített ragadozó, igazából ugyanaz történik, mintha a fenotípus színét állítanád át. (Csak itt a háttérszínhez fognak hasonlítani egy idő után az egyedek.) Arra jó ez a gomb, hogy ha már van egy populációd, ami viszonylag homogén, és hirtelen megjelenik egy ragadozó, akkor látni lehet, hogy mennyi idő alatt tud elterjedni egy új, hasznos mutáció. Ez nálam mindig több időt vett igénybe, mint egy adott fenotípus kitenyésztése.

A háttér hogyan befolyásolja az eredményt? A ragadozó sikere függ a háttér színétől?

Mondhatjuk azt, hogy a rejtőszíntől nagyon eltérő egyedeket fogja megenni. De mivel maga a ragadozó nincs rendesen szimulálva, így igazából nincs jó válaszom erre a kérdésre.
Majd elgondolkozom még azon, hogyan lehetne két különálló populáció koevolúcióját jól szimulálni, beleértve a ragadozók sikerességét is, de ez jelenleg nincs megvalósítva.

Milyen változtatásokat szeretnél még beépíteni?

Bármilyen javaslatot szívesen fogadok, amivel a biológiai evolúcióhoz jobban hasonlító rendszert lehetne készíteni.
A baj az, hogy csak ilyen túlegyszerűsített modellek esetén lesz gyors a futtatás, ha egy valós mérnöki probléma megoldására használnám, mondjuk egy repülőgép szárnymodell kifejlesztésére, akkor a fitness kiértékelése lényegében azt jelentené, hogy a “DNS”-ben tárolt adatokból létre kell hozni a szárny 3D-s modelljét, beletenni a szélcsatorna szimulációs programba, ezt megismételni a populáció minden egyedére, a kapott eredmények alapján csökkenő sorrendbe rendezni az egyedeket, majd ezekből szelektálni és új generációt létrehozni.
A kiértékelés módja miatt lassúak általában a genetikus algoritmusok, a szelekció, crossover, és mutáció megvan egy pillanat alatt, csak a fitness számítása függ a modell bonyolultságától.

Egyébként a szoftver open source, gpl3 licenszel, bárki letöltheti a forrást, és átírhatja kedve szerint. Maga a genetikus algoritmus csak a szelekciót végzi el, illetve meghívja a felhasználó által definiált dns generáló, mutáció, crossover, és fitnesz kiértékelő függvényeket. A beépített példákat megnézve látható, hogy milyen függvényeket kell megvalósítani, és milyen formában kell az eredményt visszaadni.

Köszönöm a válaszokat!

Update: Egyvalami kimaradt, a válaszaimból is, meg a programból is. Akartam egy olyan funkciót is, hogy az optimális fenotípus elérésekor megálljon, és vissza lehessen lapozni egyesével az összes generációt. Ez sajnos nem került bele, mert eszméletlen sok memóriát zabált firefoxon, pedig utánaszámolva nem olyan sok az az adat, amit tárolnia kellene. Még kísérletezek vele, és ha sikerül használható megoldást találnom, akkor azt mindenképpen belerakom.
Ez a generációnkénti visszalapozás főleg az értelmes mondatot előállító programnál lenne fontos. Dawkins weasel programját is amiatt támadják, hogy a háttérben nem csinál mást, mint hogy a sikeresen megtalált karaktereket berögzíti, amik aztán soha többet nem módosulhatnak, így folyamatosan növeli a véletlenszerű keresés sikerének esélyét.
Azt kellene észrevennie a kritikusoknak, hogy itt nem egyetlen karaktersorozatot módosítgat az algoritmus. Minden lépésben egy teljes populációt tárol, aminek az egyedei között az idő előrehaladtával egyre több lesz az olyan, amelyik hasonlít a futtatás elején megadott fenotípusra. De ezek között az egyedek között lesz elég sok olyan, amelyeknél egy korábbi jól megtalált karakter helyén valami teljesen más betű van. A teljes populációból itt csak a legnagyobb fittnesszű egyed kerül megjelenítésre. Sok futtatás során lehet találni olyan eseteket is, amikor két egymást követő generációban egy karakter “elromlik”, de két másik viszont “kijavul”.
Nincs semilyen “reteszelő mechanizmus” a programban. Sem a Dawkins által írt weaselben, sem az enyémben. A “kromoszómák” minden egyes bitjére vonatkozik a mutációs ráta, azaz minden bitnek azonos esélye van arra, hogy invertálódjon. A “reteszelő mechanizmus” maga az evolúció.