Genetické algoritmy
Genetické algoritmy
Evoluční optimalizační metoda inspirovaná biologickou dědičností a přirozeným výběrem (Mendel, Darwin). Místo přímého hledání řešení pracuje s populací kandidátních řešení, která se postupně zlepšuje.
Základní pojmy
- Chromozom — kódované řešení (často binární řetězec, např. 1100)
- Gen — jednotlivý bit chromozomu
- Fitness funkce — účelová funkce hodnotící kvalitu řešení
- Populace — soubor chromozomů v jedné generaci
Cyklus algoritmu
- Inicializace — vytvoření počáteční (náhodné) populace
- Hodnocení — ohodnocení každého chromozomu fitness funkcí
- Selekce — výběr lepších jedinců (lepší = větší šance přežít, ale i horší mohou zůstat pro diverzitu)
- Křížení — kombinace dvou rodičů → potomci s vlastnostmi obou (pravděpodobnost ~0,9)
- Mutace — náhodná změna bitu (0↔1), vzácná (~0,1), zabraňuje zamrznutí populace
- Ukončení? — pokud ne, zpět na krok 2 (nová generace)
Parametry
- Velikost populace (~1000)
- Pravděpodobnost křížení (~0,9)
- Pravděpodobnost mutace (~0,1 nebo méně)
- Kritéria ukončení: max generací, max čas, populace se nemění
Binární kódování
Chromozom jako binární řetězec → převod na reálnou hodnotu: H_D = a₃·2³ + a₂·2² + a₁·2¹ + a₀·2⁰
Mapování na interval x_min, x_max umožňuje optimalizovat reálné parametry.
Dva typy úloh
- Přímá optimalizace — min nákladů, max zisku, min času, min odpadu
- Parametrická optimalizace modelu — nejlepší parametry funkce, nejlepší nastavení predikčního systému
Aplikace
| Oblast | Příklad |
|---|---|
| Ekonomika | Minimalizace nákladů, maximalizace zisku |
| Výroba | Minimalizace výrobního času, rozvrhování strojů |
| Logistika | Obchodní cestující (TSP), nejkratší trasa |
| Materiál | Cutting plan — řezání s minimálním odpadem |
| Investice | Knapsack — výběr projektů při omezeném rozpočtu |
| Data | Aproximace měřených dat, klastrování, segmentace |
| Finance | [[predikce |
Výhody a nevýhody
Výhody: nepotřebují derivace, pracují s diskrétními i spojitými problémy, zvládají mnoho lokálních extrémů, univerzálně použitelné.
Nevýhody: negarantují globální optimum, výpočetně náročné, výsledek závisí na nastavení parametrů.
Propojení s dalšími tématy
- Neuronové sítě — GA mohou optimalizovat architekturu sítě
- Predikce — optimalizace predikčních modelů
- Fuzzy logika — GA mohou ladit parametry fuzzy systému
Kontrolní otázky ke zkoušce
- Popište metodu a vysvětlete princip genetických algoritmů.
- Popište realizaci a výpočet genetických algoritmů na počítači.
- Jak lze využít genetických algoritmů v praxi?
- Jaké jsou prvky reprodukce?
- Co znamená proces selekce?
- Co znamená proces mutace?
- Jaká se volí velikost populace?
Pojmy k zapamatování
Genetické algoritmy, optimalizace, reprodukce, selekce, křížení, mutace, účelová funkce, omezující podmínky, parametry výpočtu.
Zdroje v kurzu IpmrK
- Genetické algoritmy — teorie
- Genetické algoritmy — využití
- Kniha — shrnutí kapitoly, kontrolní otázky, pojmy