Genetikus algoritmus

Mesterséges intelligencia alapok

2025����Dr. Dudás László diái alapján

Evolúciós algoritmusok

• Az evolúciós algoritmusok a biológiai evolúciót modellezik. Az ember számtalan probléma megoldásához merítette az alapötletet a természetből. Pl. madarak szárnya → repülőgépszárny, bambuszrúd → rúdugrók üvegszálas rúdja, halak léghólyagja → tengeralattjárók merülési berendezése, emberi szemlencse → fényképezőgép optikája, stb.

​

• Amit az ember gondolkodással próbál megoldani, azt a természet gyakran hatékonyabban oldotta meg a változatosság és a szelekció eszközével. A többnyire kétszülős biológiai szaporodás és a többnyire külső hatásoknak köszönhető véletlenszerű megváltozás, a mutáció az egyedek sokszínű-ségét eredményezi, míg a túlélésért folyó verseny a jobb, életképesebb egyedek kiválogatódását, tulajdonságaik továbbörökítésének lehetőségét hordozza magában. E két működés a populáció környezeti elvárásoknak való jobb megfelelését, állandó alkalmazkodását jelenti.

​

​

​

Evolúciós algoritmusok és az optimumkeresés�

• Az evolúciós algoritmusokkal végzett problémamegoldást biológiai számításnak is nevezik.
• Az evolúciós algoritmusok populációjának egyedei megfeleltethetők a keresés állapotterében található állapotok egy részhalmazának, az egyedek életképességét, jóságát mérő ún. fittness függvény megfeleltethető a keresés kritériumfüggvényének.
• Az evolúciós mechanizmus mintájára létrehozott programokkal akkor is megoldhatók a feladatok, ha a problémamegoldásra nem tudunk részletes algoritmust adni. Az irányított „próba-szerencse” módszer feladatérzéket-lenségéért, robusztusságáért számítási idővel kell fizetnünk. Ebben is a biológiai modellre hasonlít: az evolúció nem gyorsan zajló folyamat.
• A biológiai evolúció és az evolúciós algoritmusok eltérése�A biológiai evolúció célja a környezet elvárásaihoz való minél hatékonyabb alkalmazkodás, míg az evolúciós algoritmusokkal globális optimumok keresését végezzük. Ezen optimumkeresési feladatok általában nem biológiai beágyazó környezetben zajlanak.

Evolúciós algoritmusok osztályozása�

• Evolúciós stratégiák: a kezdet, (Rechenberg, 1973, repülőgépszárny optimalizálás.)
• Evolúciós programozás: programkód kifejlesztése a kódrészletek mutálódása és szelektálása által. Véges automaták automatikus kifejlesztésére (Fogel, Owens, Walsh, 1966.).
• Genetikus algoritmus, GA: keresztezés, mutáció és szelekció matematikai modellezése (Holland, 1975).
• Osztályozó rendszerek
• Genetikus programozás, GP: programok kitenyésztése adott feladatra. (Koza, 1992).

​

​

Az Evolúciós algoritmusok általános lépései

1. Legyen P₀ a kezdeti populáció, �k=0 a ciklusváltozó kezdőértéke.
2. Ha a megállási kritérium teljesül, add vissza a P_k populációt.
3. Egyébként bővítsd a P_k populációt új egyedekkel.
4. Szelekcióval állítsd elő a P_k populációból az új P_k+1 populációt.
5. Inkrementáld a k ciklusváltozót és ismételd a 2. ponttól.

​

​

A 3. lépésben a bővítés alkalmazhat szülőválasztást, �keresztezést és mutációt.

​

A 4. lépés feladata a populáció létszámának eredeti értéken tartása a vesztes egyedek törlésével.

​

Amennyiben a populáció egyelemű, csak mutáció van, az algoritmus helybeni, és neve sztochasztikus hegymászó.

Genetikus algoritmus�

• A genetikus algoritmus egy globális kvázioptimum megtalálására kifejlesztett kereső algoritmus, mely alapvetően problémafüggetlen. A lokális informáltságú, de globális célra törő algoritmusok, a többszörös indítású hegymászó, a szimulált hűtés és a tabu keresés rokona.
• A problémára vonatkozóan rendelkezésre álló információ bevihető az algoritmusba a valós egyedeknek megfelelő fenotípusról a számításban alkalmazott modelljére,� a genotípusra való áttéréskor, valamint � a keresztezés és a mutáció módjának megválasztásakor. �Az ily módon kialakított, problémára szabott genetikus algoritmusok hatékonysága megnő.
• A globális optimum megtalálásában az egzakt analitikus módszerekhez (differenciálás, gradiens módszer, szimplex módszer) viszonyítva lassú, pontatlan, de diszkrét állapottereken is működik, igénytelen a feladattal szemben.�A hasonlóan robusztus és igénytelen kimerítő kereséstől hatékonyabb.

• A genetikus algoritmus nevét az élőlények utódaiban megjelenő kombinálódott szülői génekről, mint az utód tulajdonságainak hordozójáról kapta. A genetikus algoritmus alkalmazásának kulcskérdése a fenotípusról genotípusra való leképezés, azaz az egyed egyes tulajdonságait reprezentáló „gének”, azaz kromoszómarészletek kialakítása.
• Mivel egyszerre egy populációt, azaz egyedek egy csoportját kezeli, a globális optimum fellelésének megnő az esélye. Az állapottér feltárásában a következők játszanak szerepet:
• A kezdeti populáció egyedeinek eloszlása az állapottéren
• A keresztezések interpoláló hatása
• A mutációk extrapoláló, a keresztezéssel kialakult belterjességből, lokalizáltságból kivezető hatása.
• A kezdeti mutációk az állapottér hatékony feltárását eredményezik. A globális optimum köré gyűlt késői populációkból viszont már csak gyorsan elhaló mutációk származnak, mivel azok életképessége a populáció többi tagjához képest alacsony.

• A populáció fejlődése az egyedek fejlődésén keresztül realizálódik. A szelekciónak köszönhető látszólag spontán fejlődés nem csak a véletlen eredménye: a jobb célfüggvény (fitness) értéket reprezentáló egyedek aránya a populációban egyre nő, míg a kevésbé életképeseké csökken. Az egyedek a módszer memóriájaként is felfoghatók: a jó tulajdonságú egyedek megtartásával az algoritmus megtanulja a jó célfüggvényértéket adó tulajdonságokat, a gyengébbeket eredményező tulajdonságok pedig elfelejtődnek az azokat hordozó egyedek kihalásával.

​

​

x1

k= 0

k= 5000

x1

• Leképezés fenotípusról genotípusra��Feladata minden egyes állapothoz egy karaktersorozat, azaz bitminta hozzárendelése.

​

A leképezés kihat az alkalmazható operátorokra, végeredményben a GA hatékonyságára.

• A problémától függően a megoldásokat különböző módon lehet reprezentálni:
• Bináris kódolás: Leggyakrabban használt módszer, ahol az egyedek bit-sorozatokkal vannak ábrázolva.
• Valós számokkal történő kódolás: Hasznos a numerikus optimalizációs problémák esetén.
• Permutációs kódolás: Alkalmazott például útvonal-optimalizációs problémákban, mint a Traveling Salesman Problem (TSP).
• Példák egyszerű esetekre:
• Fenotípus: 12 zöld, vagy piros téglalapból álló sorozat.�Genotípus: 12 bites bináris szám, piros:1, zöld: 0.�Optimum: minden téglalap piros.�
• Fenotípus: m*n méretű fekete-fehér bittérkép alakjában adott kép.�Genotípus: m*n elemű bináris szám, fekete: 0, fehér: 1.�Optimum: két fekete átló a bittérképen.�
• Megjegyzés: Az egyetlen tulajdonság különböző értékeinek tárolására alkalmazott több bites, egységként, génként kezelt kromoszómarészlet által felvehető értékeket allél-eknek nevezzük.

​

A szelekciós operátor�

​

Feladata a szülőegyedek kiválasztása a keresztezés számára. A különféle szelekciós módszerekben közös, hogy a rátermettebb egyedeket jelentősebb arányban választják ki tulajdonságaik továbbörökítésére, de általában a gyengébb egyedek is kapnak egy kis esélyt.

• A szelekcióban alkalmazott technikák

​

• Rátermettség-arányos választás
• Párok versenyeztetése
• Rangsorolás

​

1.

Keresztezés operátor

Szerepe utódok, azaz új egyedek előállítása.

​

• Leggyakoribb módszerek

​

• Egypontos keresztezés

​

​

​

​

​

​

​

Véletlenszerű keresztezési pont választás.�

1

3

2

3

1

3

2

3

1

3

2

3

1

3

2

3

1

1

3

2

3

1

3

2

1

3

2

3

3

3

2

3

​

• Kétpontos keresztezés
• Két véletlenszerű keresztezési pont
• Megegyezik két különböző keresztezési pontú egypontos keresztezéssel, így a többpontos keresztezés is visszavezethető egypontos keresztezésre

​

​

​

​

​

​

• Egyenletes keresztezés

Ötven százalék eséllyel cserélődik minden egyes gén.

​

1

3

2

3

1

3

2

3

1

3

2

3

1

3

2

3

1

3

2

2

3

3

2

3

1

3

3

1

3

1

3

2

1

3

2

3

1

3

2

3

1

3

2

3

1

3

2

3

1

3

1

2

2

3

3

2

2

1

3

3

3

3

1

2

• Útvonal-újrakapcsolás (Path Relinking)
• Két jó megoldás között köztes megoldások létrehozása (Lépésenkénti mutáció)
• P1 = (1,0,0,0), P2 = (0,1,1,1)
• Akkor a gyerekek C1 = (0,0,0,0), C2 = (0,1,0,0), C3 = (0,1,1,0)
• Távolság csökkentése a lényeg a változásnak
• Megjegyzések:
• Nincsen általános módszer a keresztezés megválasztására, annak a feladathoz kell igazodnia.
• Speciális keresztező operátort igényelhet az olyan eset, amikor összefüggés van a gének között (intelligens keresztezés).
• A GA algoritmus érzékeny az operátorválasztásra.

​

Mutáció operátor

�Olyan új egyedet hoz létre, mely mentes a keresztezés belterjességétől, azaz az ősökétől merőben elütő tulajdonságokat hordozhat. A keresztezéstől kisebb gyakorisággal alkalmazott művelet.

​

​

​

​

​

​

• A módszer: az adott egyed kromoszómájának egy véletlenszerűen választott génjét egy másik génre cseréljük ki.

​

1

3

2

3

1

3

2

3

1

1

3

2

3

1

2

3

1

�A Genetikus algoritmus lépései�

• Add meg az algoritmus fő paramétereit
• Add meg a kezdeti populációt
• Ha a megállási kritérium teljesül, add vissza az aktuális populációt
• Egyébként válaszd ki az egyedeket a keresztezéshez
• Hajtsd végre a keresztezéseket
• Válaszd ki az egyedeket a mutációhoz
• Végezd el a mutációkat
• Állítsd elő az új populációt az eredeti és a keresztezéssel és mutációval kapott egyedekből álló halmazból.
• Ismételd a 3. ponttól.

​

​

• A Genetikus algoritmus paraméterei

​

• A populáció számossága (pl. 16) (ha fix)
• Kromoszóma hossz (pl.12 bit)
• A szelekciós operátor
• A keresztezés operátor: a keresztezési ráta �(új egyedek aránya, pl. 0.7), a keresztezési pontok száma, stb.
• A mutáció operátor: a mutációs ráta (pl. 0.001), a mutációs pontok száma, stb.

​

• Leállási feltételek lehetnek:
• Olyan megoldást talál, amely megfelel a minimális kritériumoknak
• Adott generációszámot elértük
• Elért költségvetés (számítási idő/pénz)
• A legrátermettebb megoldás jósága eléri vagy elérte azt a platót, hogy a követő iterációk már nem hoznak jobb eredményeket (Nem javul jelentős mértékben)
• A fentiek kombinációi

Új populáció létrehozása- Túlélési valószínűség

Távolság (d)

• Hamming távolság
• Eltérő bitek száma
• pl. 1101 és 1000 között 2
• [1,3] és [2,5] között 2
• Euklideszi távolság
• Összegzett kromoszómakénti különbségek négyzetének gyöke
• Manhattan távolság
• Kromoszómakénti különbségek abszolút értékének összege
• Könnyebb számolni
• Bináris reprezentációnál ugyanaz, mint a Hamming
• Pl. [1,3] és [2,5] esetén 3

​

​

​

A genetikus algoritmus alkalmazhatósága

Bár a genetikus algoritmusok nagyon igénytelenek az állapottérrel, az állapottéren értelmezett kiértékelő függvénnyel szemben, van néhány követelmény, amelynek eleget kell tenniük a megoldandó feladatoknak:

• A feladat megoldási lépéseinek ismerete nem szükséges, de bizonyosnak kell lennünk a megoldhatóságában.
• A megoldások összetevői között lehet részleges függőség, de nem lehet az összes összetevő függőségi viszonyban.