Genetikus algoritmusok az optimalizálásban

Genetikus algoritmusok az optimalizálásban --- Házi dolgozat ---

Raffai Tamás – I. Programtervezı Matematikus

-2-

Tartalomjegyzék 1

Bevezetı........................................................................................................................ - 4 1.1 1.2

2

Mi az a genetikus algoritmus?............................................................................... - 4 Hogyan alakult ki? ................................................................................................ - 4 -

Definíciók, alapfogalmak ............................................................................................ - 6 2.1 Egyed, egyedek reprezentációja ............................................................................ - 6 2.1.1 Bitsorozat ...................................................................................................... - 6 2.1.2 Vektor............................................................................................................ - 6 2.1.3 Permutáció..................................................................................................... - 6 2.2 Populációk ............................................................................................................. - 7 2.3 Fitnessz függvény.................................................................................................. - 7 2.4 Szelekció ............................................................................................................... - 8 2.4.1 Véletlen kiválasztásos szelekció ................................................................... - 9 2.4.2 Rátermettség-arányos szelekció .................................................................... - 9 2.4.3 Sztochasztikus univerzális mintavétel......................................................... - 10 2.4.4 Lineáris rangsorolás .................................................................................... - 10 2.4.5 Pár-verseny szelekció (binary tournament selection).................................. - 11 2.5 Rekombináció...................................................................................................... - 11 2.5.1 Egypontos keresztezés................................................................................. - 11 2.5.2 Egyenletes keresztezés ................................................................................ - 12 2.5.3 Köztes keresztezés....................................................................................... - 12 2.6 Mutáció................................................................................................................ - 13 2.6.1 Véletlen génenkénti mutáció ....................................................................... - 13 2.6.2 Véletlen elemi permutáció .......................................................................... - 13 2.6.3 Inverziós operátor........................................................................................ - 14 -

3

A GA mőködése ......................................................................................................... - 15 3.1 Alapalgoritmus .................................................................................................... - 15 3.2 A GA elınyei ...................................................................................................... - 16 3.3 Hátrányok és korlátok ......................................................................................... - 16 3.4 Speciális esetek ................................................................................................... - 17 3.4.1 Szimulált hőtés ............................................................................................ - 17 3.4.2 Tabu keresés ................................................................................................ - 17 3.4.3 Sztochasztikus hegymászó .......................................................................... - 18 -

4

GA alkalmazási területek ......................................................................................... - 19 -

5

Genetikus algoritmusok megvalósítása Matlab segítségével ................................. - 21 5.1 5.2

6

A HelloWorld! algoritmus .................................................................................. - 21 Lineáris egyenletrendszerek megoldása.............................................................. - 22 -

Genetic Algorithm és Direct Search Toolbox v2.0 a Matlab programban .......... - 23 6.1 6.2

Parancssori lehetıségek....................................................................................... - 23 Genetic Algorithm Tool ...................................................................................... - 25 -

-37

Optimalizációs példák Matlab segítségével............................................................. - 29 -

8

Költség és hatékonyságelemzés ................................................................................ - 32 -

9

Irodalomjegyzék ........................................................................................................ - 34 -

10

A helloga.m függvény tartalma ................................................................................ - 35 -

11

A gaoptimset struktúra elemei............................................................................ - 37 -

-4-

1 Bevezetı „Three billion years of evolution can't be wrong. It's the most powerful algorithm there is.” Dr. David E. Goldberg, University of Illinois, 1989

1.1 Mi az a genetikus algoritmus? Az emberiség tudományos fejlıdésében mindig is szerepet játszottak az empirikus megfigyeléseken alapuló elméletek. Ha valami készen kapva mőködik a nagyvilágban, azt mért ne lehetne felhasználni saját céljainkra, esetleg egy kicsit elvonatkoztatva, általánosítva? Rengeteg matematikai probléma, és ezen keresztül új szakterület alakult ki igen egyszerő hétköznapi problémák megfigyelésével. Nincs másképp ez a genetikus ill. evolúciós algoritmusokkal sem: itt a példát a biológia (szebben mondva az anyatermészet) adta. Alapja, Darwin: „A fajok eredete” címő könyve 1859-ben jelent meg, és már az elsı napon elfogyott minden példánya. Az óta is erısen megosztja mind a tudós, mind a laikus társaságokat. Természetesen nem célom ezzel kapcsolatban állást foglalni, csak az elmélet gyökereire kívánok rávilágítani. A genetikus algoritmusok potenciális megoldás győjteményekkel dolgoznak, különbözı stratégiák során csoportosítják, majd a „jobb” megoldásokat kiválogatva igyekeznek mindig új állományokat kreálva eljutni egy elfogadható (esetleg az optimális) megoldáshoz. A megoldások győjteményét populációnak hívjuk, a benne lévı lehetséges megoldásokat egyedeknek. Az egyedekbıl különbözı szelekciókkal és mutációkkal új egyedeket képzünk (születnek), és igyekszünk kiválogatni közülük azokat, amelyek számunkra jobb tulajdonságokkal rendelkeznek, azaz „rátermettebbek”. Több generáción keresztül ismételve ezt a folyamatot, egyre jobb, pontosabb lehetséges megoldásokat kapunk. Véges lépés után, vagy egy kellıen pontos megoldás esetében az algoritmus leáll.

1.2 Hogyan alakult ki? Genetikus algoritmusok ötlete egyidıs a számítógép ill. a számítógépes programozás megjelenésével. Az alapkoncepció már megjelent az 1950-es években, természetes evolúciókutatással foglalkozó biológusok kívánták elsıként az elméleti eredményeket minél pontosabb szimulációval vizsgálni. Akkor még nem merült fel bennük, hogy a kidolgozott módszerek szélesebb körben is használhatóak. A 60-as évek elején többen egymástól függetlenül kidolgozták az evolúció által inspirált algoritmusaikat, fıként függvényoptimalizálásra és gépi tanulásra, de ezek a munkák kevés érdeklıdésre tettek szert. 1965-ben Ingo Rechenberg publikálta az evolúciós stratégiák alapjait, ami a genetikus algoritmusok egy rokon ága. Az elméletbıl még hiányoztak alapvetı ma használt fogalmak, de a terület fejlıdésének lökést adott. Nem volt még keresztezés, csak önmagukat reprodukáló egyedek, viszont itt vetıdött fel elıször a populáció fogalma. 1966 egy új irányág, az evolúciós programozás születését hozta. A lehetséges megoldásokat ebben a verzióban véges állapotú automaták reprezentálták, egy automata állapotátmenet

-5mátrixának véletlenszerő mutációja hozott létre egy új egyedet, majd az algoritmus a kettı közül jobbnak ítéltet tartotta meg. A keresztezés jelentıségét itt sem ismerték még fel. John Holland és csoportja volt az elsı, akik hivatalosan bevezették a keresztezés fogalmát, rávilágítva annak elınyeire. A hatvanas évek elejétıl dolgozott tanuló rendszereken, eredményeit csak 1975-ben publikálta. Ez tekinthetı a genetikus algoritmusok ma is használt elméleti alapjainak. A 80-as évek közepére az evolúciós programozás különbözı válfajai széles körben használtak voltak. A számítási nagyság növekedésével és az Internet rohamos terjedésével jelentısége és használhatósága széles körben kiteljesedett. Míg az elsı idıkben fıként elméleti, napjainkban az élet számos terén alkalmazzák gyakorlati problémák megoldására.

-6-

2 Definíciók, alapfogalmak A genetikus algoritmus (továbbiakban: GA) egy globális optimalizációs eljárás. Mindenhol alkalmazható, ahol a feladat sok lehetséges megoldás közül a legjobbat megkeresni. A genetikus algoritmus lehetséges megoldások egy populációját tartja fenn, azaz egyszerre több megoldáskezdeménnyel dolgozik. A lehetséges megoldások minıségét egy értékelı-, vagy más néven rátermettségi függvény adja meg. Az aktuális populációból minden lépésben egy új populációt állít elı úgy, hogy a szelekciós operátor által kiválasztott legrátermettebb elemeken (szülıkön) alkalmazza a rekombinációs- és mutációs operátorokat. Az alapgondolat az, hogy mivel általában minden generáció tagjai az elızınél rátermettebbek, a keresés folyamán egyre jobb megoldások állnak rendelkezésre.

2.1 Egyed, egyedek reprezentációja GA esetében a különbözı lehetséges megoldásokat egyedeknek (species) nevezzük. Az algoritmus megvalósítása szempontjából az elsı lényeges dolog, az egyedek ábrázolása. Leggyakoribb esetek a bitsorozattal, vektorokkal vagy permutációval történı ábrázolás, esetleg ezek valamely kompozíciójából alkotott struktúra. Az egyedeket nagy E-vel jelöljük.

2.1.1 Bitsorozat Bitsorozattal reprezentáljuk az egyedeket, ha valamely tulajdonsághalmazzal írjuk le azokat, és mindössze arra vagyunk kíváncsiak, hogy az adott tulajdonság jellemzi-e a példányt. Elınye alacsony tárigénye, illetve, hogy könnyő számításokat végezni vele.

Egy bitsorozattal ábrázolt kromoszóma. Az egyes biteket a biológiával analóg módon alléleknek is nevezik.

2.1.2 Vektor Másik gyakori ábrázolás a (valós) vektoros ábrázolás. Ezt olyan esetekben érdemes használni, ha fontos az egyedek egyes tulajdonságainak mennyiségi értéke is. Vektoros megoldásokkal nagyon sok minden könnyen leírható, és a számítások is jól elvégezhetıek alapvetı lineáris algebrai ismeretekkel. Vektorokkal bármely olyan egyedtípus ábrázolható, amelyet fix darabszámú mennyiséggel/költséggel jellemezhetı tulajdonság ír le.

2.1.3 Permutáció

-7Sok esetben egy összesség bejárására kell sorrendet adnunk (gráfalgoritmusok, pl. utazó ügynök probléma), ilyenkor a megoldás az elemek egy permutációja lesz. Az ábrázolás itt is valós vektorral történik, a vektor elemei az alapelemek sorszámai lesznek a felsorolás sorrendjében. A klasszikus genetikus algoritmusok bitsorozattal, vagy valós vektorral megvalósított genotípusos ábrázolást használnak, de az egyedi probléma ismeretében lehetséges egy másfajta, hatékonyabb megoldás is. Mivel a véges bitsorozatok tekinthetık azonosnak a {0,1} alaphalmaz feletti vektorterekbıl vett vektoroknak, továbbiakban csak a valós vektoros ábrázolással foglalkozunk. Ezt indokolják a gyakorlati megvalósításhoz felhasznált Matlab szoftver lehetıségei is.

2.2 Populációk Az egyedek egy adott idıbeli összegségét nevezzük populációnak (population). Egyszerő lenne azt mondani, hogy ez a lehetséges megoldások egy halmaza, de ez nem igaz, mert egy adott tulajdonságokkal rendelkezı egyed többszörösen benne lehet. A populációt P-vel jelöljük. Ezen kívül használatos még a populáció méretére a µ = P jelölés (az elemszám ebben az esetben számításba veszi a többszörös elemeket is). Az algoritmus során a könnyebb számolás miatt gyakori az egyedek egyfajta kódolása. Egy ilyen kódolás adja az egyed genotípusát (genotype). Mőveleteket az egyed genotípusával végzünk, a folyamat végén ebbıl dekódoljuk az optimális megoldást. Az egyedeket leíró tulajdonságok megjelenésének összességét fenotípusnak (phenotype) nevezzük. Felfogható úgy, hogy a fenotípus az egyed valóságban vett absztrakt vagy hétköznapi megjelenése, a genotípus ennek egy leképezése valamely az algoritmus során használható adattípusba. Ezt a leképezést kódoló függvénynek, a kimeneti változóit géneknek (gene), azok adott egyednél felvett értékeit alléloknak (allele) nevezzük. Ezek szerint, a kódoló függvény az egyes egyedek tulajdonságait képezi le génekbe. A GA minden egyes iterációs lépése újabb és újabb populációkat állít elı. Az iterációs lépések során keletkezı populációkat generációknak (generation) hívjuk. Az algoritmus minden generáció során új populációt állít elı az aktuális felhasználásával. Az új egyedek beépülnek a populáció lecserélve annak néhány, vagy akár az összes tagját. Utóbbi esetben generációs (generational) algoritmusról beszélhetünk. Ha a populáció mindössze egy elemő (µ = 1) , akkor helybeni (steady state) az algoritmus. Sok esetben szokták az aktuális populáció adott számú, százalékú legjobb példányát automatikusan, változtatás nélkül bepakolni az újba. Az ilyen megvalósítást elitistának (elitist) hívjuk.

2.3 Fitnessz függvény A megoldások értékeit egy rátermettségi- vagy szokásos terminológiával fitnessz függvény (fitness function) segítségével adjuk meg. Ennek a függvénynek kell heurisztikusan keresni a globális optimumát. Így érvényesül a darwini „legrátermettebb túlélése” elv, mivel minél rátermettebb egy elem, annál jobban megközelíti a fitnessz függvény értéke a globális szélsıértéket. A fitnessz függvény megválasztása lehet a legnehezebb feladat, és egyben a legfontosabb is, hiszen ennek segítségével mérjük az egyedek teljesítményét, alkalmasságát.

-8Kiszámolása az algoritmus szempontjából sok idıt vesz igénybe, ezért megválasztása jelentıs a futási idı szerint is. Ha kromoszóma n bit hosszúságú, akkor a rátermettségi függvény a keresési téren egy n-dimenziós rátermettségi tájképet (fitness landscape) határoz meg. Valós vektorok esetén ez a függvény egy n-dimenziós folytonos valós függvény lesz. A GA megoldása ekvivalens a rátermettségi tájkép globális szélsıértékének keresésével.

Rátermettségi tájkép bitsorozatos reprezentáció esetén. A 00, 01, 10 és 11 kromoszómák rátermettsége sorban: 0.5, 0.9, 0.1 és 0.

2.4 Szelekció Alapvetı fontossággal bír az algoritmus szempontjából, hogy miként jutunk új megoldásokhoz. A meglévı egyedeken végzett mőveleteket, amelyek új lehetséges megoldásokat állítanak elı keresı operátoroknak hívjuk. Háromféle operátort különböztetünk meg, melyek mindegyikét, vagy egy részét használjuk az eljárás során. Ezek: a szelekció, rekombináció, és a mutáció. Az egyedkiválasztás, vagy szelekció (selection) operátor az aktuális populációból alkalmas szülıket (párokat) választ, utódnemzés céljából. Ez azért is fontos, mert a módszer használata során nem kívánunk „légbıl kapott” adatokkal kisérletezni, hanem szeretnénk az addig elért eredményeket felhasználva tökéletesíteni azokat. A mővelet során a szelekciós állományból (selection pool) választunk bizonyos feltételek szerint egyedeket, és helyezzük a szülıi állományba (mating pool). A szelekciós állomány kezdetben általában megegyezik a teljes populációval. A szülıi állományt addig kell növelni, amíg az új egyedek létrehozásához elegendı szülı nem kerül bele, ez a GA esetében klasszikusan megegyezik a populáció méretével. Az egymástól különbözı szelekciós metódusok mőködését összehasonlíthatjuk, értékelhetjük többféle tulajdonsággal. A szelekciós intenzitás (selection intensity) a populáció átlagos rátermettségének változását mutatja a szelekció hatására:

   ∑ E′ − ∑ E  E∈P  Int =  E′∈P′  ∑ E ′′   E′′∈P′  − E′ ∑  µ E ′∈P′    Ahol P΄a szelekcióval létrehozott populációt jelöli. Vagyis az intenzitás az új és régi populációk átlag rátermettségének különbsége, osztva az új populáció szórásával.

-9A változatosság elvesztése (loss of diversity) azon egyedek aránya, amelyek nem kerültek kiválasztásra. Azaz:

D=

{E : E ∈ P nem lett kiválasztva} µ

Jellemzı érték még a szelekciós változatosság (selection variance), amely a régi és új populációk szórásértékeinek aránya:

  ∑ E ′′    E ′′∈P′  − E′   ∑  E ′∈P′ µ    V = &   ∑E    E&∈P     ∑ µ − E      E∈P     

2

Ezen tulajdonságokkal jól vizsgálhatjuk az algoritmusunk szelekciós mőködését. A szelekciós intenzitás megmutatja, hogy az algoritmus milyen mértékben választja ki a legrátermettebb egyéneket. Ha a változatosság elvesztése túl magas, félı hogy a keresési tér beszőküléséhez és korai, nem feltétlenül globális optimumhoz való konvergenciához vezet, mivel az új populáció túl sok azonos egyedbıl áll. A variancia ennek pont ellenkezıjét mutatja: nagyobb érték esetén szélesebb keresési térben dolgozhatunk, ami gyorsabb konvergenciát biztosít a globális szélsıértékhez. Nézzük, milyen általános megvalósításai vannak a szelekciós operátornak!

2.4.1 Véletlen kiválasztásos szelekció A legegyszerőbb, ámde legkevésbé hatékony szelekció. Gyakorlatilag az aktuális populációból véletlenszerően választunk szülıket. Lehet ismétléses, vagy ismétlés nélküli. Elıbbinél a szelekció során minden egyes lépésnél minden egyed azonos eséllyes kiválasztható, míg az utóbbi esetben a már kiválasztott egyedek nem vesznek részt a további kiválasztásban. Legnagyobb hátránya az, hogy nem veszi figyelembe azt a darwini alapelvet, miszerint a rátermettebb egyedek nagyobb eséllyel érvényesülnek az egyedlétrehozásban.

2.4.2 Rátermettség-arányos szelekció A rátermettség-arányos szelekció (fitness proportionate selection) esetében egy egyed kiválasztásának valószínősége annál magasabb, minél nagyobb a rátermettsége a populáció átlagához viszonyítva. Visszatevéses szelekció, azaz minden lépésnél mindegyik példány (újra) kiválasztható. A kiválasztás esélye tetszıleges Ê egyednél:

- 10 -

p ( Eˆ ) =

F ( Eˆ ) ∑ F (E)

E∈P

Megvalósítása általában a rulett módszerrel történik, ami az egyik legrégebbi, és leginkább használt szelekciós operátor. Az algoritmus analógiája egy rulettkerék: a kerületén felvesszük az egyedeket p(Ê) hosszarányú körcikkekkel. Ahol a „golyó” megáll, az egyed kiválasztásra kerül. Elınye, hogy könnyen megvalósítható, és figyelembe veszi a szülık rátermettségét. Hátránya, hogy egy nagy rátermettségő egyed aránytalanul sokszor bekerülhet a szülık közé, ezáltal beszőkülhet az algoritmus keresési tere. Ennek elkerülésére szokták a fitnessz függvényt skálázni (scaling) a Φ( E ) = g ( F ( E )) függvény segítségével. Például, ha a fitnessz függvény exponenciális, akkor egy megfelelı g ( x) = c − log( x) függvény lineárissá teheti.

Rulett szelekció szemléltetése kördiagrammal. Az egyes egyedek kiválasztási eséllye a körcikkely méretével arányos

2.4.3 Sztochasztikus univerzális mintavétel A sztochasztikus univerzális mintavétel (stochastic universal sampling, SUS) fitnessz alapú szelekció. A rulett szelekció olyan módosított változata, amely minimalizálja a mővelet során az azonos egyedek többszörös kiválasztását. Itt úgy osztjuk fel a rulettkereket, hogy figyelembe vesszük az egyedek várható kiválasztásainak számát:

V ( Eˆ ) = µ ⋅ p ( Eˆ ) A rulett kerületén µ darab mutatót helyezünk, azt egyenlı részekre felosztva. „Pörgetés” után azt az egyedet választjuk ki, amelyik a leközelebbi mutatóhoz esik pörgésirány szerint.

2.4.4 Lineáris rangsorolás A rangsorolásos szelekció (ranking, linear ranking) szintén a fitnesszérték alapú módszereknél elıforduló szórásbeli hátulütıket kívánja kiküszöbölni. A populáció egyedeit sorbarendezzük rátermettség szerint, kezdve a legrosszabbtól a legrátermettebbig. A sorszámozás egyedi, tehát azonos fitnessz értékő egyedek

- 11 sorszáma eltérı. Az egyes egyedek kiválasztásának valószínősége lineárisan függ azok sorszámától:

1 2(1 − η )(i − 1)  η +  ( µ − 1)  µ i = (1,Κ , µ ) p ( Ei ) =

Ahol η a legrosszabb rátermettségő példány kiválasztási valószínősége (0≤ η ≤1). A legrátermettebb egyed szelekciós esélye 2-η lesz, a köztes elemek valószínőségei lineárisan eloszlanak a két szélsıérték között.

2.4.5 Pár-verseny szelekció (binary tournament selection) A versengı, vagy pár-verseny szelekció (binary tournament selection) nem fitnessz arányos szelekció. A módszer µ lépéses ciklusból áll. Minden lépésben elıre rögzített T (tour) darab elemet választunk ki véletlenszerően a populációból. Majd az így kapott elemek közül a legrátermettebbet választjuk a szülık közé. Párversenyrıl valójában T=2 esetén beszélhetünk, ami a leggyakrabban használt paraméterérték. Elınye, hogy kisebb eséllyel veszít a változatosságból, cserébe általánosan kisebb a szelekciós intenzitás, mint a rátermettség arányos metódusoknál.

2.5 Rekombináció A rekombináció (recombination) operátor két egyed (szülık) reprezentációjából generál új egyedet, egyedeket. Ez a klasszikus biológiai utód létrehozásának felel meg. A GA alapvetı keresı operátora a rekombináció, az új egyedek létrehozásában döntı szerepet játszik.

2.5.1 Egypontos keresztezés Egypontos keresztezésnél (1-point crossover) az egyedeket egy véletlenszerően kiválasztott i. bitnél (1 ≤ i < n) elvágjuk. Az új egyed az egyik szülı tulajdonságait 1,...,i bitig, a másik szülı tulajdonságait (i+1),...,n-ig örökli. Lehetséges két új egyed (testvérek) létrehozása is: a második keletkezı egyed, analóg módon a szülık kromoszómáinak másik felébıl áll össze, ahogy azt az alábbi ábra is mutatja.

- 12 -

Egypontos keresztezés. A keresztezési pont (crossover point) a 4. génnél van.

2.5.2 Egyenletes keresztezés Egyenletes keresztezés (uniform crossover, UX) használatával az utód egyes génjei a szülık azonos génjeinek valamelyike lesz. Az i. utódgén 0,5 eséllyel az egyik vagy a másik szülı azonos génje lesz. Ez alapján átlagosan a gének fele cserélıdik ki a szülık között.

Egyenletes keresztezés. A két utód 4-4 génben tér el a szülıktıl.

Formálisan leírva:

u i = api + (1 − a )qi Ahol ui az utód, pi, qi a szülık megfelelı génjeit jelöli, a pedig minden génre véletlenszerően választott együttható {0,1} halmazból.

2.5.3 Köztes keresztezés A köztes keresztezés (intermediate recombination) az egyenletes keresztezés kissé módosított változata. A különbség annyiban rejlik, hogy az elıbb megadott formulában a értéke [-h, 1+h] intervallumban mozoghat (h≥0). Tehát az utód génjeinek értéke szüleik génjeinek egy függvénye lesz, ami azt jelenti, hogy nem közvetlenül a szülıi tulajdonságokat örökli.

- 13 A rekombináció folyamata sztochasztikus genetikus algoritmusok esetén.

2.6 Mutáció A mutáció (mutation) operátor meglévı egyedeket módosít, úgy hogy véletlenszerően megváltoztatja azok bizonyos tulajdonságait. A mutáció segít szélesíteni a keresési teret, viszont óvatosan szabad csak alkalmazni, mert elronthatja a gondosan kiválasztott szülıi tulajdonságokat. Éppen ezért a mutáció jelentısége a GA folyamán csekély, egy tulajdonság megváltoztatásának esélye általában pm≤10-3. Ezt úgy kell érteni, hogy a mutáció valószínősége pm minden egyed, minden génjére. Az alábbiakban összefoglaljuk az általánosan használt mutáció megvalósításokat.

2.6.1 Véletlen génenkénti mutáció A mutáció legegyszerőbb és legkézenfekvıbb formája, hogy az egyes géneket bizonyos valószínőséggel megváltoztatjuk. Bitsorozat esetén szimplán negáljuk a megfelelı értéket, valós vektoroknál az eredeti értéket egy véletlen értékkel helyettesítjük, ügyelve természetesen arra, hogy az új érték értelmezhetı legyen az adott pozícíóban. Egy másik verzió szerint találomra veszünk n ⋅ p m  darab gént, és azokat változtatjuk meg.

Véletlen bitenkénti mutáció. A mővelet során az egyed 2 génje negálódik.

2.6.2 Véletlen elemi permutáció Egy másik könnyen megvalósítható mutációs algoritmos a véletlen elemi permutáció. Igazából akkor van jelentısége, ha az egyedek permutációkkal vannak ábrázolva, hiszen az esetben eme tulajdonságot nem szabad a mutáció során sem elrontani. Ilyenkor az aktuális permutációt megszorozhatjuk (i j) transzpozícióval (1≤i,j≤n), aminek eredménye egy olyan permutáció lesz, amiben az i. és j. érték helyet cserél. A mutáció valószínőségét egyedenként vizsgáljuk, egy kiválasztott egyednél akár több elemi permutációt is végrehajthatunk.

- 14 Véletlen elemő permutáció alkalmazása. Az eredeti egyedet a (2 5) transzpozícióval szorozva kapjuk annak új, mutáns változatát.

2.6.3 Inverziós operátor Bár a szakirodalom több helyen különálló keresı operátornak említi, az inverziós operátor valójában a mutáció egy fajtája, felfogható a véletlen bitenkénti mutáció egy változataként is. A mutáció valószínősége itt is egyedekre vonatkozik. A kiválasztott egyedeknél véletlen 1≤i,j≤n számokra a i. és j. bitek közötti részt invertáljuk. Ez bitsorozatnál a negációt jelenti. Valós vektoroknál az értelmezési tartomány alapján definiálni kell az inverz fogalmát.

Inverziós operátor alkalmazása az egyed 5. és 9. bitje közötti részre.

A mutációs operátor sztochasztikus a genetikus algoritmusoknál.

- 15 -

3 A GA mőködése 3.1 Alapalgoritmus A GA alapalgoritmusát az alábbi pszeudokóddal tudjuk leírni: 1. 2. 3. 4.

Stratégiai paraméterek beállítása t := 0 P0 kezdeti populáció létrehozása P0 egyedeinek kezdeti kiértékelése a fitnessz függvény alapján 5. WHILE NOT Kilépési_feltétel(Pt) 6. Pt* := Szelekció(Pt) 7. Pt’ := Rekombináció(Pt*) 8. Pt’ := Mutáció(Pt’) 9. Pt+1 := Visszahelyezés(Pt’) 10. t := t+1 11. WHILE ciklus vége 12. Legjobb fitnessz értékkel rendelkezı egyed kiválasztása

Az algoritmus elıször beállítja a mőködés során használt paramétereket, majd elkészíti a kezdeti populációt. Ez lehet bemenı adat (esetleg valamilyen sejtés alapján létrehozott kezdıállapot, ami nagymértékben meggyorsíthatja az algoritmus keresését), vagy véletlenszerően generált egyedek összessége. Szükség esetén ennél a lépésnél kell a kódoló függvénnyel elıállítani az egyedek genotípusait. Ezután ki kell számítani minden egyedhez tartozó rátermettségi értéket a fitnesszfüggvény segítségével. Egy t változóban számoljuk az eltelt generációkat, ezt nullával indítjuk. Az általános lépés elején ellenırizzük, hogy algoritmusunk elérte-e valamely kilépési feltételt. Ezek általánosan a következık lehetnek: fitnesszfüggvény értéke valamely egyednél elér egy adott értéket, a generációk száma eléri a maximális megengedettet (algoritmus végességének biztosítása), a fitnesszfüggvény értékek szórásának változása túl kicsi, legjobb egyed fitnessz értékének változása adott küszöb alatt marad, maximális futásidı túllépése… stb. Kilépési feltétel teljesülésénél az algoritmus véget ért, kimenetként az utolsó populáció legjobb rátermettségi értékkel rendelkezı egyedét választjuk. Az általános lépés során az algoritmus elsıként kiválasztja az aktuális populációból a lehetséges szülıket (szelekciós operátor), majd ezekbıl új utódokat képez (rekombinációs operátor). A kapott utódokon különbözı kisebb-nagyobb változásokat hozhatunk létre (nem feltétlenül minden utódnál, általában valamilyen adott valószínőség mellett – mutációs operátor). Az így kapott új elemekbıl képezzük a következı generációt (t+1. populáció), kiszámítjuk az aktuális fitnessz értékeket, t változót növeljük eggyel, és kezdjük újra az általános lépést.

- 16 -

3.2 A GA elınyei A GA elınyének legfıképp azt tartják, hogy egy problémafüggetlen metaheurisztika. Ráadásul, ellentétben a legtöbb használt metaheurisztikával, sok esetben jóval gyorsabban eléri a kívánt közelítı eredményt. Globális algoritmus, azaz megfelelıen választott kezdıpopuláció és szelekció esetén nagy keresési teret tud bejárni, kicsi az esélye hogy egy probléma valamely lokális optimuma becsapja. Fontos elıny, hogy a GA párhuzamosan mőködik, azaz egyszerre több megoldást vizsgál a keresési tér több területén. A legtöbb keresı algoritmus egyszerre csak egy lehetséges megoldást tud vizsgálni, és csak egy irányba iterál. Ezeknél egy lokális optimum esetében nincs alternatív választási lehetıség, el kell vetni az addigi eredményeket, és újra kezdeni a teljes eljárást. GA esetében egy zsákutca könnyen eldobható, más, ígéretesebb irányba folytatva a keresést, ezáltal nagyobb eséllyel juthatunk az optimális megoldáshoz. A párhuzamosság másik elınye, hogy hatalmas mérető keresési terekkel tud dolgozni. Kiválóan alkalmas nemlineáris problémák megoldására, nem ritka az 1000 bitnél is nagyobb tér, azaz ahol a lehetıséges száma 21000≈10301 feletti. A feldolgozás során mőködési elvébıl adódóan egy lehetséges megoldás vizsgálatával annak „rokonait” is feldolgozza, hiszen akár megtart, akár eldob egy megoldást, azzal minısíti a hozzá hasonló megoldásokat is (a tıle nem sokban eltérı fitnessz értékkel rendelkezıket). Felfogható egyfajta sztereotípikus gondolkodásnak is, mivel az egyed tulajdonságaiból következtetünk egy csoport tulajdonságaira. Ezt a tulajdonságot szkéma tételnek (Schema Theorem) nevezzük. Jól teljesít olyan helyzetekben is, ahol a kiértékelı függvény nem „szép”: bonyolult számolni, nem folytonos, idıben változó, esetleg örökölt, vagy számítási hibákkal terhelt. Sokszor okoz gondot, hogy egy optimalizáló eljárás nem tud elég nagy teret bejárni, ezért értékenyebb lehet a kisebb függvényhibákra is. A GA egyszerre tudja használni a feldolgozáskor kapott információkat. Az különbözteti meg az egyelemő iterációktól, hogy a többszörös kiértékelés nem szimplán sok egyelemő közelítı lépések sorozata, az egyedek keresztezésével megvalósul a potenciális megoldások közötti információáramlás. Jó keresztezési eljárás választásával elérhetı hogy minél értékesebb információk cseréljenek gazdát az új populáció elıállításakor. Végezetül, kiemelhetjük a módszer globalitását: az eredeti probléma ismerete nélkül mőködik, úgy állít elı megoldásokat, hogy nem használja fel annak tulajdonságait. Ezért kiválóan alkalmazható olyan esetekben, ahol nem tudjuk leírni magát a problémát, de értékelni tudjuk a lehetséges megoldásokat valamilyen szempont szerint.

3.3 Hátrányok és korlátok A GA természetesen nem mindenható. Sok esetben nem ad optimális megoldást, ellentétben bizonyos problémakörök ismert algoritmusainál, igaz, hogy ilyen esetekben is egy kellıen jó megoldást lehet vele gyártani.

- 17 Bár azt monduk, hogy az algoritmus anélkül képes lefutni, hogy ismerné magát a kiindulási problémát, a valóságban ez egyáltalán nem árt. A probléma alapos ismerete nélkül nehéz igazán jó és hatékony rátermettségi függvényt adnunk. Ha a kiértékelés nincs eléggé arányban az elvárásainkkal, akkor nem fogunk jó eredményt kapni, akárhogy is futtatjuk le az algoritmust. Könnyő, viszonylag kis keresési terő problémáknál túl költséges. A GA nagy elınye, a párhuzamosság hátrány lehet olyan esetben, ha az adott feladat könnyen megoldható hagyományos módszerekkel. Ilyenkor ugyanis nagyságrenddel több kiértékelést végezhetünk, mint más keresı algoritmusok, ráadásul a sztochasztikus mőködésbıl adódóan nem feltétlenül fog olyan sebességgel konvergálni az algoritmusunk, mint az erre kidolgozott más módszerekkel. Általánosságban elmondható, hogy kritikus szerepe van a futás ill. az eredmény szempontjából az alapvetı paraméterek választásának. Ezek: a populáció mérete, generációk száma, a különbözı keresı operátorok, és nem utolsó sorban a kilépési feltételek jó megválasztása. Ahhoz, hogy ezeket finomra tudjuk hangolni, szükséges lehet a probléma szerkezetének mélyebb ismerete, a meglévı sejtések vagy egyéb eredmények felhasználása. Ha másképp nem megy egyszerő probálgatással is kereshetünk jobb paramétereket. Felhasználva egy elızı futás eredményeit tudunk következtetni, hogy milyen értéken célszerő változtatni egy jobb közelítés elérése érdekében. Sajnos ez nagyban növelheti az algoritmus költségét, mivel lehet, hogy igen sokszor le kell futtatnunk ahhoz, hogy megfelelı pontosságú, elfogadható eredményt kapjunk.

3.4 Speciális esetek Az alapalgoritmus egyes lépéseinek elhagyásával, speciális értelmezéseivel speciális, megkülönböztetett esetek kaphatunk. Ezek közül a legismertebbek a szimulált hőtés, a tabu keresés és a sztochasztikus hegymászó algoritmusok.

3.4.1 Szimulált hőtés A szimulált hőtés (simulated annealing), esetében a szokásos analógia a fémek edzésének a folyamata, amelynek során a fém lassú hőtés során közel optimálisan rendezett atomi szerkezetet vesz fel. Itt a populáció egyelemő, a keresı operátor kizárólag a mutáció. Ha az új megoldás rosszabb, mint a régi, akkor is elfogadjuk egy bizonyos valószínőséggel, amit a hımérséklet paraméter szabályoz. Ha a hımérséklet nulla, az új megoldást csak akkor fogadjuk el, ha nem rosszabb, mint a régi. A hımérséklet a keresés folyamán fokozatosan csökken.

3.4.2 Tabu keresés A tabu keresés (tabu search) szintén egyelemő populációt használ, a keresı operátor szintén kizárólag a mutáció. A különbség itt is a visszahelyezési függvényben van. A tabu keresés során egy tabulistát tartunk fenn, amely a legutóbb megvizsgált néhány megoldásból áll. A tabulista mérete az algoritmus paramétere. Az új populáció, azaz az új aktuális megoldás

- 18 kiválasztásához elıször megnézzük, hogy a mutációval létrehozott új elem szerepel-e a tabulistában. Ha igen, akkor nem fogadjuk el, egyébként, ha nem rosszabb, mint a régi megoldás, akkor elfogadjuk. A régi megoldás tabulistára kerül. Amennyiben elértük a maximális elemszámot a listán, a legrégebbi elemet töröljük.

3.4.3 Sztochasztikus hegymászó A sztochasztikus hegymászó (hill climber) a legegyszerőbb változat. A populáció itt is egyelemő, a keresı operátor pedig a mutáció. Az új megoldás felváltja a régit, ha ugyanolyan rátermett vagy rátermettebb. Látható, hogy ez tulajdonképpen egy klasszikus mohó algoritmusos megvalósítás. Érdekes ezen túl, hogy a sztochasztikus hegymászó lényegében egy fix nulla hımérsékleten futó szimulált hőtés, vagy egy nullaelemő tabulistát használó tabu keresés, vagy egyelemő populációt használó elitista genetikus algoritmus. Az egyes metaheurisztikák tehát a hegymászó különbözı általánosításaiként is felfoghatók. Másrészrıl ezen a módszereknek különbözı kombinációi is használatosak, pl. tabulistát alkalmazó szimulált hőtés, csökkenı mértékő mutációt alkalmazó genetikus algoritmus, stb. A genetikus- ill. evolúciós algoritmusoknak igen sok egyéb variánsa ismeretes. Léteznek olyanok, amelyek ezen elmélettıl függetlenül jöttek létre, de mégis tekinthetıek egyfajta speciális változatnak. Ilyen például a kombinatorikus optimalizálásban használt hangya kolónia módszer, ami egy hosszú távú memóriát alkalmazó evolúciós algoritmus megvalósításként értelmezhetı.

- 19 -

4 GA alkalmazási területek „Én má’ nem muzsikálok, csak egy jelet adok a gépnek: İ mutassa meg helyettem, ahogy mozdul bennem a lélek.” Quimby: Halleluja A genetikus algoritmusok gyakorlati alkalmazási köre mára igencsak széles lett. Természetesen ez nem egy csodaszer, mint ahogy azt láthattuk az elınyık/hátrányok taglalásánál. Nézzünk néhány tipikus alkalmazási területet.




Szélsıérték problémák Legnyilvánvalóbb alkalmazási kör, adott függvény, vagy azok rendszerének szélsıérték keresése. Tulajdonképpen itt a fitnessz függvény maga a vizsgált függvény, kiegészítve az egyedre esetleg bizonyos megszorításokkal az értékkészlet, vagy egyéb feltételek alapján.




Gráfalgoritmusok A gráfelmélet számos, sok helyen elıforduló NP-teljes problémával ajándékozta meg a matematikus társadalmat. Ilyen pl. az utazó ügynök problémája, az egyes szinezési feladatok, hozzárendelési problémák. A GA implementációk sokszor jobb eredményeket adnak, mint az elméletileg igazolt egyes algoritmusok.




Játékelmélet A játékelmélet tipikusan olyan problémákkal van tele, ahol igen nagy keresési teret kell bejárni. Ezen kívül nem mindig egyszerő magát a játékot formalizálni, viszont ha egy adott helyzetet ki tudunk értékelni (megadható rátermettségi függvény), akkor jól alkalmazhatóak a GA módszerek.




Genetikus Programozás – pl. LISP programkódok „születése” A genetikus programozás a GA egy alfaja, programok fejlesztésére használják. Minden egyed egy teljes programkódot ír le, általában a bejárási fákkal reprezentálják. Természetesen a keresı operátorok is eszerint módosulnak, például a mutáció egy formája, ha két ágat kicserélünk egymással a fában. Egyik leggyakoribb alkalmazási terület LISP programkódok készítése.




Tanulási problémák Elvben minden tanulási probléma megadható optimalizálási feladatként, így a genetikus algoritmusnak is sok alkalmazása van a gépi tanulás területén.

Felsorolt problémák viszonylag jól körülhatárolt elméleti jellegőek elsı hallásra. Álljon itt néhány „extrémebb”, egyedi példa, arról hogy hány különbözı területen sikerült alkalmazni valamilyen evolúciós stratégiát.

- 20 -

•

Koncerterem tervezése, a maximális audio élmény nyújtása a hallgatóság, és a zenészek számára.

•

Szuperszónikus gépek szárnyformájának tervezése. Japánban, a 2000-es évben genetikusan tervezett szárnyak felvették a kihívást a hagyományos technológiával készültekkel, bizonyos fellelhetı trendek pedig segítettek alátámasztani az elméleti eredményeket.

•

Föld körüli mőholdak együttes pályájának optimalizálása, a hatékonyabb lefedettség eléréséhez. GA alkalmazásával a konvencionális megoldásoknál hatékonyabb, azoktól igencsak eltérı eredmények születtek, ami sok gyakorlati eredmény újragondolására ösztönözte a mérnököket.

•

A Unilever cég genetikus algoritmusokat használt bizonyos tisztítószereinek baktériumölı vegyületeinek kutatására. Az eredményeket az óta szabadalmaztatták.

•

Sikeresen használták nemzetközi valutaárfolyamok és tızsdei részvények adás-vételében.

•

Készült algoritmus rendırségi fantomkép készítéshez, amit sikeresen használtak egy bankrablás tetteseinek elfogásához.

•

Malajziában azt vizsgálták, milyen okai vannak annak, ha valaki telefonszolgáltatót vált. Olyan algoritmust kerestek, ami segít elırejelezni, hogy kik és milyen okból teszik ezt, ezáltal az okok megelızhetıek lehetnek, és a szolgáltató is jobban meg tudja választani célcsoportját.

•

Egyszerő beszédfelismerı áramkört terveztek GA alkalmazással. A feladat szinte lehetetlen kihívás elé állította a problémával foglalkozó mérnököket, ezért próbálkoztak más módszerekkel. Az eredmény meglepıen kevés logikai kaput használt fel, mőködését sokáig homály fedte.

•

Sakkozó algoritmusok. Egy igen bonyolult probléma, mivel nehéz jó rátermettségi függvényt definiálni. Más, hagyományos algoritmusokkal ötvözve sikerült nagymesteri szinten játszó gépet kreálni.

•

Jól használható az un. órarend problémára. Ez egy NP-teljes feladat, ami visszavezethetı gráfszinezési problémákra. Normál módszerekkel nem létezik rá hatékony algoritmus. Négy nagy amerikai egyetemen (egyenként több mint 25.000 hallgató) teszteltek GA megoldásokat, és 40%-kal jobb eredményt értek el, mint az elıtte lévı rendszer szerint.

És még számos példát sorolhatunk, kezdve az egyszerőtıl az igen elvadultabbakig. Látható, hogy a problémamegoldás eme módszere a tudományok minden területén tudott bizonyítani. Lehet, hogy nem mindenható, de láthatóan széles körben jól alkalmazható technika.

- 21 -

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

5.1 A HelloWorld! algoritmus Az eddigi elméleti ismeretek alapján már képesek vagyunk mőködı GA kódot generálni. Mint ahogy azt egy új programozási technika megismerésekor szokás, készítsük el a „Hello World!” genetikus algoritmusát. Ezen azt kell érteni, hogy megpróbáljuk genetikusan „kitenyészteni” sztringek egy sorozatából ezt a klasszikus üdvözlést. A populáció egyedei tehát azonos hosszúságú sztringek, amiket genotípusosan ábrázoljuk. Minden sztringhez hozzárendelünk egy sorvektort, amelynek elemei (azaz a gének) a sztring egyes karaktereinek ASCII kódjai. A fitnessz érték az egyed és a keresett sztring távolsága, azaz az egyes betők közötti távolságok összege. Minél kisebb a fitnessz érték, annál rátermettebb az adott egyed. Nyilvánvaló, hogy ha ez az érték nulla, akkor elértük a keresett sztringet. Az algoritmusunk fı ciklusában sorbarendezi a populáció egyedeit növekvı fitnessz érték alapján. A legjobbakat automatikusan beválogatja a következı populációba (elitizmus). A maradék helyeket feltöltéséhez szelekciós során kiválogatja a szülıket. A szelekció ebben az esetben egyszerő véletlen kiválasztás, ami nem foglalkozik az önreprodukcióval (mindkét szülı ugyanaz az egyed). A kiválasztott szülıket egypontos keresztezéssel rekombináljuk, a keletkezı egyedet behelyezzük az új populációba. Legvégül egy elıre beállított mutációs ráta szerint módosítjuk a sztringeket. A mutáció megvalósítása véletlen génmutáció, egyetlen génre. A kapott új populációra kiértékeljük a rátermettségi függvényt, behelyettesítjük a régi populáció helyére, növeljük a generációszámot és ezzel le is zárul a fı ciklus. Kérdés még, hogy milyen kilépési feltételt alkalmazzunk algoritmusunk során? Két dolgot veszünk figyelembe: egy elıre megadott generációszám ill. az optimális megoldás elérését (fitnessz érték nulla). Az így elkészített helloga függvény forrása megtalálható az esszé végén. Nézzünk néhány tesztet! Az alapbeállítás 1000 példányos populációkkal dolgozik. A populáció legjobb 10%-át válogatjuk az elitek közé minden lépésben. A mutáció esélye 0,25 egyedenként. Ha elérjük a 100 generációt optimális eredmény nélkül, a függvény leáll, és az adott pillanatban legjobb egyedet adja vissza közelítı megoldásként. Az elsı esetben a végrehajtás során nem sikerül eléri a „Hello World!” kifejezést, bár az eredmény egy kezdı angolos esetében egész tőrhetınek mondható: mindössze egy karakterrel tér el. >> helloga 0. generáció 10. generáció 20. generáció 30. generáció

legjobb legjobb legjobb legjobb

egyede: egyede: egyede: egyede:

^ZxW`SRibfX# C\ih~&RtxXf# Gfmes!XnlkWGfmli!Xnxo\

fitness: fitness: fitness: fitness:

179 82 49 30

- 22 40. generáció legjobb egyede: Icili!Xoqli! 50. generáció legjobb egyede: Gfmon Xnrlc! 60. generáció legjobb egyede: Gcmln Vnrlc! 70. generáció legjobb egyede: Gemln Vnrlc! 80. generáció legjobb egyede: Gello Vnrle! 90. generáció legjobb egyede: Iello Wnrld! A program elérte a maximális generációszámot

fitness: 20 fitness: 10 fitness: 8 fitness: 6 fitness: 4 fitness: 2 optimum nélkül.

ans = Hello Vorld!

Egy másik futtatásnál már szerencsénk van: a függvény optimális megoldást talál, nem sokkal a maximális generációszám elérése elıtt. És íme, az elsı genetikusan tenyésztett üdvözlıszövegünk: >> helloga 0. generáció legjobb egyede: 10. generáció legjobb egyede: 20. generáció legjobb egyede: 30. generáció legjobb egyede: 40. generáció legjobb egyede: 50. generáció legjobb egyede: 60. generáció legjobb egyede: 70. generáció legjobb egyede: 80. generáció legjobb egyede: 90. generáció legjobb egyede: Optimális érték elérve.

HmwUuIRzv{jD Gggzp&XZrdW1 Miuhp&Tgvmk# Gggmo&Xnteb% Hglkm$Vprtc% Iglkk Woroc# Gelmo Uormb! Henmo Worlb! Helmo Vorld! Helmo World!

fitness: fitness: fitness: fitness: fitness: fitness: fitness: fitness: fitness: fitness:

165 88 54 32 24 14 7 5 2 1

ans = Hello World!

5.2 Lineáris egyenletrendszerek megoldása Szép, szép, mondhatjuk, de mi a haszna az egésznek? Úgy tőnik, hogy még arra se jó, hogy egy TTK-s buliban ezzel kápráztassuk a csajokat… Elsı ránézésre tényleg nincs sok köze az optimalizáláshoz, de vegyük észre a következıket. Az egyedek genotípusos reprezentációja valójában egy vektort takar, aminek a hossza megegyezik a keresett sztring hosszával. Valójában az algoritmus során az A ⋅ x = b általános alakú lineáris egyenletrendszer megoldását keressük közelítı módszerrel, ahol speciálisan A = E , azaz a megfelelı n × n -es egységmátrix, b vektor pedig a „Hello World!” egyes karaktereinek ASCII kódja. Tetszıleges x k egyedre, annak fitnessz értéke megegyezik xk − b 1 vektornorma értékével. Mivel az algoritmus során nem tételeztünk fel semmit a sztring génjeit reprenzentáló vektorról, minden további nélkül átalakíthatjuk az eljárást egyenletrendszerek megoldására. Ehhez mindössze annyit kell tenni, hogy a rátermettségi függvényt a jelenlegi helyett a A ⋅ xk − b 1 formulával kell helyettesítenünk. Továbbgondolva a dolgot, ha definiálunk egy relációs vektort, ami azt az információt hordozza, hogy az adott feltétel egyenlet vagy egyenlıtlenség-e, akkor használhatjuk az algoritmust áltálános lineáris programozási feladatok megoldására. A célfüggvény itt a feladat célfüggvénye, annyi kiegészítéssel, hogy ha valamely megadott feltétel nem teljesül egy egyednél, akkor Inf értéket ad vissza. Könnyen belátható, hogy a kimenet az optimális megoldáshoz konvergál.

- 23 -

6 Genetic Algorithm és Direct Search Toolbox v2.0 a Matlab programban A továbbiakban a Matlab szoftver 7.1.R14 verziójával fogunk dolgozni, azon prózai okból kifolyólag, hogy jelen anyag szerzıje ehhez a verzióhoz tudott hozzájutni, ami tartalmazza az említett csomagot. Kétféle módon használhatjuk fel az eszköztár lehetıségeit: parancssorból és a Genetic Algorithm Tool segítségével.

6.1 Parancssori lehetıségek A Matlab genetikus algoritmusokat használó eszköztára sajnos csak limitált lehetıségeket rejt magában. Fı függvénye a ga függvény, amely F(X) minimumát próbálja meghatározni, megadott feltételeket figyelembe véve. Formálisan: F a fitnessz függvény, aminek a minimumát keressük, X egy tetszıleges egyed. Ekkor az optimális megoldás olyan X, ahol • • • • •

Aeq·X = beq (lineáris egyenletek) A·X ≤ b (lineáris egyenlıtlenségek) Ceq(X) = 0 (nemlineráis egyenletek) C(X) ≤ 0 (nemlineáris egyenlıtlenségek) LB ≤ X ≤ UB, azaz X egy adott intervallumon keresendı

feltételek teljesülése mellett F(X) értéke minimális. Ezen jelölések mellett a ga függvény általános alakja: >> [X,FVAL,REASON,OUTPUT,POPULATION,SCORES] = GA (F, NVARS, A, b, Aeq, beq, LB, UB, NONLCON, options)

A fent nem definiált jelölések jelentése: • • • • • • • •

NVARS: F függvény függvényváltozóinak száma NONCLON: C(X) és Ceq(X) függvényeket megvalósító Matlab függvény (ezeket ált. magunknak kell implementálnunk) FVAL: F(X), a kimenı megoldásegyedre REASON: a kilépés okának leírása OUTPUT: a futás körülményeirıl ad néhány információt ez a struktúra POPULATION: a kilépéskor meglévı populáció SCORES: a kilépéskor meglévı populáció fitnessz értékei options: az algoritmus paramétereit tartalmazó struktúra (lásd. Függelék)

A sikeres futtatáshoz elegendı már F és NVARS megadása is. Nézzük az következı triviális példát: >> ga(@(x) x*x, 1) Optimization terminated: average change in the fitness value less than options.TolFun. ans =

- 24 -

-0.0020

Ez az f ( x) = x 2 függvény abszolút minimumát keresi, ami természetesen x = 0 helyen található. Jó példa ez olyan függvényparaméter megadására, ami nem .m fájlban található, hanem csak egyszerően parancssorban van megírva. Látható, hogy az algoritmus ezen futása „egész közeli” eredményt talált. Megtudtuk, hogy a leállás a fitnessz értékek generációk közötti túl kicsi eltérése miatt történt. Figyelembe véve, hogy az alapbeállítások közel sem optimálisak, és nem túl nagy sem a populáció, sem a generációk száma, meg lehet próbálkozni egy kis finomhangolással. Az algoritmus opcióit a gaoptimset függvénnyel tudjuk beállítani. Ez egy olyan struktúrát ad vissza, ami megfelel az options bemenı paraméter követelményeinek. Beállítást módosítani paraméter, érték argumentumok felsorolásokkal lehetséges. Elsı argumentumként megadhatjuk az elızı beállítás stuktúráját, a változások ehhez képest lesznek rögzítve. Ha nem adunk meg semmit, akkor az alapértelmezett értéket fogja visszaadni. Módosítsunk néhány paramétert! >> options = gaoptimset('PopulationSize',1000,'EliteCount',50, 'Generations', 1000, 'TolFun', 1e-42); >> >> ga(@(x) x*x, 1,[],[],[],[],-1,1,[], options) Optimization terminated: average change in the fitness value less than options.TolFun. ans = 0

Növelve a populáció méretét, az iterációk számát, toleraciáját, csökkentve a keresési teret, az egészet kiegészítve némi elitizmussal megkaptuk az optimális megoldást. Természetesen ezt minden esetben nem tudhatjuk, csak azt hogy a fitnessz értékek változása folyamatosan a tolerancián belül van, ami jelen esetben 10 −42 . Mielıtt nagy lenne az örömünk, és elkönyvelnénk, hogy a GA segítségével bármely minimumkeresési feladat megoldható, kellıen nagy populáció és generációszám esetén, el kell hogy mondjam: szerencsénk volt. Valóságban csak 3. futásra kaptam meg ezt az eredményt, és 100 esetbıl is csak 11-szer sikerült reprodukálni.

- 25 -

6.2 Genetic Algorithm Tool A Matlab másik, varázslószerőbb eszköze genetikus algoritmusok futtatására a Genetic Algorithm Tool. Indítása parancssorból a gatool paranccsal vagy a Start / Toolboxes / Genetic Algorithm and Direct Search / Genetic Algorithm Toolbox menüpont alatt érhetı el. Az eszköz kinézete a következı:

Genetic Algorithm Tool 2.0 alapképernyıje

Fıbb funkciói, paraméterei:

Fitness function: Fitnessz függvény megadása. Formája lehet @fgv, ahol fgv.m egy lézetı Matlab függvény, ami skalárértéket ad vissza.

- 26 -

Number of variables: Függvényváltozók száma. A rátermettségi függvény operandusainak száma. Feltételek (Constraints) -

Linear inequalities: lineáris egyenlıtlenségek A ⋅ x ≤ b formájában. Linear equalities: lineáris egyenletek Aeq ⋅ x = beq formájában. Bounds: korlátok, alsó (lower) és felsı (upper) korlátai a vektorelemeknek - Nonlinear constraint function: nemlineáris megszorítások. Ezeket saját magunknak kell megírni, vagy egy meglévı Matlab .m függvényt felhasználni. A meghívandó függvény visszatérési értékei C és Ceq kell hogy legyenek.

Megjelenítı funkciók (Plots) Ezen beállítások szabályozásával az algoritmus egyes lépéseinek fıbb paramétereirıl kaphatunk grafikusan ábrázolt információt, már futás közben. A plot interval mezıbe írt érték a megjelenítés periódusa: minden ennyiedik populációt jelzi ki. A grafikon egy felbukkanó ablakban jelenik meg, ahol a „Stop” gomb hatására le is állíthatjuk a futást. Az elnevezések elég sokat mondóak, részletesebb információt a dokumentációban találhatunk.

Populáció Tulajdonságai (Population) - Population type: egyedek ábrázolási típusa (valós vektor, bitsorozat, egyéni). Egyéni (custom) beállításnál a Creation, Mutation, Crossover funkciókat nekünk kell megírni és beállítani a megfelelı mezıkben. - Population size: populáció mérete, egyedszám. Megadható vektorérték is, ez esetben több szubpopulációval dolgozik az algoritmus párhuzamosan. A vektorértékek az egyes szubpopulációk méreteit határozzák meg. - Creation function: populáció inicializálást végzı függvény. Lehet Uniform, ekkor a beállított paraméterek alapján egyenlı eloszlású véletlen populáció kerül legenerálásra. Vagy megadhatunk saját (Custom) inicializálófüggvényt, ami megfelelı típusú egyedeket ad vissza. - Initial population: megadhatjuk a kezdeti populáció egyedeit kézzel is ebben a mezıben. - Initial scores: kezdeti fitnessz értékeket adhatjuk meg itt. Ha üresen hagyjuk, akkor az algoritmus a fitnessz függvény szerint számítja ki ıket. - Initial range: a kezdeti populáció értékeire adhatunk korlátot egy 2 soros mátrix segítségével. Az elsı sor az egyes vektorkomponensek minimuma, a második sor azok maximuma. Ha csak 2x1-es vektort írunk ide, akkor a Matlab minden vektorkomponensre alkalmazza a kritériumot.

Fitnessz Skálázás (Fitness Scalling) Itt skálázási lehetıségeket állíthatunk be a fittneszfüggvényünkhöz. A Scaling function mezıben választhatjuk ki a megfelelı metódust. A lehetıségek: Rank, Proportional, Top, Shift Linear, Custom. Bıvebb leírás a dokumentációban.

Szelekciós Tulajdonságok (Selection) - Selection function: a szelekció fajtájának formája. A lehetıségek: Stochastic uniform, Remainder (rulett variáns), Uniform (tesztelésre), Roulette, Tournament, Custom. A variánsok mőködését a 2. fejezetben részleteztük.

- 27 -

Utódlási tulajdonságok (Reproduction) - Elite count: elit egyedek száma a populációban, ezen egyedek automatikusan bekerülnek az új populációba. - Crossover fraction: 0 és 1 közötti arányszám, a új populáció nem elitista tagjainak ezen része keresztezéssel kerül feltöltésre, míg a maradék mutációval kerül be.

Mutációs Tulajdonságok (Mutation) A mutációs operátort a Mutation function mezıben lehet kiválasztani. A következıkbıl választhatunk: Gaussian, Uniform, Adaptive feasible, Custom. Bıvebb leírás a dokumentációban.

Keresztezési Tulajdonságok (Crossover) A remkombinációs paramétereket állíthatjuk be. Megvalósítások: Scattered (egyenletes keresztezés), Single point, Two point (kétpontos), Intermediate, Heuristic, Arithmetic (súlyozott átlagértékek szerinti), Custom.

Migrációs Tuljadonságok (Migration) Párhuzamos futtatásnál egy érdekes új lehetıség a migráció fogalma. Itt több szubpopulációval dolgozik az algoritmus egyszerre. Bizonyos generációszámonként az adott szubpopuláció legjobb egyedei migrálódnak a szomszédos szubpopulációba. Ezen egyedek kiszorítják a másik populáció legrosszabb fitnessz értékő egyedeit, miközben az eredeti szubpopulációban is megmaradnak. -

-

Direction: a migráció iránya. Ha elırefelé (Forward) migráció van beállítva, akkor az i. szubpopuláció az i+1-be migrál. Kettıs (Both) migráció esetén i. szubpopuláció i-1. és i+1-be is migrál egyszerre. A szubpopulációk körbeérnek, azaz az utolsó után sorban az elsı következik, ill. fordítva. Fraction: megmondja, hogy az egyes szubpopulációk mekkora része migrálódjon. Értéke 0-1 közötti. Interval: vezérli, hogy milyen periódussal menjen végbe egy migrációs lépés.

Algoritmus Tulajdonságok (Algorithm Setting) Algoritmus specifikus beállításokat tesz lehetıvé. Jelenlegi implementációban nem sok opciót tartalmaz, mindössze a nemlineáris feltételekre büntetı paramétert beállítani, ha a megkötések nem teljesülnek.

Hibrid Függvény (Hybrid Function) Lehetıség van a genetikus algoritmus lefutása után átadni a vezérlést egy másik minimumkeresı algoritmusnak. Választhatunk a Matlab fminsearch, patternsearch, fminunc, fmincon függvényei közül. További információ a felsorolt függvények dokumentációjában olvasható.

Kilépési feltételek megadása (Stopping Criteria) -

Generations: megállási generációszám.

- 28 -

Time limit: maximális futási idı elérése, másodpercben megadva. Fitness limit: a mezıben megadott minimális fitnessz érték elérése (legjobb egyednél vizsgálva). Stall generations: ha a fitnessz értékek súlyozott átlagának változása a mezıben megadott generiószámon keresztül nem éri el a függvény toleranciáját, akkor megáll. Stall time limit: ha a legjobb fitnessz érték nem javul megadott idıhatáron belül (másodpercben), akkor kilép. Function tolerance: tolerancia. Ezt az értéket figyeli a Stall generations mezı. Nonlinear constraint tolerance: nemlineáris feltételrendszer toleranciája. Ha túl sok feltételt sért az algoritmus, akkor leáll.

Kimenet kezelése (Output Function) -

History to new window: felbukkanó ablakban mutatja a futás állapotát, ami jelenlegi verzióban a generációszámot és a legjobb fitnessz értéket jelenti. Interval: a megjelenített információk között eltelt generációk száma. Custom: megadhatunk saját készítéső megjelenítı függvényt, ahol tetszés szerint nyomon követhetjük az algoritmus lépéseit.

Parancssoros megjelenítés beállítása (Display to Command Window) Itt szabályozhatjuk, hogy legyen-e visszajelzés a Matlab standard parancsablakában. A Level of display értéke szerint több/kevesebb információt bocsát rendelkezésünkre az eszköz. Tesztelésnél hasznos lehet a Diagnose beállítása, alapból ez a funkció ki van kapcsolva.

Vektorizálhatóság (Vectorize) Ha ezt a tulajdonságot bekapcsoljuk (On), azzal jelezzük a futtatónak, hogy a fitnessz függvényünk képes a párhuzamos mőködésre, azaz egyszerre egyedek egy vektorát is ki tudja értékelni. Jól megírt függvény esetén ez nagymértékben gyorsíthatja a futást, fıleg nagy populációknál. Kikapcsolt állapotban a rátermettségeket egyedenként hívja meg az algoritmus. Az algoritmus paramétereinek beállítása után a Run solver rész „Start” gombjára kattintva indíthatjuk el az optimalizációt. Leállás, vagy leállítás után a legjobb egyed a bal alsó sarokban a Final point címke alatt olvasható le. Kicsit lejjebb, az „Export to Workspace…” gomb hatására a beállításokat ill. futási eredményeket tartalmazó gaoptions, gaproblem, garesults adatstruktúrák kiexportálhatóak a munkaterületre, ahol tovább vizsgálhatjuk, felhasználhatjuk ıket.

- 29 -

7 Optimalizációs példák Matlab segítségével Eddigi példáink nem voltak túl komolyak, inkább csak az algoritmus mőködésére hivatottak rávilágítani. Nézzünk néhány ismert, bonyolultabb alkalmazást! Matlabék (és talán mások) kedvence a Rastrigin-függvény, a dokumentáció is ezt hozza fel példaként, ha a genetikus algoritmusokról van szó. Ez egy n-változós valós függvény, amely n függvényében a következı formulával adható meg: n

(

)

f ( x ) = 10 ⋅ n + ∑ xi2 − 10 ⋅ cos(2 ⋅ π ⋅ xi ) i =1

Ez a függvény folytonos, differenciálható, és könnyen észrevehetı, hogy minimuma x = 0 pontban van, értéke f ( x) = 0 . Ezen kívül hála a cos függvény periodicitásának, a függvény tele van lokális minimumhelyekkel, ami igen rossz hatással lehet a keresı algoritmusokra. A függvény megtalálható rastriginsfcn néven a Matlab tárházában.

A Rastrigin-függvény képe (n=2, -5 ≤ x1,x2 ≤ 5).

Tegyünk egy próbát: >> x = ga(@rastriginsfcn, 2) Optimization terminated: average change in the fitness value less than options.TolFun. x = 0.0082

0.0001

Az eredmény elfogadható elsı neki futásra. Érdemes megnézni egy konkurens keresı algoritmust. Vegyük a Matlab fminsearch függvényét, nézzük mit tud kezdeni vele: >> fminsearch(@rastriginsfcn, rand(1,2))

- 30 ans = 0.9950

0.9950

Pontosan az történt, amire számítani lehetett. A keresés beleesett egy lokális minimum körüli gödörbe. Míg a GA futásánal a Rastrigin-függvény helyettesítési értéke 0,0133, a minimumkeresı függvény által megtalált közel lokális minimumnál már 1,9899. Azaz az eltérés igencsak szignifikáns. A példa itt jól igazolja a genetikus módszerek gyakorlati létjogosultságát. Nézzünk egy másik példát! Easom függvényét az alábbi képlettel adhatjuk meg:

f Easom ( x1 , x2 ) = cos( x1 ) ⋅ cos( x2 ) ⋅ e −(( x1 −π ) +( x2 −π ) ) 2

2

Ez egy kétváltozós függvény, aminek (π, π) pontnál van globális maximuma, értéke 1. Próbáljuk ki rajta a ga ill. fminsearch algoritmusokat! Mivel ezek minimumkeresı algoritmusok, a függvényünket el kell látnunk egy -1-es szorzóval. Nézzük az eredményeket: >> [x f] = ga(@(x) -cos(x(1)).*cos(x(2)).*exp(-((x(1)-pi).^2+(x(2)-pi).^2)), 2) Optimization terminated: average change in the fitness value less than options.TolFun. x = 3.1561

3.1554

f = -0.9994 >> [x f] = fminsearch(@(x) -cos(x(1)).*cos(x(2)).*exp(-((x(1)-pi).^2+(x(2)-pi).^2)), rand(1,2)) x = 1.3050

1.3050

f = -8.1102e-005

Látható, hogy a GA alkalmazásával egész szép közelítést kaptunk, mindenféle trükközés nélkül egy tizedesjegyre pontos eredményt adott. Az fminsearch számítása viszont valahogy nagyon elcsúszott, és többszöri futtatás után is ragaszkodott ehhez az eredményhez. A probléma itt az, hogy a keresési tér nagyon kicsi része különbözik a többitıl, nincs merre mennie a keresı algoritmusoknak, az egy globális optimum környezetét leszámítva túl kicsi a függvényérték változása.

Easom függvénye, az -20 ≤ x1, x2 ≤ 20 intervallumon.

- 31 A GA mellett szól, hogy az eredmény tovább javítható az algoritmus paramétereinek kellıen jó megválasztásával. Lefuttatva az algoritmust tízszeres egyed- és maximális generációszámra (természetesen jobb toleranciával a fitnesszértékékek változására), máris 5 jegyre pontos közelítést ad az algoritmus a változókra, ami a minimumértéket tekintve már 11 jegy pontosságot jelent. Harmadik példánkban nézzünk egy olyan feladatot, ahol kikötéseket teszünk a megoldásvektorra. Vegyük a következı függvényt és feltéleket:

f ( x1 , x 2 ) = ( x1 − 2 ) 2 + ( x 2 − 1) 2 x 12 − x 2 ≤ 0 x1 + x x1, x

2

2

≤ 2

≥ 0

Mivel a példánk nemlineáris feltételt is tartalmaz, meg kell írnunk egy .m fájlban az azt lekezelı függvényt. Nevezzük ezt c.m-nek, és a következıket tartalmazza: function [C Ceq] = c(x) C = x(1).^2-x(2); Ceq = [];

Figyelni kell a kimenı értékek formátumára, a ga ilyen néven várja ıket! A függvényhívás paraméterezése is bonyolultabb, a teljes általános formát kell használnunk. Az elsı feltételt a c.m függvény, a másodikat az algoritmus 3-4. paramétere kezeli. A nemnegativitást egyszerő intervallum megszorítással követeljük meg. >> [X f] = ga(@(x) (x(1)-2).^2+(x(2)-1).^2,2,[1 1],[2],[],[],[0 0],[],@c) Optimization terminated: current tolerance on f(x) 8.9125e-007 is less than options.TolFun and constraint violation is less than options.TolCon. X = 0.99994297633626

1.00003809187953

f = 1.00011405203017

Érdemes megfigyelni, hogy kilépésnél jelzi, hogy a feltételektıl nem tértünk el a megadott küszöbnél jobban. A feladat optimális megoldása (1,1) pontban van, vagyis algoritmusunk alapbeállítások mellett is már 4 jegyre pontosan megközelítette mindkét komponensével. Természetesen a paraméterek állítgatásával itt is elérhetünk jobb pontosságot.

- 32 -

8 Költség és hatékonyságelemzés Nehéz egy olyan módszer hatékonyságát elemezni, ami nemdeterminisztikus lépéseket használ mőködése közben. Egy adott GA implementáció futása a véletlen elemek miatt mindig változik, nincs két egyforma kimenető futás (hacsak nem nagyon triviális az algoritmus, vagy nagyon rossz a véletlenszám generátor adott megvalósításnál). Így nem sok értelme lenne összehasonlító futási eredményeket nézegetni, fıleg ilyen példák esetében ahol az abszolút futási idı legdurvább esetben is csak néhány másodperc. Nézzük meg milyen tényezık befolyásolják a GA költségét!




Populáció mérete A populáció mérete nyilvánvalóan alapvetıen befolyásolja mind a futás, mind a tárhely igényét. Maga az algoritmus µ aszimptotikus függvénye lesz.




Generációk száma A generációk számával egyenesen arányos a futási idı, mivel minden új generáció egy új fıciklus lefuttatását igényli. Mivel a kilépési feltétel nemcsak a maximális generációszámtól függ, elıbb is terminálhat az algoritmus, nem feltétlenül igaz, hogy egy 10x nagyobb generációszámmal paraméterezett algoritmus 10x annyi ideig fut.




Szelekció A szelekció GA esetében µ függvénye, mivel pont ennyi szülıt kell kiválasztanunk (elitista módszer esetén ennek egy részét). Ez a megvalósításoktól függıen általában lineáris költségő, de bizonyos esetekben (pl. pár-verseny szelekció) lehet nagyobb is.




Rekombináció, mutáció Hasonlóan a szelekcióhoz, ez is a µ függvénye, megvalósítástól függıen. Viszont itt már bizonyos esetekben a futási költségbe beleszólhat az egyedek reprezentációja. Ugyanis több esetben a gének számával arányos az egyedek keresztezése ill. mutációja. Természetesen több gén esetén tovább tart ezek elvégzése.




Visszahelyezés A visszahelyezés mővelete σ(1) általában, mivel egyszerően csak a régi populációt megfeleltetjük az újonnan kialakítottal. Olyan esetekben viszont, amikor az algoritmus nem generációs, lehetséges nagyobb költségő megvalósítás is.




Fitnessz kiértékelés A fitness kiértékelés nagyban függ a kiértékelı függvénytıl. Vizsgált eseteinkben ez σ(1), de könnyen elképzelhetı igen bonyolult fittnesz függvény is.

Végezetül nézzünk azért meg egy nagyon egyszerő összehasonlítást. Globális minimum keresése az elsı példánkban vett f ( x) = x 2 függvénynél. Versenyeztessük meg a ga és az

- 33 fminsearch algoritmusokat! A „feladat” komplexitása miatt azt várjuk, hogy az utóbbi lesz a

nyertes. És tényleg, lefuttatva alapbeállításokkal, 100 futás átlagára azt kapjuk, hogy kb. 1213-szor gyorsabb, mint a GA megvalósítás. Ráadásul az eredmény átlag 15-16 jegyre pontos, míg a genetikus metódus 4-7 jegyig egyezı eredményeket tud csak produkálni. Javítva a GA paraméterezésén, némi kisérletezés után ezt sikerül annyira lefaragni, hogy azonos pontosság mellett (sıt a GA jóval pontosabb eredményeket is adott, csak sajnos igen nagy volt a megoldások szórása) mindössze 5-ször annyi idıbe telik lefuttatni a ga parancsot, mint társát. Mit mutat ez meg? Nem többet és nem is kevesebbet, mint amire számítottunk. Látszik, hogy ilyen típusú feladatnál érdemesebb a hagyományos keresı technikákat alkalmazni, fıleg hogy ezeknek igen jó megvalósítása adva van Matlab környezetben. A probléma túl egyszerő, túl költséges egy párhuzamos számításokat alkalmazó eljárást használata. Érdemes viszont azt is megfigyelni, hogy a paraméterek helyes beállítása milyen nagymértékben tudja befolyásolni a futás költségét és kimenetelét. További futási idı teszteken azt kaptam, hogy mind a Rastrigin-függvény, mind Easom függvénye esetében megmaradt az fminsearch 10-15-szörös sebességkülönbsége, alapbeállítások mellett. Cserébe nem ad helyes eredményt egyikre sem… Ebbıl olyan következtetést vontam le, hogy GA alkalmazása olyan esetekben célszerő ahol jobb eredményt várunk tıle, mint a hagyományos keresı algoritmusoktól, vagy ahol azok nem használhatóak. Bizonyos esetekben jó megoldás lehet az algoritmusok keverése: egy alacsonyabb költségő keresı eljárás segítségével információt szerzünk a problémáról, amit felhasználhatunk a késıbbi GA paraméterezésénél.

- 34 -

9 Irodalomjegyzék 1. Borgulya István: Evolúciós algoritmusok, Dialógus Campus Kiadó, Pécs, 2004 2. Futó Iván: Mesterséges Intelligencia, Aula Kiadó, Budapest, 1999 3. Genetic Algorithm and Direct Search Toolbox 2.0 http://www.mathworks.com/products/gads 4. Generation5 website - http://www.generation5.org 5. Adam Marczyk: Genetic Algorithms and Evolutionary Computation http://www.talkorigins.org/faqs/genalg/genalg.html 6. The Genetic Algorithms Archive - http://www.aic.nrl.navy.mil/galist 7. Dorsey and Mayer: Journal of Business and Economic Statistics, January 1995 8. Genetic and Evolutionary Algorithms: Principles, Methods and Algorithms http://www.systemtechnik.tu-ilmenau.de/~pohlheim/GA_Toolbox/algindex.html 9. Hartmut Pohlheim weboldala - http://www.pohlheim.com 10. GEATbx: Genetic and Evolutionary Algorithm Toolbox for use with Matlab http://www.geatbx.com

- 35 -

10 A helloga.m függvény tartalma %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

function y = helloga(str) % HELLOGA(STR) % % STR-ben megadott sztring kitenyésztése genetikus algoritmussal. % Paraméter nélkül hívva a 'Hello World!' üzenetet próbálja elérni. % % 'Hello World!' - Genetikus Algoritmus demo függvény Matlabhoz (version 6.5) % % Készítette: Raffai Tamás % Szeged, 2005-11-10 %Stratégiai paraméterek beállítása GA_TARGET = 'Hello World!'; GA_POPSIZE = 1000; GA_MAXITER = 100; GA_ELITRATE = 0.1; GA_MUTATION = 0.25; PRINTOUT = 10;

% % % % % %

default célstring populáció egyedszáma maximális iterációszám elitráta mutációs ráta eredmény kiíratás periódusa

if nargin>0 GA_TARGET = str; end % t := 0, populációk számának inicializálása t = 0; % P kezdeti populáció létrehozása P = floor (rand(GA_POPSIZE, length(GA_TARGET)) * 96 + 32); F = sum(abs(P-ones(GA_POPSIZE,1)*GA_TARGET), 2); % WHILE NOT Kilépési_feltétel(P) while t < GA_MAXITER & F(1) ~= 0 megoldás

% kilépési feltétel: iterációk száma v.

% Aktuális populáció sorbarendezése [F, I] = sort(F); for i = 1 : length(I) TMP(i, :) = P(I(i), :); end P = TMP; y = char( P(1, :)); % legjobb egyed % Algoritmus futásáról tájékoztatni illik a felhasználót if rem (t, PRINTOUT) == 0 str = sprintf('%d. generáció legjobb egyede: %s fitness: %d', t, y, F(1)); disp (str); end % Elitek beválogatása elitek = floor (GA_ELITRATE * GA_POPSIZE); Puj(1:elitek,:) = P(1:elitek,:);

- 36 -

% Szelekció (a fennmaradó helyekre) for i = elitek+1 : GA_POPSIZE e1 = floor( rand * GA_POPSIZE + 1); e2 = floor( rand * GA_POPSIZE + 1); crp = floor( rand * length(GA_TARGET) + 1); % Rekombináció Puj(i, :) = [P(e1, 1:crp), end

% anyuci % apuci % keresztezési pont

P(e2, (crp+1):length(GA_TARGET))];

% Mutáció (várható érték alapján) for i = 1 : GA_POPSIZE*GA_MUTATION Puj (floor(rand*GA_POPSIZE)+1, floor(rand*length(GA_TARGET))+1) = floor(rand * 96 + 32); end % Visszahelyezés P = Puj; % P egyedeinek kiértékelése az F fitnessz függvény alapján F = sum(abs(P-ones(GA_POPSIZE,1)*GA_TARGET), 2); % Populációszám (iterációszám) növelése t = t + 1; end % WHILE ciklus vége % Legjobb fitnessz értékkel rendelkezı egyed kiválasztása [F, I] = sort(F); y = char(P(I(1), :)); if F(1) == 0 disp('Optimális érték elérve.'); else disp('A program elérte a maximális generációszámot optimum nélkül.'); end % end of helloga %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

- 37 -

11 A gaoptimset struktúra elemei Option

Description

Values

CreationFcn

Handle to the function that creates the initial population

{@gacreationuniform}

CrossoverFraction

The fraction of the population at the next generation, not including elite children, that is created by the crossover function

Positive scalar | {0.8}

CrossoverFcn

Handle to the function that the algorithm uses to create crossover children

@crossoverheuristic {@crossoverscattered} @crossoverintermediate @crossoversinglepoint @crossovertwopoint @crossoverarithmetic

EliteCount

Positive integer specifying how many individuals in the current generation are guaranteed to survive to the next generation

Positive integer | {2}

FitnessLimit

Scalar. If the fitness function attains the value of FitnessLimit, the algorithm halts.

Scalar | {-Inf}

FitnessScalingFcn

Handle to the function that scales the values of the fitness function

@fitscalingshiftlinear @fitscalingprop @fitscalingtop {@fitscalingrank}

Generations

Positive integer specifying the maximum number of iterations before the algorithm halts

Positive integer |{100}

PopInitRange

Matrix or vector specifying the range of the individuals in the initial population

Matrix or vector | [0;1]

PopulationType

String describing the data type of the population

'bitstring' | 'custom' | {'doubleVector'}

HybridFcn

Handle to a function that continues the optimization after ga terminates

Function handle | @fminsearch @patternsearch @fminunc @fmincon {[]}

InitialPopulation

Initial population used to seed the genetic algorithm

Matrix | {[]}

InitialScores

Initial scores used to determine fitness

Column vector | {[]}

InitialPenalty

Initial value of penalty parameter

Positive scalar | {10}

PenaltyFactor

Penalty update parameter

Positive scalar | {100}

MigrationDirection Direction of migration

'both' | {'forward'}

MigrationFraction

Scalar between 0 and 1 specifying the fraction of individuals in each subpopulation that migrates to a different subpopulation

MigrationInterval

Positive integer specifying the number of generations that take Positive integer | {20} place between migrations of individuals between subpopulations

MutationFcn

Handle to the function that produces mutation children

@mutationuniform @mutationadaptfeasible {@mutationgaussian}

OutputFcns

Functions that ga calls at each iteration

@gaoutputgen |{[]}

PlotFcns

Array of handles to functions that plot data computed by the algorithm

@gaplotbestf @gaplotbestindiv @gaplotdistance @gaplotexpectation @gaplotgeneology @gaplotselection @gaplotrange @gaplotscorediversity @gaplotscores @gaplotstopping | {[]}

Scalar | {0.2}

- 38 -

Option

Description

Values

PlotInterval

Positive integer specifying the number of generations between consecutive calls to the plot functions

Positive integer | {1}

PopulationSize

Size of the population

Positive integer | {20}

SelectionFcn

Handle to the function that selects parents of crossover and mutation children

@selectionremainder @selectionrandom {@selectionstochunif} @selectionroulette @selectiontournament

StallGenLimit

Positive integer. The algorithm stops if there is no improvement in the objective function for StallGenLimit consecutive generations.

Positive integer | {50}

StallTimeLimit

Positive scalar. The algorithm stops if there is no improvement in the objective function for StallTimeLimit seconds.

Positive scalar | {20}

TolFun

Positive scalar. The algorithm runs until the cumulative change in the fitness function value over StallGenLimit is less than TolFun.

Positive scalar | {1e-6}

TolCon

Positive scalar. TolCon is used to determine the feasibility with respect to nonlinear constraints.

Positive scalar | {1e-6}

Display

Level of display

'off' | 'iter' | 'diagnose' | {'final'}

TimeLimit

Positive scalar. The algorithm stops after running for TimeLimit seconds.

Positive scalar | {Inf}

Vectorized

String specifying whether the computation of the fitness function is vectorized

'on' | {'off'}