Számítógépes döntéstámogatás Genetikus algoritmusok ´ Werner Agnes ´ oki ¨ es ´ Informaci ´ os ´ Rendszerek Tanszek ´ Villamosmern
e-mail:
[email protected]
BLSZM-10 – p. 1/18
´ Bevezetes • 1950-60-as évek biológiai evolúció - mérnöki problémák -
optimalizálási feladatok • Darwini evolúciós elmélet • Genetika • Evolúciós módszerek • Genetikus algoritmusok - John Holland (1975) • Többpontos, párhuzamos keresés - robosztusság
BLSZM-10 – p. 2/18
´ os ´ feladatok Optimalizaci • az ellenállás meghatározása a mért áramerosség ˝ és
feszültség segítségével • a sebesség számítása a mért idob ˝ ol ˝ és a megtett
távolságból • a napi beosztások megtervezése • két város között az optimális út megkeresése • adott eroforrások ˝ mellett az eredmény maximalizálása • adott gazdasági cél mellett a ráfordítás minimalizálása • menükészítés
BLSZM-10 – p. 3/18
´ asi ´ feladatok Optimalizal Az optimalizálási feladatok során egy adott halmazon (keresési tér, S ) definiált függvény (fitnesz függvény, f ) maximumhelyét (vagy minimumhelyét) keressük. Vannak hagyományos módszerek: • hegymászó módszer (gradiens módszer) véletlen pontot
választunk a keresési térben, • szimulált lágyítás (szimulált lehutés) ˝ véletlenszeruen ˝
választjuk meg a lépés irányát a keresési térben Evolúciós algoritmusok: • evolúciós stratégia • evolúciós programozás • genetikus algoritmusok • genetikus programozás
BLSZM-10 – p. 4/18
´ anos ´ ´ algoritmus pszeudo-k ´ odja ´ Altal evoluci ´ os • t := 0 {kezdeti ido˝ beállítása} • initpopulacio Pt {kezdeti populáció létrehozása} • f itneszszamit Pt {fitneszértékek kiszámítása} • while amíg nincs kész do • Pt′ := szulokivalasztas Pt {szülok ˝ választása} • keresztez Pt′ {a szülok ˝ génjeinek keresztezése} • mutacio Pt′ {véletlen mutáció} • f itneszszamit Pt′ {az új fitnesz kiszámítása} • Pt+1 := tulelo(Pt , Pt′ ) {az új populációba kerülnek az
egyedek} • t := t + 1 • end while
Az algoritmus konvergál. BLSZM-10 – p. 5/18
Genetikus algoritmusok • 1975 John Holland • a megoldásokat nem az eredeti feladatnak megfelelo˝
formában tárolja - kromoszóma • a muveleteket ˝ a kromoszómákon hajtjuk végre • szelekció • rekombináció • mutáció • egyedek fitneszértéke
BLSZM-10 – p. 6/18
˝ GA jellemzoi • több pontos keresést valósítanak meg • flexibilisek • robosztusak • biztosítják, hogy elfogadható idon ˝ belül elfogadhatóan jó
megoldást találjunk • a problémának nem egy, hanem több különbözo, ˝ közel
optimális megoldását nyújthatja, amelyek közül a ˝ felhasználó kiválaszthatja a neki leginkább megfelelot
BLSZM-10 – p. 7/18
¨ esi ´ sem ´ aja ´ A genetikus algoritmus muk ˝ od
BLSZM-10 – p. 8/18
´ azol ´ asi ´ formaja ´ Az egyedek abr • Bináris vektor
Genotípus formát jelent Jelölje az (x1 , x2 , . . . , xn ) valós (egész) vektor az egyed tulajdonságait. Bináris ábrázolásban az egyed egy sztringként jelenik meg: x1 , x2 , . . . , xi , . . . , xn . . . 00|11010111|01 . . .
az xi változó kódolt értékei
BLSZM-10 – p. 9/18
Szelekcio´ Rulett szelekció: • Fitnesz arányos szelekció, amely az egyedeket fitnesz
értékük abszolut értékének arányában választja ki a szelekciós állományból. • Visszatevéses muvelet ˝ • Egy egyed kiválasztását a szelekciós valószínuség ˝
határozza meg: P (Ei ) =
P nf (Ei ) j=1 f (Ej )
f a fitnesz függvény, Ei (i = 1, . . . , n) az egyedek
BLSZM-10 – p. 10/18
Rulett szelekcio´ • veszünk egy rulettet • feleltessünk meg minden Ei egyednek valamely kiindulási
pontból folyamatosan egy-egy körszeletet • generálunk egy [0, 1]-beli véletlen számot, a véletlen számot
ívhossznak tekintjük • azt az egyedet választjuk, amelynek körszeletében az ív
˝ végzodik • egy µ elemu˝ szelekciós halmazból a választást µ-ször kell
˝ állománya megismételni, amíg kialakul a szülok A kiválasztott egyedek közt µ ∗ p(Ei ) (i = 1, . . . , n) várható számú másolata lesz az Ei egyednek.
BLSZM-10 – p. 11/18
Versengo˝ szelekcio´ • Az egyedek fitnesz értékeinek sorrendjét használja fel. • Nem fog növekedni az egyed duplikációk száma. • Több egyedbol ˝ a legjobb fitnesz értéku˝ egyedet választja ki.
(Biológiai szelekciót modellezi.)
BLSZM-10 – p. 12/18
Versengo˝ szelekcio´ Lépések: 1. Input: A szelekciós állomány Ei elemei és f (Ei ) fitnesz értékei (i = 1, . . . , n), tour paraméter ˝ állománya): Ei′ 2. Output: A populáció a szelekció után (szülok
(i = 1, . . . , n)
3. for i = 1 to µ do 4.
for k = 1 to tour do
5.
válasszunk egy j ∈ {1, . . . , n} indexet véletlenszeruen ˝
6.
Tk = Ej
7.
od
8.
Ei′ = Tj ha f (Tj ) = max(f (T1 ), . . . , f (Ttour ))
9. od A kiválasztott egyedek közt µ ∗ p(Ei ) (i = 1, . . . , n) várható számú másolata lesz az Ei egyednek.
BLSZM-10 – p. 13/18
´ o´ Rekombinaci • szelekció után keletkezo˝ szülo˝ állomány ◦ tartalmazhat ismétlodéseket ˝ ◦ részben vagy egészben azonos lehet a populációval • ketto-több ˝ ˝ szülo˝ felhasználásával képez utódot (jellemzoen
˝ ol ˝ egyet vagy kettot) ˝ kettob • célja: a szülokb ˝ ol ˝ minél jobb, újabb megoldások
összeállítása az átvett, "örökölt" tulajdonságok alapján • formáját befolyásolja a változók típusa és a problémák
sajátosságai • Pr ≈ 0, 7
BLSZM-10 – p. 14/18
´ sztringek rekombinaci ´ oja ´ Binaris • Egypontos keresztezés ◦ két szülob ˝ ol ˝ két utód ◦ véletlenszeruen ˝ választunk keresztezési pontot az
{1, 2, . . . , L − 1} pozíciók közül • Többpontos keresztezés ◦ két szülob ˝ ol ˝ két utód ◦ n számú keresztezési pontot választunk ◦ a kapott keresztezési pontokat növekvo˝ sorrendbe
˝ egymás után következo˝ rendezzük, majd a megfelelo, keresztezési pontok közti bitsorozatokat rendre ˝ ol ˝ választjuk más-más szülot
BLSZM-10 – p. 15/18
´ o´ Mutaci A rekombináció nem alkalmas finom közelítések megvalósítására. A mutáció az utód közvetlen környezetében keres jobb megoldásokat. Pm ≈ 0, 01 Bináris típusú változók mutációja az egyed egy bitsorozat, melynek egyes bitjeit mutációval változtatjuk ˝ a mutáció egy xi változónál a következo: ( xi , ha Rnd > Pm zi = 1 − xi , ha Rnd ≤ Pm
BLSZM-10 – p. 16/18
´ Az EA ciklus kialak´ıtasa • stratégiai paraméterek megadása ◦ populáció mérete ◦ a rekombináció alkalmazásának Pr valószínusége ˝ ◦ a mutáció alkalmazásának Pm valószínusége ˝ ◦ az utódképzési ráta értéke ◦ a visszahelyezési ráta értéke • kezdo ˝ populáció kialakítása ◦ véletlenszeru˝ eloállítás ˝ ◦ eloz ˝ o˝ feladat eredményeinek felhasználása ◦ korábbi eredmények módosított felhasználása
BLSZM-10 – p. 17/18
´ Az EA ciklus kialak´ıtasa megállási feltétel
• • • • •
maximális generációszám elérése maximális futási ido˝ elérése ˝ adott ido˝ alatt nem javul a megoldás minosége hasonlóak az egyedek ˝ adott érték megközelítése elore
fitnesz kiértékelés
•
A problémák legtöbbjénél ismerünk egy célfüggvényt, amely az értelmezési tartomány, azaz a keresési tér pontjaihoz egy valós számot vagy vektort rendel.
• •
Az esetek többségében a fitneszfüggvényt azonosnak választjuk a célfüggvénnyel.
•
Konkrét formája függ a reprezentációtól.
Sokszor nincs célfüggvényünk és a fitneszfüggvény megfogalmazása a probléma megoldásának egyik fontos kulcseleme.
BLSZM-10 – p. 18/18
