====== 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. **


===== Výpočet nedominovaných frontů =====

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.
 
^ Vstup | Populace s napočítanými hodnotami kritérií pro každého jedince |
^ Výstup | Populace s napočítanými hodnotami frontů a //crowding distance// pro každého jednince |


===== Binární turnajový operátor =====

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

^ Vstup | dvojice řešení $x_1$ a $x_2$ |
^ Výstup | true, když je $x_1$ lepší než $x_2$ z hlediska binárního turnajového operátoru. Jinak false. |


===== Náhradová strategie =====

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.

^ Vstup | populace řešení $P_t$ a $Q_t$ |
^ Výstup | populace $P_{t+1}$ |

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


===== Experimentální ověření funkčnosti NSGA-II =====

Jako testovací úlohu můžete použít problém vícekriteriálního batohu, **Multiobjective Knapsack Problems** viz 
[[https://sop.tik.ee.ethz.ch/download/supplementary/testProblemSuite/|Test Problem Suite]]. 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.