Search
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í.
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čů.
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).
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.
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.
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.