Geneticke-algoritmy.md

# Genetické algoritmy Genetický algoritmus je nejpřeceňovanější metoda v celé umělé inteligenci. Zní totiž skvěle - evoluce, přežití nejsilnějšího, populace se sama vyvíjí k řešení - a proto se sahá po něm i tam, kde by [hill climbing s restarty](Lokalni-prohledavani) doběhl dřív a s lepším výsledkem. Zároveň je to metoda, která u jedné konkrétní třídy úloh nemá konkurenci: **když se řešení dá zakódovat do řetězce a když má smysl kombinovat dvě částečná řešení do třetího.** Rozvrhy, trasy, rozmístění, návrhy tvarů. Tam evoluce dělá přesně to, co slibuje. Tahle stránka je o tom, jak se to nastavuje a proč jednotlivé operátory existují. Předpokládá to [lokální prohledávání](Lokalni-prohledavani) - genetický algoritmus je v podstatě local beam search s křížením a měl bys tedy vědět, co je lokální maximum. Konkrétní kód se tu nepíše, ten patří k [nástrojům](Nastroje-pro-UI). ## Odkud se to vzalo | Rok | Kdo | Co ||---|---|---|| 1960 | I. Rechenberg | první odborná práce, *Evolution strategies* || 1975 | John Holland | první genetický algoritmus || 1992 | John Koza | aplikace GA na programy, tedy genetické programování | Motivace je přímo z Darwina a stojí na třech tvrzeních: - děti dědí vlastnosti rodičů,- lepší jedinci lépe přežívají a mají víc potomků,- **pomocí počítačů můžeme vytvořit a ohodnotit tisíce umělých individuí během zlomku vteřiny**. Ten třetí bod je celý důvod, proč to funguje. Příroda potřebuje na generaci roky. Ty ji uděláš za milisekundu, takže si můžeš dovolit evoluci, která by v přírodě trvala miliony let. ## Slovník: co odpovídá čemu | V přírodě | V genetických algoritmech ||---|---|| Jedinec | řetězec symbolů, např. `h = (1001)` || Přirozený výběr | výběr podle hodnotící funkce `f(h)` || Křížení | kombinace dvou řetězců || Mutace | náhodná záměna 0 a 1 v řetězci | **Chromozóm** je základní prvek generace, tedy jedno zakódované řešení. Reprezentovat se dá čtyřmi způsoby: - **binárně** - `111011101`,- **permutací přirozených čísel** - `(6 1 7 4 3 9 2)`,- **znakově** - řetězec písmen abecedy,- **stromově** - a tomu se pak říká genetické programování. **Populace** je množina chromozómů. Každý z nich drží **jedno řešení** dané úlohy. První populace se vygeneruje náhodně a základním parametrem je její velikost. **Volba reprezentace je nejdůležitější rozhodnutí celého návrhu** a rozhoduje o tom, jestli budou operátory dávat smysl. Binární kódování pro trasu obchodního cestujícího vyrobí po křížení řetězec, který navštíví jedno město dvakrát a jiné vůbec. Permutační kódování ten problém nemá - ale zase nesnese obyčejné křížení, viz níž. ## Čtyři operátory ### Křížení Ze dvou chromozómů (otec a matka) se spojením vytvoří jeden nebo víc nových chromozómů - potomků. Nejběžnější je náhodné vybrání místa spojení a vzájemné překřížení: ```Otec:        11101|101Matka:       11100|001 Potomek 1:   11101|001Potomek 2:   11100|101``` Další typy: - **Two-point crossover** - dva body křížení, vymění se prostředek.- **Uniform crossover** - pro každý bit se náhodně zvolí rodič.- **Greedy crossover** - hladové křížení pro [TSP](#tsp-obchodní-cestující). **Křížení je jediná věc, kterou genetický algoritmus umí navíc oproti [lokálním metodám](Lokalni-prohledavani).** Kombinuje dvě řešení, z nichž každé je dobré v něčem jiném, a doufá, že vyjde jedno dobré v obojím. Když u tvé úlohy taková kombinace nedává smysl, nemá smysl ani genetický algoritmus. ### Mutace Náhodná genetická změna právě vytvořeného potomka - typicky invertování náhodně vybraného bitu. **Mutace existuje kvůli jediné věci: aby řešení neuvázlo v lokálním optimu.** Když celá populace zkonverguje na stejnou hodnotu bitu, křížení už tu hodnotu nikdy nezmění - kříží se stejné se stejným. Bez mutace je ten bit zamčený navždy. ### Fitness funkce Udává „sílu" daného chromozómu a má **velký vliv na to, které chromozómy zůstanou v populaci**. Je to totéž, co [heuristická funkce](Informovane-prohledavani) v prohledávání, jen se jí říká jinak. Rozdíl je, že u fitness nikoho nezajímá přípustnost - nemusí být dolním odhadem ničeho, jen musí rozlišovat lepší od horšího. ### Selekce Metod výběru rodičů je několik a liší se tím, jak tvrdě favorizují nejlepší jedince. **Ruletové kolo (roulette wheel).** Pravděpodobnost výběru je úměrná fitness: ```P(hi) = f(hi) / Σj f(hj)``` Algoritmus: spočti celkovou sumu fitness `S`, vygeneruj `r` z intervalu `⟨0, S⟩`, procházej populaci a sčítej fitness, vrať chromozóm, u kterého `r` poprvé klesne pod aktuální součet. **Rank selection.** Roztřídění podle pořadí, pravděpodobnost se odvozuje od pořadí místo od hodnoty. Používá se tam, kde jeden jedinec má fitness o řád vyšší než ostatní a ruleta by vybírala pořád jeho. **Tournament selection.** Vyber náhodně dva jedince a s pravděpodobností `Pt` vezmi lepšího. Nejjednodušší na implementaci a v praxi nejpoužívanější. **Steady-State selection.** Nahrazuje se jen část populace, zbytek přechází beze změny. **Elitismus.** Nejlepší jedinci přecházejí přímo do nové generace. **Tohle používej vždycky.** Bez elitismu můžeš nejlepší nalezené řešení ztratit tím, že ho zkřížíš, a nikdy se k němu nevrátíš. ## Algoritmus 1. **Inicializace** - náhodně vytvoř populaci o `n` chromozómech.2. **Ohodnocení** - ohodnoť každý chromozóm fitness funkcí `f(x)`.3. **Vytvoř novou populaci:**   - vyber „rodiče" z populace,   - vytvoř z rodičů potomky (křížení s pravděpodobností `Pc`),   - zmutuj potomky (s pravděpodobností `Pm`),   - přidej potomky do populace.4. **Nahrazení** - starou populaci nahraď novou.5. **Ukončení** - je-li maximální fitness ≥ práh `t`, zastav. Jinak pokračuj bodem 2. ```mermaidflowchart TD    A[náhodná počáteční populace] --> B[ohodnoť fitness]    B --> C{konec?}    C -->|ano| D[vrať nejlepšího jedince]    C -->|ne| E[selekce rodičů]    E --> F["křížení s pravděpodobností Pc"]    F --> G["mutace s pravděpodobností Pm"]    G --> H[nahraď populaci]    H --> B``` Ta ukončovací podmínka „fitness ≥ práh" má jeden háček: **u optimalizačních úloh neznáš optimum, takže nevíš, jaký práh nastavit.** V praxi se proto ukončuje jinak - pevným počtem generací, nebo tím, že se nejlepší fitness `k` generací po sobě nezlepšila. ## Pravděpodobnost křížení a mutace Tyhle dvě čísla rozhodují o chování algoritmu víc než cokoliv jiného. **Pravděpodobnost křížení `Pc`:** - `Pc = 0 %` → nová populace je kopií původní, nic se neděje.- `Pc = 100 %` → každý potomek vzniká křížením. **Pravděpodobnost mutace `Pm`:** - `Pm = 0 %` → žádný chromozóm není pozměněn, populace zamrzne v tom, co má.- `Pm = 100 %` → každý chromozóm je pozměněn, což je náhodné prohledávání. **Obvyklé nastavení je vysoké `Pc` (kolem 70-90 %) a velmi nízké `Pm` (kolem 1 %).** Důvod je asymetrický: křížení kombinuje existující dobré vlastnosti a je proto konstruktivní. Mutace je z definice destruktivní a slouží jen jako pojistka proti zamrznutí. Když ti algoritmus konverguje předčasně (celá populace je za dvacet generací stejná), zvyš `Pm` nebo zeslab selekční tlak. Když bloudí a nekonverguje vůbec, `Pm` naopak sniž. ## TSP: obchodní cestující Klasická ukázka toho, proč se operátory musí přizpůsobit reprezentaci. Obchodní cestující má navštívit všechna města právě jednou a vrátit se do výchozího bodu s **minimální celkovou vzdáleností**. **Kódování:** každému městu se přiřadí celé číslo a města se v řetězci vyskytují v pořadí, v jakém jsou navštívena - třeba `(9 3 4 0 1 2 5 7 6 8)`. Tady se ale rozbije obyčejné jednobodové křížení. Vezmi `(1 2 3 | 4 5)` a `(3 4 5 | 1 2)`, zkřiž a dostaneš `(1 2 3 | 1 2)`. Města 1 a 2 jsou dvakrát, města 4 a 5 vůbec. **Takový potomek není řešením úlohy.** Proto **hladové křížení (greedy crossover)**: 1. Vyber první město jednoho rodiče.2. Porovnej druhá města u obou rodičů a vyber to bližší k prvnímu.3. Pokud je vybrané město už v řetězci, vyber od druhého rodiče. Pokud i to už v řetězci je, vyber náhodné dosud nenavštívené město.4. Pokračuj pro třetí, čtvrté a další. **Ten třetí krok je celý trik.** Operátor si hlídá platnost řešení a zároveň dědí po rodičích to, co je na nich dobré - krátké úseky trasy. Tohle je obecný vzorec: **u permutačního kódování musíš křížení navrhnout tak, aby platnost neporušilo.** Existují i další (PMX, OX, cyklické), ale princip je pokaždé stejný. ## K čemu se to používá - optimalizační úlohy - rozvrhy, rozmístění komunikací,- automatické navrhování mechanických systémů,- chování robotů,- teorie her,- genetické programování. ## Kde genetické algoritmy přestávají platit **Jsou pomalé.** Každá generace vyžaduje ohodnocení celé populace. Když fitness funkce trvá vteřinu a máš populaci sto jedinců po tisíc generací, počítáš to den. Pokaždé si spočítej, kolik vyhodnocení fitness si můžeš dovolit, **ještě než začneš psát kód**. **Nedávají žádnou záruku.** Ani úplnost, ani optimalitu, ani ohraničený čas. Vrací nejlepší nalezené řešení a nic o jeho kvalitě neřeknou. Když potřebuješ důkaz optimality, jdi na [A*](Informovane-prohledavani) nebo celočíselné programování. **Když křížení nedává smysl, nedává smysl ani GA.** Klidně to poznáš na tom, že potomci jsou soustavně horší než oba rodiče. V takovém případě jsi napsal drahé náhodné prohledávání a [simulované žíhání](Lokalni-prohledavani#simulované-žíhání) bude lepší. **Parametrů je moc.** Velikost populace, `Pc`, `Pm`, typ selekce, typ křížení, elitismus, ukončovací podmínka. Ladit se dají do nekonečna a **výsledek nejvíc ovlivní reprezentace a fitness, ne ta čísla**. Když ti to nefunguje, přepiš kódování dřív, než začneš točit `Pm`. ## Praktická pravidla **Vždycky zapni elitismus.** Bez něj můžeš nejlepší řešení zahodit a už ho nenajít. **Nejdřív porovnej s náhodným prohledáváním.** Vygeneruj stejný počet náhodných řešení a vezmi nejlepší. Když GA nevyhraje výrazně, něco je špatně s reprezentací nebo fitness. **Měň jednu věc naráz.** Když změníš tři parametry a začne to fungovat, nevíš nic. **Sleduj diverzitu populace, ne jen nejlepší fitness.** Křivka nejlepší fitness vypadá dobře i ve chvíli, kdy je populace už deset generací identická a algoritmus jen tepe na místě. **Fitness měř na tom, co doopravdy chceš.** Optimalizuje se přesně to, co jsi napsal, včetně děr v tom zápisu. Pokud fitness nepenalizuje neplatná řešení, dostaneš neplatné řešení s vynikající fitness. ## Co si odnést **GA je lokální prohledávání s populací a křížením.** Nic mystického se tam neděje. **Křížení je jediná přidaná hodnota.** Když se dvě řešení nedají smysluplně kombinovat, nepoužívej to. **Mutace je pojistka proti zamrznutí, ne motor.** Proto `Pm` kolem procenta. **Reprezentace rozhoduje.** Permutační kódování potřebuje vlastní křížení, jinak vyrábí neplatná řešení. **Elitismus zdarma zachrání nejlepší řešení.** Není důvod ho nemít. **Žádné záruky.** Ani úplnost, ani optimalita, ani odhad chyby. ## Kam dál - **[Lokální prohledávání](Lokalni-prohledavani)** - jednodušší metody, které často stačí- **[Informované prohledávání](Informovane-prohledavani)** - když potřebuješ optimalitu dokazatelně- **[MLP a backpropagation](MLP-a-backpropagation)** - jiný způsob optimalizace, tentokrát gradientem- **[Nástroje pro UI](Nastroje-pro-UI)** - v čem se tohle prakticky píše