Genetické algoritmy — teorie

Zdroj: raw/ipmrk/ga-teorie.md | Kurz: IpmrK

Shrnutí

Přednáška zavádí genetické algoritmy jako evoluční optimalizační metodu. Pokrývá biologickou inspiraci, kódování řešení jako chromozomů, cyklus selekce–křížení–mutace a praktický postup návrhu.

Hlavní body

Biologická inspirace — Mendel (dědičnost), Darwin (přirozený výběr), Goldberg. Principy: populace, selekce, křížení, mutace.
Kódování — řešení = chromozom (často binární řetězec). Gen = jednotlivý bit. Převod: H_D = a₃·2³ + a₂·2² + a₁·2¹ + a₀·2⁰.
Cyklus GA: inicializace → selekce → křížení → mutace → hodnocení → ukončení? → nová generace.
Selekce — lepší jedinci mají větší šanci na výběr (simulace přirozeného výběru), ale i horší mohou přežít pro zachování diverzity.
Křížení — dva rodiče si vymění části chromozomů → noví potomci s kombinovanými vlastnostmi. Hlavní mechanismus tvorby nových řešení.
Mutace — náhodná změna bitu (0↔1). Vzácná, ale důležitá — zabraňuje zamrznutí populace, umožňuje prohledat nové oblasti prostoru.
Fitness funkce — účelová funkce hodnotící kvalitu řešení (min náklady, max zisk, min odpad...). Bez ní by GA nevěděl, koho selektovat.
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 iterací (~10 000), max čas (~50 min), populace se nemění.
Příklady využití — obchodní cestující (TSP), řezání materiálu, prostorové uložení (knapsack), výroba, klastrování, predikce.

Zkouškové shrnutí

Genetický algoritmus je evoluční optimalizační metoda, která pomocí populace chromozomů, selekce, křížení a mutace postupně hledá co nejlepší řešení podle zadané fitness funkce.

Souvislosti

Genetické algoritmy — hlavní téma
Genetické algoritmy — využití — navazující přednáška o aplikacích
Optimalizace — obecnější kontext