Genetikus algoritmusok globális optimalizálás sok lehetséges megoldás közül keressük a legjobbat értékel® függvény: rátermettségi függvény ( tness function) populáció kiválasztjuk a legrátermettebb egyedeket keresztezési (rekombinációs) és mutációs m¶veletekkel aktualizáljuk keresztezés 1. szül® 1 0 0 | 0 1 1 1 2. szül® 1 1 1 | 1 0 0 0 1. utód 1 0 0 | 1 0 0 0 2. utód 1 1 1 | 0 1 1 1 mutáció eredeti 1 0 0 0 1 1 1 mutált 1 1 0 0 1 1 1
1
A genetikus algoritmus f®bb lépései: 1. (Kezdet) Véletlenszer¶en el®állítunk egy N elem¶ populációt (elemei egyedek v. kromoszómák). 2. (Rátermettség vizsgálata) Kiszámítjuk minden egyed rátermettségét. 3. (Új populáció el®állítása) a. (Kiválasztás) Kiválasztunk két egyedet (bizonyos kritérium alapján). b. (Keresztezés) Keresztezzük a két kiválasztott egyedet. c. (Mutáció) A két utódegyeden mutációt hajtunk végre. 4. (Helyettesítés) Helyettesítjük a régi populációt az újjal. 5. (Ellen®rzés) Ha a leállási feltétel igaz, akkor vége. Különben folytassuk a 2. lépéssel.
2
Kiválasztási kritériumok • elitista kiválasztás: a legrátermettebb egyedek kiválasztása • arányos kiválasztás: a legrátermettebbek a legvalószín¶bbek, de nem feltétlenül • rulettkerék kiválasztás: a rátermettebbek nagyobb szeletet kapnak a rulettkeréken, amely véletlenszer¶en áll meg egy adott helyen • skálázott kiválasztás: a rátermettségi függvény változik, ahogy az átlagos rátermettség n® • verseny típusú kiválasztás: az egyedek részcsoportjain belül mindenki mindenkivel versenyzik. Minden csoportból csak egy kerül tovább. • rang szerinti kiválasztás: minden egyed kap egy rangot (a rátermettség alapján), és e szerint választódik ki, nem az abszolút különbség alapján • generációs kiválasztás: csak új egyedek kerülnek az új generációba, a régiek kimaradnak • stationárius állapotú kiválasztás: bizonyos kiválasztott egyedek visszakerülnek egy el®z® generációba, hogy a gyengébb egyedeket helyettesítsék • hierarchikus kiválasztás: szinteken keresztül történik a kiválasztás
3
Hátizsákfeladat hátizsák kapacitása K s1, s2, . . . , sn tömeg¶ tárgyak, az i-edikb®l ni darab van (1 ≤ ni < ∞), e1, e2, . . . , en érték¶ek, megoldás: x1, x2, . . . , xn feladat: (
s1 x 1 + s2 x 2 + . . . + sn x n ≤ K 0 ≤ xi ≤ ni,
i = 1, 2, . . . , n
max(e1x1 + e2x2 + . . . + enxn)
Ha minden ni = 1, akkor 0-1 hátizsákfeladatról beszélünk. 0-1 hátizsákfeladat tömegek: (s1, e1)|(s2, e2)| · · · |(sn, en)
megoldás: x1|x2| · · · |xn (kromoszóma) xi = 1, ha az i-edik tárgy bekerül a zsákba
4
Az algoritmus f® lépései: 1. Inicializáljuk az els® generációt (N kromoszóma) 2. repeat 3. minden kromoszómára számítsuk ki az össztömeget és rátermettséget (nyereséget) 4. if a kromoszómáknak kevesebb, mint 90%-a azonos nyereség¶ 5. then válasszunk ki véletlenszer¶en két kromoszómát 6. keresztezzük ®ket, 7. majd hajtsunk végre mindkét utódon mutációt 8. until legalább 90% kromoszóma azonos nyereség¶ vagy a lépésszám nagyobb a fels® korlátnál A rátermettségi függvény Minden kromoszómára a populációból végezzük el: 1. while igaz 2. do számítsuk ki az össztömeget és nyereséget 3. if össztömeg ≤ K 4. then return össztömeg, nyereség 5. else véletlenszer¶en válasszunk ki egy 1-est 6. állítsuk 0-ra a megfelel® értéket
5
Verseny típusú (csoportos) kiválasztás rátermettségi függvény f (i) az i-edik tárgy rátermettségi függvénye i 0 1 2 3 4 5 6 7 8 9 10 11 f (i) 40 20 5 1 9 7 38 27 16 19 11 3
Csökken® sorrendben f értéke szerint a tárgyak indexe: 0 1 2 3 4 5 6 7 8 9 10 11 0 6 7 1 9 8 10 4 5 2 11 3
4 csoportra osztjuk a tömböt (indexek alapján): 02 35 68 911 Véletlenszer¶en választunk: 50%-os valószín¶séggel választunk az 1. csoportból, 30%-os valószín¶séggel választunk a 2. csoportból, 15%-os valószín¶séggel választunk a 3. csoportból, 5%-os valószín¶séggel választunk a 4. csoportból.
6
Véletlenszer¶en generálunk egy 0 − 99 közötti számot, ha 0 − 49 közötti, akkor az 1. csoportból választunk véletlenszer¶en egy elemet, ha 50 − 89 közötti, akkor az 2. csoportból választunk véletlenszer¶en egy elemet, ha 90 − 94 közötti, akkor az 3. csoportból választunk véletlenszer¶en egy elemet, ha 95 − 99 közötti, akkor az 4. csoportból választunk véletlenszer¶en egy elemet.
7
Utazó ügynök problémája (Traveling Salesman Problem) n város: 1, 2, 3, . . . , n, közöttük adott távolsággal feladat: legrövidebb körút meghatározása Kromoszóma: az 1, 2, 3, . . . , n számok egy permutációja. Egyéb feladatok: • függvények maximuma • gráfszínezés
Három példa (Javaban): http://www.obitko.com/tutorials/genetic-algorithms
8
A genetikus algoritmus el®nyei gyors kis er®forrásigény egyszer¶ és olcsó implementáció globális optimumot talál A genetikus algoritmus hátrányai matematikailag nem bizonyítható a megoldás helyessége nem mindig konvergál
9
