GA optim

1.
Ebben a videoban egy tobbvaltozos fuggvenyt probalunk optimalizalni.

2.
Adott a kovetkezo fuggveny: a+2b+3c+4d=30
A feladat genetikus algoritmussal meghatarozni az a, b, c es d erteket ugy, hogy az eredmeny minel kozelebb keruljon 30-hoz. Eloszor hatarozzuk meg az optimalizalni kivant fuggvenyt, ez lesz az 

f=a+2b+3c+4d-30

A megoldast akkor talaltuk meg ha az f erteke 0-ra csokken. Az egyszeruseg kedveert feltetelezzuk, hogy a, b, c es d erteke egesz szam, es a (0, 30) tartomanybol van.
A populacio merete legyen N=6, es minden populaciobeli egyed 4 egesz szamot fog tartalmazni 0 es 30 kozott.

Az algoritmus hasonlo mint a MAXONE feladatnal, de vannak kulonbsegek is. A MAXONE feladat binaris 0,1 ertekekkel dolgozott, ebben az optimalizacios peldaban pedig decimalis szamok szerepelnek.
A masik kulonbseg a fitneszfuggvenyben van. A MAXONE feladatnal a nagyobb fitnesz jobb egyedet jelentett, ebben a peldaban viszont a cel az f fuggvenyt minimalizalni, tehat az egyed annal jobb minel kisebb a fitnesze.

3.
Az elso lepes persze a veletlen kezdopopulacio inicializalasa. Hat egyedet (illetve kromoszomat) hozunk letre, kozuluk mindegyik 4 darab 0 es 30 kozotti szambol all. Itt lathatjuk a populaciot.

K1=[12, 05, 23, 08]
K2=[02, 21, 18, 03]
K3=[10, 04, 13, 14]
K4=[20, 01, 10, 06]
K5=[01, 04, 13, 19]
K6=[20, 05, 17, 01]

A kovetkezo lepes az egyedek kiertekelese a celfuggveny alapjan.

f_1 = 1*12 + 2*5 + 3*23 + 4*8 - 30 = 93
f_2 = 1*2 + 2*21 + 3*18 + 4*3 - 30 = 80
f_3 = 1*10 + 2*4 + 3*13 + 4*14 -30 = 83
f_4 = 1*20 + 2*1 + 3*10 + 4*6 - 30 = 46
f_5 = 1*1 + 2*4 + 3*13 + 4*19 - 30 = 94
f_6 = 1*20 + 2*5 + 3*17 + 4*1 - 30 = 55

Ennek a fuggvenynek az ertekei 46 es 94 kozott mozognak, ne felejtsuk el hogy a kisebb ertek jelent jobb egyedet, amelyiket nagyobb valoszinuseggel kell szelektalni. 

4.
Most meghatarozzuk az egyedek fitneszet, illetve hogy szazalekban mekkora az egyedek eselye a kivalasztasra. Erre a kovetkezo kepletet hasznaljuk

fitnesz_1 = 1/(1+f_1)

A nevezoben azert adtunk hozza 1-et a celfuggvenyhez hogy elkeruljuk az esetleges nullaval valo osztast.

fitnesz_1 = 1/94 = 0.0106
fitnesz_2 = 1/81 = 0.0123
fitnesz_3 = 1/84 = 0.0119
fitnesz_4 = 1/47 = 0.0213
fitnesz_5 = 1/95 = 0.0105
fitnesz_6 = 1/56 = 0.0179

A fitneszek osszege 0.0845.

5.
Az egyes kromoszomak kivalasztasanak valoszinusege:

P[1] = 0.0106 / 0.0845 = 0.1254
P[2] = 0.0123 / 0.0845 = 0.1456
P[3] = 0.0119 / 0.0845 = 0.1408
P[4] = 0.0213 / 0.0845 = 0.2521
P[5] = 0.0105 / 0.0845 = 0.1243
P[6] = 0.0179 / 0.0845 = 0.2118

A valoszinusegek alapjan latjuk, hogy a 4. kromoszomanak (amelyiknek a legnagyobb a fitnesze) van a legnagyobb eselye a kivalasztasra. Szelekcios modszerkent ismet a fitneszaranyos rulettkerek kivalasztast alaklmazzuk. 

6.
Ehhez ki kell szamolni a kummulativ valoszinusegeket.

C[1] = 0.1254
C[2] = 0.1254 + 0.1456
     = 0.2710
C[3] = 0.1254 + 0.1456 + 0.1408
     = 0.4118
C[4] = 0.1254 + 0.1456 + 0.1408 + 0.2521
     = 0.6639
C[5] = 0.1254 + 0.1456 + 0.1408 + 0.2521 + 0.1243
     = 0.7882
C[6] = 0.1254 + 0.1456 + 0.1408 + 0.2521 + 0.1243 + 0.2118
     = 1.0

7.
A kivalasztas 6 darab fuggetlen veletlen szam letrehozasaval tortenik a (0,1) intervallumbol. Legyenek ezek a veletlen szamok: 

0.201   0.284   0.099   0.822   0.398   0.501

Ha a veletlen szam a 0-0.1254 intervallumbol van, az elso kromoszoma kerul kivalasztasra, ha ez a szam 0.1255 es 0.2710 kozott van, akkor a masodik kerul kivalasztasra, es igy tovabb. A veletlen szamok alapjan belathatjuk hogy a 2., 3., 1., 6., ujra a 3. es vegul a 4. kromoszomakat valasztotta ki az algoritmus. 

8.
Ezert az uj kromoszomak:

K1=[02, 21, 18, 03]
K2=[10, 04, 13, 14]
K3=[12, 05, 23, 08]
K4=[20, 05, 17, 01]
K5=[10, 04, 13, 14]
K6=[20, 01, 10, 06]

9.
Kovetkezik a keresztezes. Ugyanugy ahogy a MAXONE feladatnal is felteteleztuk, a keresztezes minden szulopar kozott letrejon, tehat a K1-et a K2-vel, a K3-at a K4-gyel, a K5-ot pedig a K6-tal parositjuk. Meg csak azt kell eldonteni hogy melyik pontban vagjuk el az egyes szuloparokat. Ezt is egy veletlen szam donti el amelyik 1 es 3 kozott van. Mivel 3 szulopar van, 3 veletlen szamot hozunk letre, ezek az 1, 1 es 2. Ez annyit jelent, hogy az elso es a masodik szuloparat az 1., a harmadik szuloparat pedig a masodik gen utan vagjuk el. Ezt lathatjuk az abran is.

K1=[02, |  21, 18, 03]
K2=[10, |  04, 13, 14]

K3=[12, |  05, 23, 08]
K4=[20, |  05, 17, 01]

K5=[10, 04, |  13, 14]
K6=[20, 01, |  10, 06]

10.
A szulokromoszomak bal oldalat erintetlenul hagyjuk, a jobb oldalakat pedig felcsereljuk. Ezutan az utodok a kovetkezok:

K1=[02, 04, 13, 14]
K2=[10, 21, 18, 03]

K3=[12, 05, 17, 01]
K4=[20, 05, 23, 08]

K5=[10, 04, 10, 06]
K6=[20, 01, 13, 14]

11.
A kovetkezo lepes a mutacio. Azt hogy mennyi gen valtoztatja meg veletlenul az erteket a mutacios rataval hatarozzuk meg. A mutaciot ugy vegezzuk, hogy egy veletlen helyen a gen-t uj ertekre valtoztatjuk. Eloszor meghatarozzuk a genek szamat a populacioban, ez 6*4=24. Feltetelezzuk, hogy a mutacio valoszinusege genenkent 10%. Ez annyit jelent, hogy az egesz populacioban 0.1*24=2.4~2 gent valtoztatunk meg. A mutacio a 4. kromoszoma utolso genjet valtoztatta meg 8-rol 2-re, es a 6. kromoszoma 3. genjet 13-rol 5-re.

K1=[02, 04, 13, 14]
K2=[10, 21, 18, 03]
K3=[12, 05, 17, 01]
K4=[20, 05, 23, 02]
K5=[10, 04, 10, 06]
K6=[20, 01, 05, 14]

Amennyiben a reprodukcional nem alkalmazzuk az elitizmust, hanem generacios cseret vegzunk, akkor megkaptuk az uj populaciot. Ha a kilepesi feltetel ki van elegitve, akkor az algoritmus itt be is befejezodik. Ellenkezo esetben az egesz folyamatot ujrakezdjuk. 

12.
Vizsgaljuk meg hogy milyen hatassal voltak a genetikus muveletek a populaciora. Az uj populacioban szereplo kromoszomak fitnesze a kovetkezo:

f_1 = 1*2 + 2*4 + 3*13 + 4*14 - 30 = 75
f_2 = 1*10 + 2*21 + 3*18 + 4*3 - 30 = 78
f_3 = 1*12 + 2*5 + 3*17 + 4*1 -30 = 47
f_4 = 1*20 + 2*5 + 3*23 + 4*2 - 30 = 77
f_5 = 1*10 + 2*4 + 3*10 + 4*16 - 30 = 82
f_6 = 1*20 + 2*1 + 3*5 + 4*14 - 30 = 63

Az inicialis populacional a celfuggveny ertekei 46 es 94 kozott mozogtak, ennel a fuggvenynel 47 es 82 kozott vannak. A celfuggveny atlagos erteke enyhen csokkent, tehat az algoritmus, kis lepessel ugyan, de jo iranyba halad. Az uj kromoszomak felett ugyanazokat a genetikus muveleteket fogjuk elvegezni mint az elozo populacion amig a kilepesi feltetel nem teljesul. 

13.
A feladat lehetseges megoldasai:
a=7, b=5, c=3, d=1, vagy
a=1, b=2, c=3, d=4.
Ezenkivul leteznek mas megoldasok is.

Belathatjuk, hogy a genetikus algoritmus altal megtalalt megoldas kielegiti az egyenloseget.