14. Princip genetických algoritmů, význam selekčního tlaku pro jejich funkci. (NI-KOP)

---

Genetické algoritmy

Inspirace přírodní evolucí:

• Napodobení procesu přírodního výběru
• Řešení optimalizačních problémů metodou "přežití nejzdatnějších"

Operátory:

• Binární: křížení, selekce
• Unární: mutace

Genetický algoritmus - cyklus

1. Počáteční populace
   1. Vytvoření počáteční populace řešení
2. Selekce
   1. Ohodnoceni kvality každého jedince pomoci fitness funkce
   2. Výběr nejlepších jedinců pomoci selekčního algoritmu
   3. Slouží k intenzifikaci
3. Křížení
   1. Vytvoří nove generace pomocí binárních operací
   2. Existuje vice způsobů křížení: jednobodové, uniformní...
4. Mutace
   1. Náhodné změny v genetické informaci jedince
   2. Slouží k diverzifikaci
5. Proces se opakuje do splnění ukončovací podmínky

Selekce

Ruletový výběr (Roulette Wheel Selection)

Princip:

1. Každý jedinec v populaci dostává prostor na pomyslné ruletě úměrný své fitness hodnotě. Čím vyšší fitness, tím větší plocha na kole.
2. Vybereme jedince pomoci náhodného výběru úhlu v kružnici. Vybereme toho jedince do kterého uhel spadá
   1. Nebo můžeme vybrat jeden uhel a tento uhel postupně z replikovat

Selekční tlak

• Přímá úměra mezi zdatností a poměrnou pravděpodobností výskytu často zdegeneruje populaci – je třeba nadržovat slabším
  • Přepočítání zdatnosti lineární funkcí (scaling)
  • Použití pořadí ve zdatnosti místo zdatnosti (ranking)
  • Prahování, zkrácený výběr (truncation selection)

Turnajový výběr (Tournament Selection)

Princip:

1. Náhodně vybere skupinu $m$ jedinců
2. Mezi jedinci ve skupině proběhne "turnaj", vítěz postupuje.
   1. Vyhraje jedinec/jedinci s nejvyšší fitness funkcí

Selekční tlak

• Selekční tlak se řídí se velikostí turnaje
  • turnaj přes celou populaci - jistota výběru nejlepšího jedince intenzifikace
  • turnaj s jedním jedincem - žádný selekční tlak diverzifikace

Zkrácený výběr (Truncation Selection)

• Z populace vybereme $n$ nejzdatnějších jedinců

Elitismus

• Vybereme nejlepších $n$ jedinců z minulé populace aby pršeli do nové populace
• Tento typ výběru jde kombinovat s ostatními typy selekce

Křížení

• Jedná se o reprodukční operátor, který simuluje náhodnou výměnu informací obsažených v rodičích
  • Jednobodové – náhodně vybereme pozici uvnitř binárního vektoru
    • hodnoty před touto pozicí potom zdědí z jednoho rodiče, zbytek zdědí z druhého rodiče
    • 
  • Dvoubodové – obdobně jako u Jednobodového křížení, ale vybereme dvě pozice
    • 
  • Uniformní – každý bit binárního vektoru vybereme náhodně z jednoho nebo druhého rodiče
    • 

Selekční tlak v genetických algoritmech

Selekční tlak = míra preference lepších jedinců v populaci

Konvergence vs. Divergence:

• Konvergence: Zužování prostoru řešení
• Divergence: Rozšiřování genetické diverzity

Diverzifikace vs. Intenzifikace:

• Diverzifikace: Průzkum stavového prostoru
• Intenzifikace: Zaměření na perspektivní oblasti

Malý selekční tlak:

• Pomalá evoluce
• Zachování genetické diverzity
• Riziko pomalé konvergence až divergence pokud je pravděpodobnost mutace moc velká

Velký selekční tlak:

• Rychlá konvergence
• Riziko degenerace populace
  • Vytvoření populace která ma stejnou strukturu
  • Ztráta genetické rozmanitosti
• Uvíznutí v lokálním extrému

Typy genetických algoritmu

• Genetický algoritmus
• Genetický programovaní
• Evoluční strategie
• Evoluční programovaní