# 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|101
Matka:       11100|001

Potomek 1:   11101|001
Potomek 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.

```mermaid
flowchart 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