GA - 8 kiralyno

1.
Ez a video azt mutatja be, hogyan kell a 8 kiralyno problemat megoldani genetikus algoritmus segitsegevel.

2.
Ebben a peldaban a populacio 6 egyedbol all, a kezdopopulaciot veletlenul hatarozzuk meg, es feltetelezzuk hogy oszloponkent egy kiralynot helyezunk el.

3.
A kiralynok veletlen lerakasaval a kovetkezo kezdopopulaciot kaptuk. Minden egyedet 8 szammal reprezentalhatunk, az 16256453 annyit jelent, hogy az elso oszlop kiralynoje az elso sorban van, a masodik oszlop kiralynoje a hatodik sorban, es igy tovabb.
A tablakat a kiralynokkel tobbet nem mutatjuk, ezutan csak a szamokkal dolgozunk.

4.
Fitneszfuggvenykent a nemtamado kiralynoparok szamat vesszuk, tehat minel nagyobb ez a szam, annal kevesebb a kiralynok kozotti tamadas es annal kozelebb all az adott egyed a megoldashoz. Ez annyit jelent hogy a celfuggvenyt makszimalizalni kell. A legrosszabb esetben amikor minden kiralyno tamad minden kiralynot, ennek a fuggvenynek az erteke 0 (0 par olyan kiralyno van amelyik nem tamadja egymast). A megoldast akkor talaljuk meg ha a celfuggveny erteke 28.

A kezdopopulacio kiertkelesevel kapjuk a nemtamado kiralynoparok szamat, ami sorra

23, 17, 22, 25, 23, 17

A celfuggveny populaciobeli atlagerteke 21.17.

5.
A skalazott fitneszeket ugy nyerjuk, hogy az egyes celfuggvenyertekeket elosztjuk az atlaggal. Ezek az ertekek
1.086, 0.803, 1.039, 1.181, 1.086, 0.803
Utana szazalekban is kifejezzuk az egyes egyedek josagat.
Lathatjuk, hogy a masodik es a hatodik egyednek van a legkisebb eselye a kivalasztasra, 13.4%, mig a legnagyobb eselye a negyedik egyednek van, 19.7%.
A szelekcio technikai megvalositasahoz ki kell meg szamitani a kummulativ valoszinusegeket is, ezt az utolso oszlop mutatja.

6.
Feltetelezzuk, hogy a kovetkezo egyedek lettek kivalasztva a genetikai muveletek vegzesere: 5, 1, 4, 3, 4, 6.

Ezek a kivalasztott egyedek kozott kerul sor a keresztezesre.

7.
Minden szulo-par reszere letre kell hozni egy veletlen szamot 1 es 7 kozott amelyik megmondja hogy melyik ertek utan vagjuk el a kromoszomakat. Mivel 3 szulo-par van, 3 veletlen szamot hozunk letre, legyenek ezek 2, 6 es 5. Az egyedek bal felet erintetlenul hagyjuk, a jobb felet pedig megcsereljuk.

8.
A rekombinacio utan meg csak a mutaciot kell elvegezni. Feltetelezzuk, hogy a mutacio valoszinusege genenket 6%, ami annyit jelent hogy 48 genbol 0.06*48=2.88~3 gen lesz kicserelve.
Az elso kromoszoma 3. genje mutalt 2-rol 7-re, a harmadik kromoszoma 6. genje mutalt 3-rol 1-re, es a hatodik kromoszoma 3. genje mutalt 4-rol 5-re.
Ha generacios cseret vegzunk, tehat nincs elitizmus, akkor elkeszult az uj generacio. 

9.
Vizsgaljuk meg az uj egyedek josagat.
Amint latjuk, az uj egyedek fitnesze 17 es 23 kozott mozog. Ismeteljuk meg, hogy a fitnesz a nemtamado kiralynoparok szamat jeloli, a megoldast akkor talaljuk meg ha az egyed josaga eleri a 28-at. Az uj populacio atlagos fitnesze 20.83, ami enyhe csokkenes az elozo populaciohoz kepest, ahol ez az ertek 21.17 volt. Az uj populacioban a legmagasabb fitnesz 23, mig a regi populacioban a legjobb egyed fitnesze 25 volt. Ha hasznaltuk volna az elitizmust, megmenthettuk volna az elozo generacio legjobb egyedet.
Amint latjuk, nincs garancia arra, hogy az algoritmus mindig jo iranyba fog haladni. A genetikus algoritmus a pozitiv hatasat valoszinuleg a kovetkezo lepesek egyike soran fejti majd ki.