16. tétel - Genetikus algoritmus II.
Mutassa be az evolúciós módszerek jellegzetességeit és alapvető lépéseit! Részletesen ismertesse a különféle szelekciós lehetőségeket (elitizmus, csonkolás, rendezett kiválasztás, fitnesz arányos kiválasztás, versengő kiválasztás)! Miként lehet megvalósítani a keresztezést és mutációt?
Evolúciós módszerek jellegzetességei és alapvető lépései
Szelekciós lehetőségek
A szelekció történhet:
- visszahelyezéssel: az egyes elemek többször is részt vehetnek a kiválasztási folyamatban
- visszahelyezés nélkül: egy egyed csak egyszer választható
1. Elitizmus
A populáció legjobb elemei automatikusan átkerülnek a következő populációba.
- a fitnesz értéke így biztosan monoton csökken
- de nagyobb az esélye, hogy beragad egy lokális optimumba.
2. Csonkolás
A legegyszerűbb, determinisztikus módszer.
- Fitnesz szerint sorbarendezzük az elemeket
- Kiválasztjuk a legjobbakat
- A többit eldobjuk
3. Rendezett kiválasztás
Hasonló a csonkoláshoz, de nem determinisztikus. A fitnesz szerint rendezett listában előbb lévő elemek nagyobb valószínűséggel kerülnek kiválasztásra.
Van egy \(k\) paramétere. Ha ez kicsi, jó eséllyel be fognak kerülni a rosszabb elemek is, ha nagy, akkor csak a legjobbak szaporodhatnak.
Egy ciklussal generál \(M_{size}\) darab véletlen számot az alábbi képletekkel:
\[\gamma = \frac{1}{1-\frac{\log{k}}{\log{|M_{size}|}}}\]
\[i = RND_u(0,1)^{\gamma}\cdot|P|\]
Az így kapott \(i\)-t indexként értelmezzük, a populáció \(i.\) eleme bekerül a készülő \(M\) halmazba. Azáltal, hogy \(M_{size}\) darabot generál, telepakolja az \(M\) halmazt.
4. Fitnesz arányos kiválasztás (Rulettkerék módszer)
Az alapelve, hogy a jobb fitnesszel bíró elemek nagyobb eséllyel szaporodjanak.
\(P(p)\) valószínűség adja meg, hogy a kiválasztás során milyen eséllyel választjuk a \(p\) egyedet (minél kisebb a fitnesz, annál jobb az elem, és annál nagyobb esélye van):
\[P(p) = \frac{\frac{1}{f(p)} }{ \sum\limits_{\forall q \in P } \frac{1}{f(q)} }\]
Tehát a populáció összes \(q\) elemére kiszámoljuk \(\frac{1}{f(q)}\) értéket, ezeket összeadjuk, és ehhez viszonyítjuk az adott \(p\) elemmel számolt \(\frac{1}{f(p)}\) értéket. A kapott szám 0 és 1 közötti valószínűség lesz.
Ha kicsi az eltérés a fitneszek között, érdemes lehet a min-max normalizálást használni.
5. Versengő kiválasztás
Felveszünk \(k\) darab egyedet a populációból, és versenyeztetjük őket egymással. A nyertes bekerül a szülő állományba.
\(k\) itt ugyanúgy a szelekciós nyomás, ha kicsi, akkor rosszabb elemek is bekerülhetnek, ha nagy, akkor csak a legjobbak. Ennek oka, hogy az egyedek átlagosan \(k\) darab versenyben fognak részt venni.
Előnye, hogy számszerű fitnesz értékre nincs hozzá szükség.
Továbbfejlesztése, hogy nem a nyertes kerül be biztosan, csak ő kap erre nagyobb esélyt. Például a verseny \(i.\) helyezettje \(p(1-p)^{(i-1)}\) eséllyel választódik ki.
Keresztezés
Amikor kettő vagy több szülő adatai alapján létrehozunk egy egyedet.
1. Bináris keresztezés
- Megadjuk, hogy az egyes kromoszómák hány ponton legyenek szétvágva, majd összeillesztve.
- Alapvetően binárisan kódolt kromoszómákra dolgozták ki.
Fajtái:
2. Köztes keresztezés
Ha tudjuk, hogy a gének számok, akkor számoknál értelmezett műveleteket hajthatunk rajtuk végre.
Ha \(p_1[i]\)-vel és \(p_2[i]\)-vel jelöljük az első és második szülő \(i.\) génjét, akkor a leszármazott \(i.\) génje kiszámolható:
\[ c[i] = \alpha \cdot p_1[i] + (1-\alpha) \cdot p_2[i] \]
Ahol \(\alpha\) egy véletlen szám az alábbi tartományból:
\[\alpha \in [-h, 1+h] \]
Itt \(h\) egy tetszőlegesen beállítható paraméter, megadja, hogy az új egyed mennyire léphet ki a szülei által megadott tartományból.
Mutáció
- gének értékének egyedi megváltoztatása
- ez ad lehetőséget a lokális optimumokból való kiugrásra
- biztosítja, hogy ne konvergáljon túl gyorsan
- két paramétert szoktunk megadni:
- mutációs ráta: megadja, hogy milyen eséllyel fog megváltozni egy elem
- mutáció mérete: megadja, hogy mekkora méretű mutációk történhetnek
- lehet egy korlát, vagy eloszlás paraméterei, stb.
- a mutáció érinthet:
- egy pontot: a kromoszóma egy génje változik meg
- több pontot: a kromoszóma egymástól független génjei változnak meg
- összefüggő területet: egy jól behatárolt terület génjei változnak meg
- változó hosszúságú kromoszómáknál:
- 1 vagy több elemmel bővülhet a meglévő kromoszóma
- kitörölhetünk egy gént vagy génsorozatot