Warning
This page is located in archive.

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?
courses/a0m33eoa/cviceni/tyden_04.txt · Last modified: 2018/10/18 11:07 by xposik