Warning
This page is located in archive. Go to the latest version of this course pages.

Domácí úloha 2: Evoluční algoritmus pro řešení úloh s omezeními

Cílem této domácí úlohy je implementovat a porovnat dva přístupy pro řešení optimalizačních úloh s omezeními pomocí evolučních algoritmů. V rámci této úlohy zhodnotíte úsilí, které jste vložili do implementace algoritmů na předchozích dvou cvičeních.

Minimální požadavky

Porovnejte metody implementované na předchozích cvičeních na již známých problémech optimalizace reálných funkcí se spojitými parametry, g06, g08, g11 a g24, viz minulé cvičení.

První přístup využívá metodu Stochastic Ranking pro uspořádání a porovnání jedinců v populaci. V ideálním případě byste evoluční algoritmus s metodou Stochastic Ranking již měli mít naimplementovaný.

Druhý přístup je založený na tom, že se úloha s omezeními převede na dvoukriteriální úlohu, ve které vystupují tato kritéria:

  • původní optimalizovaná účelová funkce,
  • součet velikostí porušení jednotlivých omezení.

Tento přístup budete realizovat pomocí vícekriteriálního evolučního algoritmu NSGA-II, který byste také již měli mít naimplementovaný.

Úkoly nad minimální požadavky

Multikriteriální přístup s více kritérii

Zahrňte do porovnání ještě jeden přístup využívající multikriteriální EA:

  • První kritérium nechť je původní účelová funkce.
  • Další kritéria ať jsou tvořena velikostí porušení jednotlivých omezení.

Vizualizace dosažených řešení

Implementujte funkci, jak si graficky znázornit dosažená řešení vzhledem ke známému optimálnímu řešení a k daným oblastem přípustných a nepřípustných řešení.

Porovnání zadaných metod na složitějším problému

Porovnejte metody alespoň na jednom problému s více než 3 proměnnými a více než 3 omezeními. Nabízí se např. g04, g05, g09 a g21.

NSGA-II s upraveným turnajovým operátorem

Implementujte binární turnajový operátor pro algoritmus NSGA-II, který zohledňuje přípustná/nepřípustná řešení, viz přednáška, slajd 32: NSGA-II: Constraint Handling Approach. Porovnejte NSGA-II s tímto upraveným turnajovým operátorem se zadanými dvěma přístupy.

Jiná metoda práce s omezeními

Implementujte, popiště a zahrňte do porovnání nějakou další metodu pro práci s omezeními, kromě těch, které jsme již zmínili.

Dvoj nebo multikriteriální EA jiný než NSGA-II

Implementujte jiný typ MOEA než NSGA-II a použijte ho ve dvoj nebo multikriteriálním přístupu pro práci s omezeními místo NSGA-II. Algoritmus popište a zahrňte do porovnání.

Hodnocení

Podobně jako u první domácí úlohy i teď bude nutné splnit jisté minimální požadavky, jejichž splněním si zajistíte minimální potřebný počet bodů. Každé další vylepšení vám přinese body navíc, až do maximálního počtu 10 bodů.

Splnění minimálních požadavků

Abychom tuto úlohu považovali za splněnou, musíte

  • implementovat oba přístupy
  • porovnat oba přístupy na daných problémech
  • stručně a adekvátně tyto algoritmy a výsledky popsat v reportu.

Co odevzdat

DO BRUTE do úlohy DU2 Budete odevzdávat ZIP archiv obsahující

  • zdrojové kódy vaší implementace,
  • README soubor, kde popíšete, jak a co zkompilovat a jak a co spustit, pokud chci získat výsledky algoritmu A na instanci B,
  • stručný report s popisem řešení (viz níže).

Součástí hodnocení může být předvedení funkčnosti implementace na některém cvičení. Pokud jste si pro implementaci vybrali jiný jazyk než Python, Javu, nebo C/C++, bude předvedení funkčnosti povinné.

Očekávaný obsah reportu:

  • Adekvátní popis (nikoli výpis zdrojového kódu) algoritmů a použitých operátorů.
  • Popis nastavení experimentu (jak jste porovnávané algoritmy nastavili, kolik prostředků/času/generací/ohodnocení jste jim na optimalizaci dali, kolik opakovaných pokusů jste dělali, apod.).
  • Smysluplné porovnání algoritmů v tabulkové a grafické formě.
  • Upozornění na příp. nedostatky použité experimentální procedury.
  • Explicitní seznam věcí realizovaných nad rámec minimálních požadavků s odkazy na místa ve vašich kódech, kde jejich implementaci nalezneme, a návrh jejich bodového hodnocení.

Bodování

Za úlohu můžete získat maximálně 10 bodů.

Bodů Za co
6 Za splnění minimálních požadavků.
+1 Za implementaci multikriteriálního (nikoli jen 2kriteriáního) přístupu.
+1 Vizualizace dosažených řešení
+1 Porovnání zadaných metod na složitějším problému
+1 NSGA-II s upraveným turnajovým operátorem
+1 Za porovnání s dalším přístupem pro práci s omezeními.
+2 Za porovnání s dalším přístupem využívající jiný multikriteriální EA.
courses/a0m33eoa/du/du2.txt · Last modified: 2018/11/12 12:23 by xposik