Evoluční algoritmy Flashcards
(6 cards)
Evoluční algoritmy
Evoluční algoritmy jsou optimalizační a vyhledávací metody inspirované principy biologické evoluce. Jsou užitečné pro řešení složitých problémů, kde není znám efektivní analytický nebo deterministický algoritmus. Patří mezi tzv. heuristické a metaheuristické metody.
Hlavním principem evolučních algoritmů je simulace přirozeného výběru a evolučních procesů, jako jsou mutace, křížení a selekce, na množině kandidátních řešení (tzv. populace). Cílem je nalézt optimální nebo dostatečně dobré řešení daného problému.
Evoluční algoritmy zastřešují řadu přístupů využívajících modely biologické evoluce. Tyto modely jsou: přirozený výběr (výběr silnějšího jedince, podle fitness funkce), náhodný genetický drift (mutace, decimuje jedince s vysokou fitness) a reprodukční proces (křížení jedinců). Spadají zde přístupy jako genetické algoritmy, genetické programovaní, evoluční strategie, evoluční programovaní.
Obecný evoluční algoritmus začíná se základní populací. Z této populace se vytvoří výběr jedinců, kteří se zříží. Tito jedinci následně zmutují a vytvoří novou populaci. Tyto kroky se opakují v 𝑁 iteracích. Ukončení je stanoveno předem: počtem iterací, dosažení požadovaného jedince, minimální změnou fitness populace po několik iterací.
Evoluční algoritmy - Komponenty
Populace – množina možných řešení problému, která se vyvíjí v čase.
Chromozom (individuum) – jedno konkrétní řešení kódované ve vhodné reprezentaci.
Fitness funkce – ohodnocení kvality jednotlivých řešení.
Selektivní operátory – mechanizmy výběru, křížení a mutace, které vedou k evoluci populace.
Genetické algoritmy
Genetické algoritmy jsou založeny na Darwinově myšlence „přežije nejsilnější“. Využívá metody křížení, mutace a selekce. Kódování řetězci má také svou analogii v gentice, kde řetězce odpovídají chromozomům, jednotlivé pozice v řetězci jednotlivým genům a konkrétní hodnoty na těchto pozicích pak alelám.
1) Inicializace populace - Populace se obvykle inicializuje náhodně nebo pomocí nějaké heuristiky. Každý jedinec v populaci reprezentuje možné řešení problému (tzv. chromozom).
2) Hodnocení kvality řešení (fitness funkce) - Každý jedinec je ohodnocen pomocí fitness funkce, která určuje, jak je dané řešení dobré.
3) Výběr rodičů (selekce) - Probíhá výběr jedinců, kteří se budou dále reprodukovat.
Turnajová selekce – náhodně se vybere několik jedinců a ten nejlepší z nich postupuje.
Ruletová selekce – jedinci s vyšší fitness mají vyšší
pravděpodobnost výběru.
4) Křížení - Kombinace genetické informace dvou rodičovských jedinců za účelem vytvoření nového potomka.
5) Mutace - Náhodná změna některých genů v chromozomu, aby se zachovala genetická diverzita a předešlo se ustrnutí v lokálním optimu. Typicky se provádí s nízkou pravděpodobností.
6) Nahrazení staré populace - Nejlepší jedinci nebo nově vytvoření potomci nahrazují starou populaci.
7) Zastavovací podmínka - Algoritmus se zastaví, když je dosaženo určité kvality řešení nebo po určitém počtu generací.
Genetické programování
Genetické programování je rozšířením genetických algoritmů, které nepracuje pouze s pevně strukturovanými chromozomy, ale s celými programy (obvykle ve formě stromových struktur). Místo optimalizace numerických hodnot se zde optimalizuje samotná programová struktura.
Oproti GA se liší v reprezentaci jedinců. V GP jsou jedinci
vytvořeni stromem s proměnlivou délkou chromozomu. Zjednodušeně je to převedení GA do programovacích jazyků.
Evoluční algoritmy - Pojmy - Populace, mutace, křížení, chromozom, selekce (ruletový, turnajový výběr)
Populace – množina jedinců (řešení) pevné velikosti, ze které jsou vybíráni pro evoluční operace (křížení, mutace).
Jedinec – konkrétní řešení, reprezentované jedním chromozomem.
Chromozom – řetězec složený z genů, kódovaný např. binárně, reálnými čísly, znaky nebo objekty.
Gen – pozice na chromozomu reprezentující určitou charakteristiku.
Alela – konkrétní hodnota genu (např. 0 nebo 1).
Fitness funkce – měří kvalitu řešení, např. přesnost, výpočetní náročnost, počet chyb. Existují různé typy: hrubá, standardizovaná, přizpůsobená, normalizovaná.
Turnajová selekce – náhodně se vybere malý počet jedinců a nejlepší z nich postupuje dál.
Ruletový výběr (varianta 1) – pravděpodobnost výběru jedince odpovídá jeho fitness (čím lepší, tím větší šance). Nevýhodou je dominance jednoho silného jedince.
Metody křížení - elitářství, n-bodové křížení, uniformní křížení, mutace
Elitářství (elitism)
Nejedná se o křížení v užším smyslu, ale o strategii uchování nejlepších jedinců beze změny do další generace. Zaručuje, že nejlepší řešení nebude ztraceno.
n-bodové křížení
Chromozomy rodičů se rozdělí na více částí pomocí n náhodných bodů. Dílčí segmenty se střídavě skládají do potomka.
1-bodové křížení – nejčastější: rozdělení na dvě části (např. první část od rodiče A, druhá od B).
2-bodové a víc – více střídání, větší variabilita.
Uniformní křížení
Každý gen potomka je náhodně vybrán z jednoho z rodičů (s pravděpodobností, např. 0.5). Nepoužívá se dělení chromozomu na segmenty, ale rozhoduje se gen po genu. Zvyšuje míru kombinace genetického materiálu.
Mutace
Náhodná změna jednoho nebo více genů v chromozomu s malou pravděpodobností. Slouží k zachování diverzity a k prohledávání nových oblastí prostoru řešení.
