Intelligens Rendszerek Elmélete Dr. Kutor László
Párhuzamos keresés genetikus algoritmusokkal http://mobil.nik.bmf.hu/tantargyak/ire.html login: ire jelszó: IRE07 2009. ősz
BMF NIK,
Dr. Kutor László
IRE 5/1
A természet általános kereső algoritmusa: a genetikus algoritmus
2009. ősz
BMF NIK,
Dr. Kutor László
IRE 5/2
Az élet információ tárolói
2009. ősz
BMF NIK,
IRE 5/3
Dr. Kutor László
Orvosi Nobel díj 2009. (okt. 5)
Elisabeth Blackburn (ausztráliai-amerikai)
Carol Greider, (amerikai)
Jack W. Szostak (angol-amerikai)
A telomerek és a telomeráz enzim felfedezéséért IRE 5/4
Természetes és mesterséges genetikus terminológia Természetes
Mesterséges
Kromoszóma Karakterfüzér (sztring) (a sejtek örökletes tulajdonságokat hordozó anyaga) Gén Jellemző, karakter (az öröklődő tulajdonságokkat hordozó kromoszóma egy része, (nukleinsav molekula)) Allél A karakter (jellemző) értéke Lókusz Karakter pozíció Genotípus Karakterfüzér szerkezet (az örökletes tulajdonságok összessége) Fenotípus Paraméter készlet (az élőlény alaktani és élettani sajátosságainak összessége. Az örökletes és a környezet együttes hatására létrejött megjelenési alak) IRE 5/5 2009. ősz BMF NIK, Dr. Kutor László
A genetikus algoritmus (GA) alkalmazási vázlata 1. Az optimalizálandó rendszer leírása (mesterséges kromoszómába) A rendszerre jellemző változók egymást követő generációk
2. Kezdeti generáció
GA GA 3. GA sorozatos alkalmazása 2009. ősz
BMF NIK,
GA Dr. Kutor László
GA IRE 5/6
A genetikus algoritmus alkalmazásának feltételei
1. Egyértelmű rendszerleírás egy rendszerváltozókat tartalmazó karakterfüzérbe az un. mesterséges kromoszómába. 2. Reprezentatív populáció, ami azonos formában különböző jellemzőkkel bíró egyedek (rendszerek) leírását tartalmazza. 3. Alkalmas mérési módszer, mellyel a vizsgált rendszerek jóságát meg lehet határozni. 2009. ősz
BMF NIK,
Dr. Kutor László
IRE 5/7
A genetikus algoritmusok operátorai Andrew Z. Fire Szelekció Craig C. Mello Kereszteződés Orvosi Nobel díj Mutáció 2006. 10. 2. Alacsony szintű operátorok: Mario Capecchi Dominancia Oliver Smithies Inverzió Martin Evans Törlődés 2007. 10. 08 Halkítás (erősítés) Kikapcsolás „knock out” Populációra vonatkozó operátorok: Migráció Alap operátorok:
„Házassági” korlátozás Jóság transzformáló függvények 2009. ősz
BMF NIK,
Dr. Kutor László
IRE 5/8
Kiválasztási mechanizmusok A relatív jósággal (fitness) arányos un. rulettkerék algoritmus Csak a legjobbakat kiválasztó algoritmus „ elicista”
S =
n
∑F i =1
i
Paraméterek: populáció méret, Reprodukciós arány (állandó, csökkenő, bővülő,..) 2009. ősz
BMF NIK,
Dr. Kutor László
IRE 5/9
A genetikus algoritmus alkalmazásának menete
1. A mesterséges kromoszóma (leíró adatfüzér) 2. 3. 4. 5.
szerkezetének kidolgozása (változók és jellemzői) Kezdeti populáció létrehozása A populációt alkotó egyedek értékelése, az abszolút- majd a relatív jóság meghatározása A genetikus operátorok alkalmazásával új populáció létrehozása (pl.:szelekció, keresztezés, mutáció, stb…) A 3.-ik és a 4.-ik lépés ismétlése, amíg a megállási feltétel nem teljesül.
2009. ősz
BMF NIK,
Dr. Kutor László
IRE 5/10
A relatív jósággal (fitness) arányos un. rulettkerék algoritmus 1. Az egyedek jóságának meghatározása: Fi=f(Ii) 2. A populáció összes tagja jóságának meghatározása: S = ∑F 3. Az egyedek relatív jóságának kiszámítása: n
i =1
i
(Teljes Relatív Fitness TRF=1): 4. 1 és 100 közötti szám hozzárendelése a populáció minden tagjához a relatív jóságuknak megfelelően. (n = a jelenlegi populáció mérete) 5. Egy „m” véletlen szám generálása 1 és 100 között (m: az új populáció mérete) 6. m egyed (génstruktúrájának) másolása az új generációba, 2009. ősz
BMF NIK,
IRE 5/11
Dr. Kutor László
Kereszteződés Paraméterek:
kereszteződési pontok száma kereszteződési pontok helye
kiinduló sztringek: X
X 1
X 2
X 3
X 4
X 5
X 6
X X 7 8
Y
Y 1
Y 2
Y 3
Y 4
Y 5
Y 6
Y Y 7 8
X’
X 1
X 2
X 3
X 4
Y 5
Y 6
Y 7
Y 8
Y’
Y 1
Y 2
Y 3
Y 4
X 5
X 6
X 7
X 8
új sztringek:
2009. ősz
BMF NIK,
Dr. Kutor László
IRE 5/12
Mutáció Paraméterek:
mutációs helyek száma mutációs változás tartománya
2009. ősz
kiinduló sztring:
X
X 1
X 2
X 3
X 4
X 5
új sztring:
X’
X 1
M X 2 3
X 4
M M X 5 6 7
BMF NIK,
X 6
X X 7 8
M 8
Dr. Kutor László
IRE 5/13
A genetikus algoritmus előnyei a hagyományos kereső algoritmusokhoz képest A keresési tér több pontját vizsgálja egyszerre (párhuzamosság) Csak jellemzőket tartalmazó sztringgel dolgozik, a változók értelmezésétől függetlenül, ezért általános keresési algoritmus A véletlenszerű változók használata miatt a lokális minimumokra kevésbé érzékeny. Mivel a keresési szabályok nem determinisztikusak, hanem valószínűségi szabályokat alkalmaznak, így az NP teljes jellegű problémákra is megközelítést adhat. 2009. ősz
BMF NIK,
Dr. Kutor László
IRE 5/14
A genetikus algoritmusok korlátai Túlságosan nagy jóságú egyedek eluralhatják a populációt Ha csak minimális különbségek vannak az egyedek között akkor nincs javulás Részleges megoldások: Különböző jóság transzformáló eljárások a keresés előrehaladtával (pl. nagy különbségek kiegyenlítése a keresés elején, kis különbségek felnagyítása a keresés vége felé)
fg(xi) = αg + βg f(xi) 2009. ősz
BMF NIK,
IRE 5/15
Dr. Kutor László
Példa a GA alkalmazására 5
x2 f(x) = 3x12 + 2x22 + 3.5x32 +4x42 + 2.7x52e –Σ i=1 i
xi értelmezési tartománya -10-től +10-ig Kezdeti populáció száma: 20 Megállási feltétel: f(x) >=1.1471, vagy 105 generáció Eredmények: x1, x2, x3, x4, x5 elért generációk száma
Példa megoldás:
x1= 0.0000005267=0, x2= 0.000000015805=0, x3= 0.000000542=0, x4= 1.0.000002049=-1, x5=0.0000005267=0, g= 78967 IRE 5/16 2009. ősz BMF NIK, Dr. Kutor László
Kérdések • Milyen tényezők befolyásolják a genetikus algoritmusok sikeres alkalmazását? • Milyen problémák megoldásában segíthet a genetikus algoritmusok alkalmazása? • 3. Lehet-e gyors eredményt elérni genetikus algoritmusokkal?
2009. ősz
BMF NIK,
Dr. Kutor László
IRE 5/17
