Genetikai algoritmusok; 3. laboratórium
3. laboratórium
tartalom
Genetikai algoritmusok
A módszert Darwin evolúciós elmélete ihlette. Dolgozzon a megoldásjelölt populáció, amely fejlődik és alkalmazkodik egy környezethez (ebben az esetben a környezet az optimalizálandó funkció). A genotípus megváltozik:
- mutációt követően (egy gén módosítása az egyén kódolásában)
- két személy genetikai kódjának rekombinációját követően)
Az evolúciós elv szerint a legjobbak túlélése, egyik generációról a másikra a legjobb (jól alkalmazkodó) egyének túlélését részesítik előnyben.
Terminológia
- egyén (kromoszóma) = jelölt oldat, kódolva, mint a 2. laboratóriumban
- kromoszómák állnak gének (tulajdonságok)
- minden gén a kromoszómában egy helyen van (locus/locus)
- a gén különböző értékeit nevezzük allél
ál
alkatrészek
Az egyének kiválasztása az új populációban az erőnlét arányos valószínűséggel történik.
Egyes egyéneknek több gyermekük lehet az új populációban, másoknak 0 lehet. túra
Az egyének véletlenszerűen kiválasztott m csoportokban "harcolnak". Minden csoportból kiválasztják a legjobb n-t.
A hierarchia alapján
Hasonló a szerencsés keréktípus kiválasztásához, azzal a különbséggel, hogy a kiválasztás valószínűsége nem arányos az erőnléttel, hanem attól függ, hogy az egyén milyen helyzetben van a populáció rendezett egyedlistájában. Ez csökkenti annak esélyét, hogy a gyenge egyéneket "elfojtsák" azok, akik nagyon magas erőnlétűek.
Az egyének megváltoztatása Genetikai operátorok, keresztezés és mutáció révén történik.
-
átkelés
- Vágási ponttal való keresztezés véletlenszerűen. Példa:
- N véletlenszerűen generált vágási ponttal való keresztezés. Példa (n = 3):
- Egységes keresztezés: minden lokuszhoz egy szülő génjét választják ki valószínűség szerint.
- mutáció
Megváltoztat egy vagy több önkényesen kiválasztott gént a kromoszómán. A mutáció valószínűségét a paraméter adja meg délután. A mutált gének számát pm * chromosoma_length * pop_size értékkel becsüljük meg. A mutáció alkalmazása:
Ha az ábrázolást bitek karaktersorozataként használják, akkor a mutáció abból áll, hogy a megfelelő bit értékét 0-ról 1-re változtatják, vagy fordítva.
"Normál" paraméterek pop_size = 50 egyén mutáció valószínűsége pm = 0,01 kereszteződés valószínűsége pc = 0,25 Megállási kritériumok TMAX számú iteráció elérése nem javítja a megoldást az utolsó TW (vagy TW (t)) iterációkban .
Végezzen el egy genetikai algoritmust az 1. laboratóriumban javasolt funkciók végpontjainak megtalálásához.
Ábrázolja, hogyan fejlődnek a megoldások. A diagramnak ki kell fejeznie az egyes generációk maximális, minimális és átlagos alkalmasságát.
Készítsen rövid jelentést (szöveges formátum), amely a következőket tartalmazza:
- minimális, átlagos és maximális végrehajtási idő
- a legjobb és a legrosszabb megoldás, valamint a számos futtatás után kapott oldatok átlaga.
Két szülő kromoszóma tulajdonságait ötvözi, így olyan utódok születnek, amelyek részben öröklik ezeket a tulajdonságokat. Valószínűséggel befolyásolja a kromoszómákat PC. Egy generáció keresztezésében részt vevő egyedek számát pc * pop_size segítségével becsüljük meg.
A keresztezésben szenvedő személyek kiválasztása: