Intelligens technikák k a

Intelligens technikák a döntéstámogatásban Genetikus algoritmusok

Starkné Dr. Werner Ágnes

PDF created with pdfFactory trial version www.pdffactory.com

Bevezetés A 60-as években merült fel először az a gondolat, hogy az evolúcióban megfigyelhető szelekciós folyamatok mintájára olyan számítógépes modelleket lehetne létrehozni, amelyek képesek mérnöki (elsősorban optimalizálási) feladatok megoldására. 4 fő kutatási terület alakult ki (evolúciós módszerek):

—

—

1. 2. 3. 4.

1960 Rechenberg: evolúciós stratégiák, 1966 Fogel, Owens, Walsh: evolúciós programozás, 1975 Holland: genetikus algoritmusok, 1992 Koza: genetikus programozás.


Az öröklődési folyamat


Optimalizálási feladatok — — — — — — — —

mérési eredmény kiértékelése, adott erőforrások mellett az eredmény maximalizálása, adott gazdasági cél mellett a ráfordítás minimalizálása, a napi beosztásunk megtervezése, két város között az optimális út megkeresése, órarend tervezés, menü tervezés stb.


A algoritmus általános szerkezete 1. 2. 3. 4. 5. 6.

Hozzuk létre a P0 kezdeti populációt t := 0 while not Kilépés(Pt) Pt’ := ÚjElemek(Pt) Pt+1 := ÚjPopuláció(Pt’, Pt) t := t + 1


A genetikus algoritmus működési sémája Probléma felépítés Lényeges tulajdonságok, kódolás meghatározása

Jósági függvény meghatározása

Generációméret meghatározása

Kilépési feltétel meghatározása

Genetikus műveletek specifikálása, valószínűségek meghatározása

Kezdeti populáció Genetikus műveletek: rekombináció (keresztezés), mutáció végrehajtása

Jósági mértékek meghatározása, reprodukció

Új generáció Szülők kiválasztása

Jósági mértékek meghatározása, kilépési feltétel vizsgálata

Eredmény kiválasztása és dekódolása


A genetikus algoritmusok alkalmazási területei: Koncerttermek tervezése — Szuperszonikus gépek szárnytervezése — Fantomkép-készítés — Órarend-készítés — Kommunikációs hálózatok — Játékok — Robotok vezérlőprogramjai — Stb. —


A gráfszínezési probléma A probléma: egy adott irányítatlan gráfhoz találnunk kell egy jó k-színezést, ami azt jeleneti, hogy minden csúcshoz az előre adott k különböző szín valamelyikét kell rendelni, úgy, hogy minden él két különböző színű pontot kössön össze. — Döntési problémák: térképszínezés, térinformatikai problémák, repülők járatokhoz rendelése stb. — A genetikus algoritmus populációk sorozatát állítja elő, a populációk megoldásokat tartalmaznak. Itt egy megoldás a gráf egy színezése.

—


A színezés direkt kódolása — —

—

A megoldásokat kódolni kell, hogy újabb megoldásokat lehessen szerkeszteni. Minden megoldáshoz így hozzárendelünk egy szintaktikailag jól manipulálható betűsorozatot egy kódoló függvény segítségével. A gráf pontjaihoz rendelt színeket felsoroljuk, ez a számsorozat lesz a kód. 1

4 5

11213 2 3


Fitnesz függvény (rátermettség mérése) Az azonos színű csúcsokat összekötő élek száma legyen k. — A csomópontok száma legyen n. — A fitnesz függvény megadható: f(n)= - k —

—

Az optimális érték: f(n)=0


Szülők választása —

Pár-verseny szelekció: Válasszunk ki a populációból két megoldást teljesen véletlenszerűen és a szelekció által kiválasztott elem legyen a kettő közül a rátermettebb. (További általánosítás.)

—

Rátermettség-arányos szelekció: Valószínűségi mintavételt használunk: egy megoldás kiválasztásának a valószínűsége annál nagyobb, minél nagyobb a rátermettsége a populáció rátermettségi átlagához képest. A populáció minden e elemére a kiválasztódás valószínűségét megadhatjuk a

f (e) P (e) = n ∗ f ( pop) képlettel, ahol f(e) a rátermettség értéke, n a populáció elemszáma és f(pop) a populáció tagjainak átlagos rátermettsége.


Rekombináció (keresztezés) —

— —

Több kiindulási megoldásból (szülőből) állítanak elő újabb megoldást a szülők kódjainak valamilyen kombinációja segítségével. Pl. egypontos keresztezés Véletlenszerűen választunk egy keresztezési pontot és a keletkezett fél kódokból új megoldást rakunk össze. 223332112 223322113 113222113


Mutáció — —

Véletlenszerűen kiválasztott pozíciókat változtatunk meg. A pozíciók kiválasztására sokféle módszer alkalmazható, pl. minden pozíció egy rögzített valószínűséggel mutálódhat. Legtöbbször úgy állítjuk be ezt a valószínűséget, hogy átlagosan egy pozíció változzon meg egy kódban.

223332112


221332112

Intelligens technikák k a

Recommend Documents