Genetikus algoritmust szeretnék írni, ami megoldja a snakehez hasonló játékomat, de nem tanul semmit. Mit tegyek, hogy menjen?

Ez tipikus hiba, hogy valami tanuló algoritmussal próbálnak megoldani valamit, amire van jól bejáratott, hatékony, determinisztikus gráfalgoritmus.

Ha az a cél, hogy a 2-eseket gyűjtsük a pályán, úgy hogy közben a kígyó nem harap a farkába és nem megy neki a falnak, akkor ez egy sima útkeresés a kígyó fejétől a 2-esig a pálya implicit gráfján. Egy cellából léphetsz akármelyik szomszédosra, kivéve ha ott fal vagy kígyó van vagy kilépnénk a pályáról. Ezt flood fill vagy breadth-first search algoval szokták kezelni ilyen játékokban.

Alapvetoen jo iranyba indultal el. Viszont van par algoritmus (es a genetikus pl. tipikusan ilyen), amiben ha van egy bug, akkor vert izzadva talalod csak meg. Miutan az alapelv, amit leirtal, jo, igy valoszinubb a bug.

Ha valaki kifejezetten a neuralis halot akarja genetikus algoritmussal vegyiteni, van egy nagyon jo algoritmus, a NEAT, hatekony, de eleg nehez implementalni. Tovabbi elonye, hogy nem neked kell kitalalnod, hogy hany reteged es azokban hany neuronod legyen, mert ezeket o talalja ki az evolucioval. (persze ehhez is van mindenfele library, meg konvolucios reteggel ellatott is, abbol viszont nem tanulsz)

Ha sima tobbretegu perceptront akarsz hasznalni, ahol a sulyok vannak a "DNS"-edben kodolva, az is mukodik. Kevesbe lesz hatekony, lassabban tanul, de menni fog.

Az uj generacio letrehozasa tobb modon is mehet, igazabol ha par alapszabalyt betartasz, akkor mar menni fog valamennyire. A legelterjedtebb talan az, hogy a regi generaciot fitness szerint sorba rendezed, a fitnessel sulyozottan veletlenszeruen valasztasz 1-1 part, a parokat keresztezed, mutalod, es ezekkel toltod fel a kovetkezo generaciot (aminek megtalalod a fitness erteket a szimulacioddal, aztan keresztezed, mutalod, stb..)

Volt egy faek egyszerusegu (talan kevesbe hatekony) modszer is: kivalasztasz a populaciodbol 2 elemet veletlenszeruen, megnezed a fitness ertekeit, a kettot keresztezed, mutalod, az uj egyedet meg beteszed a rosszabb fitness erteku elem helyere. Tokeletesen mukodik ez is, bar itt a generaciok nem kulonulnek el annyira egymastol.

A keresztezes mehet tobb modon, a legjobb, ha elkezded a ket egyed kozul veletlenszeruen az egyikkel, a genjeit egymas utan elkezded az eredmenybe masolni, es minden egyes gen utan valamilyen random (kis) valoszinuseggel valtasz a ketto kozott. Ugye itt a genek egy neuralis halo sulyait kodoljak, szoval ha a halo strukturaja nagyjabol egyben marad, az az elonyos. Ezert jobb, ha hosszabb lancokat kap az utod, es nem innen-onnan egy-egy elemet. Amugy akar mar az is mukodhet, ha 0 es hossz kozott valasaztasz egy szamot veletlenszeruen, es az egyik felet az egyik, masikat a masik szulotol kapja. Ez is mukodni fog.

A mutacio meg annyi, hogy vegigmesz az osszesen, es valami kis valoszinuseggel (mondjuk 0.1%-kal) megvaltoztatod az ott talalhato erteket. Kicsit trukkosebb implementaciok az elejen nagyobb mutacios erteket adnak, es kesobb lecsokkentik (vagy ha megallt a fitness ertekek javulasa, akkor megint meg lehet novelni).

Ahhoz, hogy az evolucio mukodjon igazabol arra van szukseg, hogy legyen kivalasztas (ez itt trivialisan teljesul), a tulajdonsagok valahogy oroklodjenek (keresztezes megoldja), es legyen a populacion belul variancia (kezdeti random, ill. a kesobbi mutacio gondoskodik rola). A konkret szabalyok csak a tanulas sebesseget fogjak valtoztatni, igy dol el, hogy hany milliard ev alatt jon letre egy ember bonyolultsagu valami.

Inkabb itt valaszolok, mert ide kapcsolodik, es ezt mas is latja.

A programnyelvet azert kerdeztem, mert par eve irtam egy ilyet PHP-ban (a progi mas reszei mar abban voltak, nyilvan nem idealis szamitasi ido szempontjabol), ill. Pythonban terveztem egy altalanosabbat.

Ha a C++ ismeros, akkor gondolom a PHP olvasasa sem fog nehezseget okozni, par helyen van benne a C++-hoz kepest plusz dollarjel, aztan ennyi. Ja, tombbe uj elemet be lehet illeszteni a $tombnev[]=$uj_elem; kifejezessel (ekkor o talalja ki az uj elem indexet, a tombok nem fix meretuek, kb. mint az STL-es adatszerkezetek, a legjobban a hashmap-re hasonlit)

A DNA::getRand01() egy olyan fuggvenyem, ami a 0..1 intervallumbol ad egy random erteket. A tobbi sztem a nevebol kitalalhato.

A relevans reszek:

public function createNextPop()

{

$newpop=array();

$newpop[]=$this->pop[0];

while(count($newpop)<$this->maxPop)

{

$a=$this->pop[$this->getRandIndex()];

$b=$this->pop[$this->getRandIndex()];

$c=$a->crossoverWith($b);

$newpop[]=$c;

}

return $this->pop=$newpop;

}

es amit hivogat:

public function getRandIndex()

{

$r=$this->fitnessSum*DNA::getRand01();

for($i=0;$i<$this->maxPop;$i++)

{

$f=max(0,$this->pop[$i]->getFitness());

if($r<=$f)

return $i;

$r-=$f;

}

return 0;

}

A lenyeg:

Tegyuk fel, hogy 100 egyedbol all a populacionk. Ugy hozunk letre egy uj, szinten 100 egyedbol allo populaciot, hogy a regit sorba rendezzuk (opcionalis), es 100 alkalommal valasztunk veletlenszeruen 1-1 indexet, a ket kivalasztott egyedet keresztezzuk, es ezt az uj egyedet illesztjuk be az uj populacioba.

Azert, hogy ne teljesen veletlenszeruen csinaljon mindenfelet az algoritmus, hanem a kivant fitness erteket idovel novelje, a veletlen kivalasztas nem teljesen veletlen: jobb fitness erteku egyedeket nagyobb valoszinuseggel valasztunk ki, megpedig pont a fitnessek aranyaban. Ha minden fitness ertek pozitiv (legalabbis nemnegativ), akkor ha 0 es a populacio fitness ertekeinek az osszege kozott valasztasz egy szamot, es az egyedeken vegiglepkedve pont kijon, hogy melyik egyed a szerencses.

pl: van egy 3 egyedbol allo populacionk, mondjuk A,B, es C, 6, 3 es 1 fitness ertekekkel. Ekkor ha egy 10-es dobokockaval dobunk (0-9 kozt szamozva), akkor 0-5 szamoknal az A-t (6-ost) valasztjuk, 6-8 szamoknal a B-t (3-ast), es 9-nel a C-t (1-est). Ha az uj populacionk is 3 egyed meretu lesz (ez amugy nagyon keves, csak nem akarok annyi szamot irni), akkor a kovetkezo lesz az eredmeny:

Dobtam 4-et, 5-ot, szoval az A-t keresztezem A-val, eredmenyt mutalom, beteszem az ujba. Utana dobtam 2-t es 8-at, szoval az A-t es a B-t keresztezem, mutalom, ez lesz az uj populacio 2. eleme. Megint dobtam, 4,6: szoval ismert az A-t es B-t keresztezem. Szoval az uj populacioba bekerul az A mutansa, meg az A-B ketfele mutansa, a C kiszelektalodott. Ha nem 3, hanem mondjuk 100 vagy 1000 egyedbol all a populacio, akkor 100 vagy 1000 part valasztunk a populaciobol az ismertetett modon.

A fenti kod kb. ezt valositja meg, annyi az elteres, hogy az uj populaciot a (rendezett) populacio 0. elemevel kezdem, szoval a valaha volt legjobban teljesito egyed mindenkepp bekerul az ujba is. (ez a sor: $newpop[]=$this->pop[0]; )

A fitness fuggvenynel meg azt celszeru figyelembe venni, hogy valami pozitiv egesz legyen az erteke. A talalt 2-esek szama+valami konstans peldaul mukodhet. Ha csak a talalt 2-esek szama lenne, akkor szerencsetlen esetben rogton kiesne az 1. generacio jelentos resze (semmit nem talal), ami a varianciat tulsagosan lecsokkenti. (ez ellen betehetsz a populacioba mindig adott szamu uj, teljesen random egyedet is, vagy a fitness fuggveny eredmenyet at lehet kuldeni valami nemlinearis, szig. monoton novekvo fuggvenyen, ami az extrem eseteket kiszuri)