3. Evoluční algoritmy

Definice¶

Individuum
- Řešení problému zakódované chromozómem + jeho ohodnocení fitness fukcí.
Chromozóm
- Celková reprezentace řešení (např. nějaký bitový vektor, string charů, strom, reálná čísla, obrázek,...).
Fitness
- Mira kvality přirazená k individuu. Označuje jak dobře se adaptovala k prostředí.
Gen
- Základní jednotka ze které se skládá chromozóm
Genotyp
- Konkrétní kódování jedince na jeho chromozómu.
Fenotyp
- Projev genotypu, tedy jeho význam (např. nějaká sekvence čísel může značit rychlost jedince.

Genetické algoritmy
Genetické programování - řešení jsou ve formě programů, jejich fitness se určuje dle schopnosti řešení daného výpočetního problému
Evoluční programování - podobné genetickému programování, ale místo toho se vyvíjí parametry programu (ne program samotný)
Evoluční strategie

Je to algoritmus na selekci jedinců které se budou reprodukovat.
Každý jedinec má šanci na výběr, ale upřednostňuje výběr lepších jedinců tím, že pravděpodobnost jejich výběru je přímo úměrná jejich fitness funkci (fitness jedince / součet fitness všech jedinců).
- $P_i=\frac{fitness_i}{\sum_{j=i}^{PopSize}{fitness_j}}$

Rank selekce funguje stejně jako ruletová, ale pravděpodobnost není vypočítána přímo z fitness, ale z pořadí jak dobrý daný jedinec je.
- Např. když máme dva, tak ten lepší (vyšší rank = 2) má PST 0.66 a ten horší (rank = 1) 0.33.
Toto je robustnější než klasická ruleta.

Linear scaling
- Přeškálování distribuce fitness hodnot, abychom získali požadovaný selekční tlak.
Fitness sharing
- Když je hodně podobných jedinců, tak se jejich fitness snižuje (dobří jedinci v hustě zastoupených místech budou mít horší fitness než stejně dobří, kteří jsou sami).
Elitismus
- Vždy do další generace přeneseme nejlepšího jedince bez jakékoliv změny, aby byla garance nezhoršení se.
Ostrovní model
- Vyvíjíme několik populací odděleně a občas je nějaká pravděpodobnost, že se část populací zkříží mezi sebou.
Katastrofa
- Zabijeme většinu populace a necháme přežít jen ty nejsilnější, zbytek doplníme random.

Snaží se analyzovat efekt selekce, crossoveru a mutace aby napomohla
- Hledat důležité části chromozomů
- Jak úspěšně kombinovat dvě existující řešení
Předpokládá binární reprezentaci řešení, proporciální ruletovou selekci, 1-point crossover a bit-flip mutace.
Schéma
- Šablona, která definuje sadu řešení, která jsou si nějakým způsobem podobná.
- Obsahuje 0, 1 a * jakožto wildcard symbol, značící libovolnou hodnotu.
- Pokrývá $2^r$ stringů, kde $r$ je počet použití *
- Např. $1 1 * 0 *$ značí: $11000$ , $11100$ , $11001$ , $11101$ .
Defining length
- Vzdálenost mezi prvním a posledním non-wildcard symbolem (počet pozic kde může 1-point crossover narušit schéma).
- Například: $S_a=1*1**10*$
  - Vzdálenost je 6
Order
- Počet non-wildcard symbolů (počet pozic kde může bit-flip mutace narušit schéma).
- Například: $S_a=1*1**10*$
  - Order je 4
Fitness
- Průměrná fitness všech stringů, které schéma reprezentuje.
- Například: $S_a=1*1**10*$
  - Celkově ma $2^4$ stringu
  - 1 string s fitness 3, 4 s f=4, 6 s f=5, 4 s f=6, 1 s f=7
  - $f(S_a) = (1 · 3 + 4 · 4 + 6 · 5 + 4 · 6 + 1 · 7)/16 = 80/16 = 5$

$m(S, t)$ je počet jedinců patřící pod schéma S v generaci t
$f_S(t)$ je průměrná fitness hodnota pro strings patřící do schématu S v generaci t
$f(t)$ je průměrná fitness hodnota přes všechny strings v populaci.
Počet jedinců patrici do t+1 generace
- $m(S,t+1)=m(S,t)\frac{f_S(t)}{f(t)}$