1. Az elozo prezentacioban a genetikus algoritmusokkal ismerkedtunk meg, es bemutattuk hogyan kell megoldani a 8 kiralyno feladatot ennek a modszernek a segitsegevel. Ebben a ket uj videoban meg ket feladat megoldasat mutatjuk be a genetikai muveletek segitsegevel. Az elso a MAXONE ahol az a cel hogy a bitsztringben minel tobb 1-es legyen, a masik pedig egy fuggvenyoptimalizacio ahol 4 valtozo erteket keressuk ugy, hogy egy adott celfuggvenyt makszimalizaljunk. 2. A MAXONE feladat lenyege olyan bitsztringet letrehozni amelyikben az egyesek szama makszimalis. Ebben a peldaban az a cel hogy a tizbites bitsztringben minel tobb egyes legyen (lehetoleg 10). A populacio merete legyen 8, tehat inicializalaskor 8 darab 10-bites bitsztringet hozunk letre. A veletlenul generalt kezdeti populacio az abran van bemutatva. 3. A genetikus algoritmus elso lepese az egyedek kiertekelese. Mivel a cel olyan egyedeket letrehozni amelyekben az egyesek szama makszimalis, fitneszfuggvenykent eppen a bitsztringekben szereplo egyesek szamat vesszuk. Az egyedek celfuggveny-erteke a kovetkezo: 7, 5, 6, 6, 7, 2, 8, 4 Amint latjuk, a legnagyobb fitnesze a 7. egyednek van, mivel a lehetseges makszimalis 10 bitbol 8 mar 1-es. Legkisebb fitnesze a 6. egyednek van, csupan 2. 4. A kovetkezo lepes a skalazas, amelyik elokesziti a populaciot a szelekcio muveletere. Ahhoz eloszor meg kell hatarozni a populacio atlagos fitneszet. Tehat osszeadjuk a fitneszeket es elosztjuk 8-cal. Azt kapjuk hogy az atlagos fitnesz 5.625. EZT A SORT NEM KELL!!! atlagos fitnesz = (7+5+6+6+7+2+8+4)/8=5.625, tehat minden populaciobeli egyedben atlagosan 5.625 1-es van. Most az egyedek skalazott fitneszet ugy nyerjuk hogy a megfelelo fitneszeket elosztjuk az atlagos fitnesszel. A skalazott fitneszertekek az abran lathatok. skalazott fitnesz = 1.24 0.89 1.07 1.07 1.24 0.35 1.42 0.71 A skalazott fitnesz ertekek osszege meg kell hogy egyezzen az egyedek szamaval a populacioban, ami 8. Igy akar le is ellenorizhetjuk, hogy jol szamoltunk-e. 5. A kovetkezo lepes a szelekcio, illetve a kivalasztas. Szelekcios modszerkent a fitneszaranyu rulettkerek szelekcios modszert alkalmazzuk (angolul roulette wheel, fitness based). A skalazott fitneszek alapjan eloszor ki kell alakitani a fitneszkereket, es meghatarozni hogy minden egyednek mekkora terulet felel meg a fitneszkereken belul. A legnagyobb valoszinusege a kivalasztasra termeszetesen a 7. egyednek lesz amelyiknek a fitnesze 8, legkisebb eselye a kivalasztasra pedig a 6. egyednek amelyiknek a fitnesze 2. Az egyedeknek megfelelo teruletek nagysagat szazalekban ugy hatarozzuk meg, hogy a skalazott fitneszt elosztjuk 8-cal. Az elso egyed kivalasztasanak valoszinusege 15.5%, a masodike 11.1%, es igy tovabb. szazalek = 15.5 11.1 13.4 13.4 15.5 4.3 17.7 8.9 6. A reszaranyos rulettkerek a kovetkezo abran lathato. A genetikai muveletekben resztvevo egyedeket a rulettkerek kepletes forgatasaval nyerjuk. A forgatasok szama megegyezik a populacio meretevel, tehat 8-szor fog megtortenni. A forgatasok egymastol fuggetlenek. 7. A valosagban azonban a fitneszkereket maskepp oldjuk meg. Elkeszitjuk a szazalekban meghatarozott fitneszertekek kummulativ szummajat, amelyik a tablazat utolso oszlopaban lathato. EZT NEM!!!kummulativ szumma: 0.155 0.266 0.400 0.534 0.689 0.732 0.909 1.000 A kivalasztas ugy tortenik hogy letrehozunk egy veletlen szamot 0 es 1 kozott. Ha a veletlen szam 0 es 0.155 kozott van, akkor az 1. egyedet valasztjuk, ha a veletlen szam 0.155 es 0.266 kozott van akkor a masodik egyedet valasztjuk, ha pedig a veletlen szam 0.909 es 1 kozott van, az utolso, 8. egyedet valasztjuk. Ezt az eljarast 8-szor ismeteljuk meg. 8. Feltetelezzuk, hogy a 8 veletlen szam 0.612, 0.382, 0.178, 0.845, 0.132, 0.756, 0.596, 0.449. Akkor a kovetkezo egyedek lesznek szelektalva: 5,3,2,7,1,7,5,4. Amint latjuk, a legnagyobb fitnesszel rendelkezo 7. egyed ketszer kerult kivalasztasra, akarcsak az 5. egyed. A ket leggyengebb fitneszu, a 6. es a 8. egyszer sem lett kivalasztva. 9. A kovetkezo lepes a rekombinacio, illetve keresztezes. Az egyedeket parosaval vesszuk, es ket kivalasztott egyedbol ket masik egyedet hozunk letre. A keresztezes is valamilyen valoszinuseggel tortenik, ebben a peldaban viszont azt feltetelezzuk, hogy a keresztezes a szulok kozott minden alkalommal megtortenik. A keresztezes arra szolgal hogy az egyedek egymas kozt kicsereljek a genetikai tulajdonsagait. Ez tobbfelekeppen tortenhet. Letezik egypontos, ketpontos es n-pontos keresztezes, ebben az esetben a legegyszerubb egypontos mellett dontunk. Ket szulokromoszomat ugy rekombinalunk, hogy meghatarozunk egy veletlen szamot 1 es 9 kozott, ez lesz az a pont ahol a szulokromoszomakat "elvagjuk". Ezutan a kromoszomak bal felet megtartjuk, a valasztovonal jobb oldalan levo reszt pedig felcsereljuk. Ez a kovetkezo abran van bemutatva. Mivel 8 szulo van, a szuloket pedig kettesevel parositjuk, osszesen 4 darab 1 es 9 kozotti szamra lesz szuksegunk. Feltetelezzuk, hogy ezek a szamok 2, 6, 4 es 7. 5. 11 | 11101100 3. 00 | 11010111 2. 101100 | 1010 7. 011111 | 0111 1. 1101 | 001111 7. 0111 | 110111 5. 1111101 | 100 4. 1110111 | 000 10. A kromoszomak jobb oldali reszenek felcserelese utan az egyedek a kovetkezok lesznek: 1111010111 0011101100 1011000111 0111111010 1101110111 0111001111 1111101000 1110111100 11. A kovetkezo lepes a mutacio amelyik a kromoszoma valamelyik bitjet (illetve genjet) veletlenszeruen megvaltoztatja. Feltetelezzuk hogy a mutacionak a valoszinusege 4%, ami a teljes populacion annyit jelent hogy 80*0.04=3.2 ~ 3 bit lesz megvaltoztatva. A mutacio bitenkent fejti ki hatasat, tehat minden bit 4%-os valoszinuseggel lesz megvaltoztatva. Feltetelezzuk hogy a kovetkezo 3 bit ertke valtozik: (2. egyed 4. bit 1-0, 3. egyed 5. bit 0-1 es 5. egyed 3. bit 0-1). 1111010111 0010101100 1011100111 0111111010 1111110111 0111001111 1111101000 1110111100 12. Ezzel elkeszult az uj generacio ahol a fitneszek a kovetkezok: 8, 4, 7, 7, 9, 7, 6, 7. Azt tapasztalhatjuk, hogy az atlagos fitnesz megnovekedett 5.625-rol 6.875-re. Ez a jelentos javulas a genetikai muveletek hatasa miatt tortent. 13. Az utolso lepes a reprodukcio. Most dontjuk el hogy a teljes generaciot lecserljuk-e, vagy a regi generaciobol meghagyunk valamennyi egyedet? Ebben a peldaban az elitizmus aranyat 10 szazalekra hatarozzuk meg, ami annyi mint 0.8, kerekitve pedig 1. Tehat a regi generacio legjobb egyede nem veszik el, hanem atkerul az uj generacioba a leggyengebb fitneszu egyed helyere. Az uj generacioban a leggyengebb fitnesze a masodik egyednek van (4), ennek helyebe jon az elozo generacio legjobb egyede, a 0111110111, melynek fitnesze 8. Ezutan letrejott az uj generacio vegso valtozata: 1111010111 0111110111 1011100111 0111111010 1111110111 0111001111 1111101000 1110111100 Az elitizmus miatt az atlagos fitnesz meg valamennyivel novekedett, erteke most 7.375. Ezek utan az egesz ciklus ujraindul. A vegrehajtando generaciok szama a kilepesi kriteriumtol fugg.