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 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í - 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.

Odkud se to vzalo

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

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.

Křížení je jediná věc, kterou genetický algoritmus umí navíc oproti lokálním metodám. 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 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.

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* 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í 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í - jednodušší metody, které často stačí
• Informované prohledávání - když potřebuješ optimalitu dokazatelně
• MLP a backpropagation - jiný způsob optimalizace, tentokrát gradientem
• Nástroje pro UI - v čem se tohle prakticky píše