Genetické algoritmy; Laboratórium 3
Laboratórium 3
obsah
Genetické algoritmy
Metóda je inšpirovaná Darwinovou evolučnou teóriou. Spolupracujte s a populácia kandidáta na riešenie, ktorý sa vyvíja a prispôsobuje prostrediu (v tomto prípade je prostredie funkciou, ktorá sa má optimalizovať). Genotyp sa mení:
- nasledujúca mutácia (modifikácia génu v kódovaní jednotlivca)
- po rekombinácii genetického kódu dvoch jedincov)
Podľa evolučného princípu prežitie najschopnejších, z jednej generácie na druhú bude uprednostňované prežitie najlepších (dobre adaptovaných) jednotlivcov.
Terminológia
- jednotlivec (chromozóm) = kandidátske riešenie, kódované ako v laboratóriu 2
- chromozómy sa skladajú z gény (znaky)
- každý gén je v chromozóme v jednej polohe (lokus/lokus)
- nazývajú sa rôzne hodnoty, ktoré môže mať gén alela
pseudo
komponenty
Jednotlivci sú do novej populácie vyberaní s pravdepodobnosťou úmernou ich fyzickej zdatnosti.
Niektorí jedinci môžu mať v novej populácii viac detí, iní môžu mať 0. prehliadka
Jednotlivci „bojujú“ v skupinách po náhodne vybraných. Vyberie sa najlepších n v každej skupine.
Na základe hierarchie
Je to podobné ako pri výbere šťastného kolesa s tým rozdielom, že pravdepodobnosť výberu nie je úmerná zdatnosti, ale závisí od postavenia jednotlivca v zoradenom zozname jedincov v populácii. Znižuje sa tak pravdepodobnosť „zadusenia“ slabých jedincov osobami s veľmi vysokou fyzickou zdatnosťou.
Zmena jednotlivcov Deje sa to prostredníctvom genetických operátorov, kríženia a mutácie.
-
kríž
- Križovanie s bodom rezu, vybrané náhodne. Príklad:
- Križovanie s n náhodne generovanými bodmi rezu. Príklad (n = 3):
- Jednotné kríženie: pre každý lokus je pravdepodobnostne vybraný gén jedného z rodičov.
- mutácia
Mení jeden alebo viac ľubovoľne vybraných génov na chromozóme. Pravdepodobnosť mutácie je daná parametrom popoludnie. Počet mutovaných génov sa odhaduje na pm * dĺžka chromozómu * veľkosť popu. Uplatnenie mutácie:
Ak sa reprezentácia používa ako reťazec bitov, mutácia spočíva v zmene hodnoty príslušného bitu z 0 na 1 alebo naopak.
„Štandardné“ parametre pop_size = 50 jedincov pravdepodobnosť mutácie pm = 0,01 pravdepodobnosť kríženia pc = 0,25 Kritériá zastavenia dosiahnutie počtu iterácií TMAX žiadne vylepšenie riešenia v posledných iteráciách TW (alebo TW (t)) .
Implementujte genetický algoritmus na vyhľadanie koncových bodov funkcií navrhovaných v laboratóriu 1.
Graf, ako sa vyvíjajú riešenia. Graf musí vyjadrovať maximálnu, minimálnu a priemernú zdatnosť každej generácie.
Vytvorte krátku správu (textový formát) s uvedením:
- minimálny, priemerný a maximálny čas vykonania
- najlepšie a najhoršie riešenie, ako aj priemer riešení získaných po niekoľkých pokusoch.
Kombinuje vlastnosti dvoch rodičovských chromozómov, čo vedie k potomkom, ktoré tieto vlastnosti čiastočne dedia. Ovplyvňuje chromozómy s pravdepodobnosťou PC. Počet jedincov zúčastňujúcich sa na krížení za celú generáciu sa odhaduje pomocou pc * pop_size.
Výber jedincov, ktorí utrpia kríženie: