====== Evoluční algoritmy pro binární a reálnou reprezentaci ======


Cílem dnešního cvičení je vytvoření evolučního algoritmu řešícího optimalizační problémy, s nimiž jsme se seznámili v minulých cvičeních. Specifikace jednotlivých součástí EA uvedená níže je spíše konceptuální: implementaci lze realizovat mnoha různými způsoby, berte proto popis uvedený níže spíše jako specifikaci schopností, které má implementace mít, než jako specifikace samotné implementace.

** Pokud úkoly nestihnete na cvičení, dokončete je doma. **


===== Populace =====
Hlavním rozdílem EA a lokálního prohledávání je fakt, že stav algoritmu je reprezentován populací a nikoli jediným kandidátským řešením. Rozmyslete si, jak budete populaci reprezentovat. Zvažte výhody a nevýhody následujících možností:
  * seznam jedinců,
  * 2D pole (např. v MATLABu či numpy),
  * specializovaná třída reprezentující populaci.


===== Inicializace =====
Vytvořte funkci, která vytvoří inicializovanou populaci kandidátských řešení. Výsledek samozřejmě bude závislý na zvolené reprezentaci. Funkce může využít už existující funkci pro inicializaci jediného kandidátského řešení.

^ Vstup | Velikost populace |
^ Vstup | Funkce pro inicializaci jednoho kandidáta |
^ Výstup | Inicializovaná populace kandidátů |

Pokud se vám nepovede vytvořit univerzální inicializační proceduru, nevadí. Prostě jich budete muset vytvořit víc, specializovanějších.


===== Selekce =====
Implementujte funkci pro selekci rodičů.

^ Vstup | Počet rodičů, kteří mají být vybráni |
^ Vstup | Seznam hodnot fitness jedinů v populaci |
^ Výstup | Indexy rodičů v populaci. (Někteří jedinci se mohou stát rodiči vícekrát, někteří se rodiči nestanou vůbec.) |

Vyberte si jeden typ selekce a ten implementujte přednostně. Ostatní mohou počkat. Můžete zkusit:
  * Žádná selekce: všichni jedinci jsou vybráni jako rodiče.
  * Náhodná selekce.
  * Turnajová selekce.
  * Ruletová selekce.
  * Pořadová selekce.


===== Křížení =====
Implementujte funkci pro křížení. Rozmyslete, co přesně budou vstupy a výstupy (tedy kolik rodičů bude do funkce vstupovat a kolik potomků bude generovat).

^ Vstup | Seznam rodičů. |
^ Výstup | Jeden nebo více potomků. |

Opět, vyberte si jeden typ křížení a implementujte jej přednostně. Ostatní nechte na později. Můžete zkusit
  * Jednobodové křížení (pro bin. i real. reprezentaci).
  * Dvoubodové křížení (pro bin. i real. reprezentaci).
  * Rovnoměrné křížení (pro bin. i real. reprezentaci).
  * Aritmetické křížení (pro real. repr.)
  * "Blend" křížení (pro real. repr.)
  * Atd.


===== Mutace =====

S mutací si nemusíme dělat hlavu. Perturbační funkce, které jsme implementovali v minulých cvičeních jsou vlastně operátory mutace.


===== Náhradová strategie =====

Implementujte funkci pro náhradovou strategii.

^ Vstup | Ohodnocená stará populace (nebo staří jedinci a jejich ohodnocení). |
^ Vstup | Ohodnocená populace nových potomků (nebo potomci a jejich ohodnocení). |
^ Výstup | Ohodnocená populace přeživších jedinců (nebo přeživší jedinci a jejich ohodnocení). |

Vyberte si jeden typ náhradové strategie a implementujte ji přednostně. Ostatní nechte na později. Můžete zkusit:
  * Generační náhradová strategie (zahodí starou populaci, jen potomci přežijí).
  * Steady-state strategie:
    * Náhodná (spojí starou populaci s potomky a vybere mezi nimi náhodně).
    * Truncation (spojí starou populaci s potomky a zahodí nejhorší z nich).
    * Turnajová.
    * Ruletová.
    * Pořadová.

Až budete vybírat selekci a náhradovou strategii pro vlastní EA, alespoň jedna z těchto dvou částí by měla generovat nějaký selekční tlak, tj. preferovat lepší jedince. Jinak bude váš EA fungovat jako náhodné prohledávání.


===== Evoluční algoritmus  =====
Vytvořte funkci/třídu, která bude implementovat evoluční algoritmus.

^ Vstup | Účelová funkce, jejíž optimum hledáme. |
^       | Inicializační funkce. |
^       | Selekční funkce. |
^       | Operátor křížení. |
^       | Pravděpodobnost křížení. |
^       | Operátor mutace. |
^       | Pravděpodobnost mutace. |
^       | Náhradová strategie. |
^       | Ukončovací podmínky. |
^ Výstup | Nejlepší nalezené řešení a jeho kvalita. |
^        | Statistiky o průběhu optimalizace. |

Zvažte, zda místo mnoha vstupních parametrů funkce či mnoha vlastností třídy nevyužít nějakou datovou strukturu, která by reprezentovala konfiguraci algoritmu a do funkce se předávala jako jediný parametr.

===== Porovnání =====

S využitím výstupů LS algoritmu a EA algoritmu a vizualizačních nástrojů z minulého cvičení byste měli být schopni vytvořit jednoduché porovnání obou typů algoritmů aplikovaných na stejný problém.

Zkuste oba typy algoritmu porovnat na různých binárních a reálných problémech.
  * Jaký výsledek byste očekávali na jednoduchých unimodálních problémech? Shoduje se pozorování s očekáváním?
  * Jaký výsledek byste očekávali na složitějších multimodálních či klamných problémech? Shoduje se pozorování s očekáváním?