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