Genetikus algoritmusok megvalósítása Mathematica segítségével

Sárádi András E4AZ55
BME VIK Müszaki Informatika szak

A genetikus algoritmusok a természetben megfigyelhető evolúciós mechanizmusra épülő optimalizálásra és keresési problémákra alkalmazható módszerek.

Példánkban egy [0,1] intervalumnba eső valós számot próbálunk optimlizálni megadott fitneszfüggvény szerint.

Kromoszóma

A probléma szempontjából lényeges tulajdonság maga a valós szám, ennek az algoritmus számára megfelelő reprezentációja a kromoszóma, amelyet általában egy bitsztringgel valósítunk meg. Mathematicában erre legalkalmasabba bitek listája.  A kromoszóma méretét az alábbi változóban rögzítjük:

chromosomeLength = 10;

Szükségünk van egy, a kiválasztott lényeges tulajdonságot - jelen esetben egy valós számot - a megfelelő reprezentációba - jelen esetben bitsztring - átalakító fügvényre.

Clear[FloatToBitstring];
FloatToBitstring[
        x_] := 
Module[{tmp}, 
tmp = 
          RealDigits[x, 2]; 
Take[
          Join[Table[0, {-tmp[[2]]}], tmp[[1]], 
            Table[0, {chromosomeLength}]], 
          chromosomeLength]
]

A beépített RealDigits eljárás a bináris tört számot bináris normál alakban adja vissza, nekünk azonban a megfelelő reprezentációhoz szükségünk van a lista elejére kerűlő nullákra is.

c1 = FloatToBitstring[0.123]

Mivel a fitneszfüggvénytől nem várhatjuk el, hogy közvetlenül a bitsztringet értékelje ki, ezért szükség van a kromoszómát az eredeti tulajdonsággá visszaalakító függvényre.

Clear[BitstringToFloat];
BitstringToFloat[bitstring_] := 
Module[{i}, 
        N[Sum[bitstring[[i]]*2^(-i), {i, 
              Length[bitstring]}]]
]

BitstringToFloat[c1]

Genetikus operátorok

Az új generáció populációját az előző generáció egyedeiből a genetikus operátorok együttes, egymás utáni, esetenként többszöri alkalmazásával állítjuk elő

Mutáció

Mutációs ráta egy, bit átállítódásának valószínűsége

mutationRate = 0.002;

A mutáció egy megvalósítása döntően imperatív eszközökkel a következő:

Clear[Mutation];
Mutation[bstr_] := 
      Module[{tmp, i}, 
        tmp = bstr; 
Do[
          If[Random[] < mutationRate, tmp[[i]] = 1 - tmp[[i]]], {i, 
            Length[bstr]}]; 
tmp
]

A mutáció egy megvalósítása döntően funkcionális eszközökkel a következő:

Clear[Mutation];
Mutation[bstr_] := 
      Module[{}, 
Map[
          If[Random[] < mutationRate, 1 - #, #] &, 
          bstr]
]

c1
tmR = mutationRate;
mutationRate = 0.5;
Mutation[c1]
mutationRate = tmR;

Egypontos keresztezés

Ezen a ponton meg kell kötnünk, hogy a populáció csak azonos hosszúságú kromoszómákból áll, és az egyes generációk során ez nem változik. Így kijelőlve egy vágási pontot a két azonos hosszúságú szakaszt kicserélhetjük.

Clear[SingleCrossover];
SingleCrossover[ {bstr1_, bstr2_} ] := 
Module[{bstrlen,cutpoint,tmp1,tmp2},
	bstrlen = Length[bstr1];
	cutpoint = Random[Integer, {1,bstrlen-1}];
	tmp1 = Join[ Take[bstr1, cutpoint],
		Drop[bstr2, cutpoint] ];
	tmp2 = Join[ Take[bstr2, cutpoint],
		Drop[bstr1, cutpoint] ];
	{tmp1, tmp2} 
]

c1
c2 = FloatToBitstring[0.564]
p = SingleCrossover[{c1, c2}];
p[[1]]
p[[2]]

Szelekció

A szelekció során, adott fitnesz függvény alapján eldöntjük, hogy a majdani új populáció mely egyedek leszármazottaiból alakuljanak ki. 
A szelekcióban jelen esetben az ugynevezett rulettkerék kiválasztást alkalmazzuk. Ennek során a szülőpopuláció úgy választjuk ki egyesével az egyedeket, hogy a kiválasztás valószínűsége az egyed jósági mértékével, vagyis az egyed fitneszértéke a populáció átlagosfitneszértékével vett normáltjával arányos.

Clear[Selection];
Selection[fitnessfunction_, pop_] := 
      Module[
{selectedPopulation, 
fitnessList,  
normalizedFitnessList, 
rouletteWheel
}, 
fitnessList = 
          Map[fitnessfunction[BitstringToFloat[#]] &, 
            pop]; 
normalizedFitnessList = 
          Map[#/(Fold[Plus, 0, fitnessList]) &, 
            fitnessList]; 
rouletteWheel = 
          Table[
{Fold[Plus, 0, 
                Take[normalizedFitnessList, {1, i - 1}]], 
              Fold[Plus, 0, Take[normalizedFitnessList, {1, i}]], 
              pop[[i]]}, {i, 
              Length[pop]}
]; 
SelectByDraw[RW_] := 
          Module[{ball, sel}, 
ball = 
              Random[]; 
Select[RW, 
                IntervalMemberQ[Interval[{#[[1]], #[[2]]}], 
                    ball] &][[1, 
                3]]
]; 
selectedPopulation = 
          Table[SelectByDraw[rouletteWheel], {i, 
              Length[pop]}]
]

A populáció méretét a populationSize változóban rögzítjük

populationSize = 30;

Population = 
        Map[FloatToBitstring, 
          Table[Random[], {populationSize}]];
sampleFitnessFunction[
          x_] := -32 x (x - 1);
Plot[sampleFitnessFunction[x], {x , 0, 1}]

Selection[sampleFitnessFunction, Population]

Reprodukció

Az új generáció alapját a selekcióval előállított átmeneti populácó adja. Ebből kiindulva jön létre az utódgeneráció, mely az átmeneti populációra alkalmazott genetikus operátorok eredményéből született egyedek populációja.

Population

Clear[Reproduction];
Reproduction[pop_] := 
        Module[{tmp1pop, tmp2pop, 
            newPopulation}, 
tmp1pop = 
            Flatten[Table[ 
SingleCrossover[
                  SingleCrossover[{
pop[[Random[
                            Integer, {1, 
                              populationSize}]]], 
pop[[Random[
                            Integer, {1, 
                              populationSize}]]]
}] ], 
{i, populationSize/2}
], 
              1]; 
tmp2pop = 
            Map[Mutation, tmp1pop]; 
newPopulation = 
            Selection[sampleFitnessFunction, 
              tmp2pop]; 
newPopulation
];

Reproduction[Population]

Fold[Reproduction[#1] &, Population, 
      Range[20]]
Map[BitstringToFloat, %]

Látható, hogy az egyedek többsége beáll a fitnesz függvény maximumának helyére, aza 0.5 környékre. Ha azt tapasztalnánk, hogy a rendszer lokális minimumban ragad az egy konkrét feladatban, akkor a mutációs ráta értékének növelésével ez elkerülhető. További lehetőség a hatékonyság növelésére az elitizmus alkalmazása a reprodukcióban, vagyis, hogy az új populáció egyedei nem csupán a genetikus operátorok által módosított kromoszómák. Az új populóció ekkor a régi egyedekkel megegyező egyedeket is tartalmaz.

Alakalmazások

A módszer alkalmazásásnak feltétele, hogy az adott problémára megfelelő reprezentációt tudjunk találni, valamint alkalmas feltételek és fitnesz függvény tudjunk találni. A [1] forrásban megemlítik a hálózatoptimalizálásban betöltött szerepét, ahol az kromoszóma az útvonalválasztást reprezentálja, a költségfüggvény pedig az utvonalon lévő kapcsolóállomások alapján számolható. Szintén alkalmazható a módszer órarendoptimalizálásra. Itt büntető jellegű fitneszfeltételeket fogalmaznak meg, de adott esetben elfogadhatatlan megoldást reprezentáló egyedeket teljesen ki is zárják a populációból. A lyukas órák számával arányosan lehet bünteteni az egyedet.

Felhasznált irodalom, segédanyagok:

[1] Álmos A. - Győri S. - Horváth G. - V. Kóczy A.: Genetikus algoritmusok, TYPOTEX, Budapest, 2222.

http://www.typotex.hu/book/m_0068.htm

[2] Mats Bengtsson: Genetic Algorithms

http://library.wolfram.com/infocenter/MathSource/569/