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.

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ý.

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

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

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.

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.

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.

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

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ů.

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.

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

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