Vícekriteriální evoluční algoritmus NSGA-II

Cílem dnešního cvičení je vytvoření vícekriteriálního evolučního algoritmu typu NSGA-II.

Jak sami uvidíte, spočívá to pouze v několika jednoduchých úpravách základního evolučního algoritmu, který jste si naimplementovali na minulém cvičení.

Pokud úkoly nestihnete na cvičení, dokončete je doma.

První úprava se týká způsobu porovnání dvou řešení podle jejich kvality. Jak již víte, u jednokriteriálního evolučního algoritmu pracují selekční a náhradové strategie s fitness funkcí, která vrací jednu hodnotu pro každé řešení. Zde je tedy porovnání dvou řešení jednoduché.

Ovšem u vícekriteriální úlohy už to tak přímočaré není, protože každé řešení má přiřazeno několik hodnot udávajících jeho kvalitu. V algoritmu NSGA-II se pro porovnání dvou řešení používají dva ukazatele odvozené z původních hodnot kritérií daného řešení:

• číslo nedominovaného frontu, do kterého řešení patří,
• unikátnost řešení v daném frontu (tzv. crowding distance, viz přednáška).

Vašim prvním úkolem tedy je implementovat metodu pro výpočet frontů a crowding distance pro všechna řešení v populaci.

NSGA-II používá tzv. binární turnajový operátor, který prohlásí řešení $x_i$ za lepší než řešení $x_j$, když platí jedna ze dvou následujících podmínek:

• řešení $x_i$ je z lepšího frontu než řešení $x_j$,
• řešení $x_i$ je ze stejného frontu jako řešení $x_j$, ale má větší hodnotu crowding distance.

Implementujte tento operátor, který pro dvě kandidátní řešení $x_i$ a $x_j$ vrátí true, když je $x_i$ lepší než $x_j$.

Poslední modifikace se váže k náhradové strategii. NSGA-II používá náhradovou strategii, která ze staré populace $P_t$ a populace nově vygenerovaných řešení $Q_t$ vytvoří novou populaci $P_{t+1}$ tak, že z množiny řešení $P_t \cup Q_t$ vybere potřebný počet řešení z nejlepších nedominovaných frontů, viz přednáška.

Implementujte tuto náhradovou strategii.

Teď už máte všechny potřebné ingredience k tomu, abyste zkompletovali a rozběhli algoritmus NSGA-II.

Jako testovací úlohu můžete použít problém vícekriteriálního batohu, Multiobjective Knapsack Problems viz Multiobjective Optimization Library. Podobně jako u TSPLib i tady mají vstupní soubory jednotný formát a pro každou instanci je známá hodnota doposud nejlepšího řešení.

Tento problém je pro naše účely šikovný v tom, že můžete použít jednoduchou binární reprezentaci (vektor délky $n$, kde $n$ je počet položek) s klasickými operátory křížení a mutace, jak jste si je v předešlých hodinách naimplementovali.