====== Multi-objective EAs ======

The goal of this lab exercise is to implement a multi-objective evolutionary algorithm (MOEA), in particular the [[https://ieeexplore.ieee.org/document/996017|NSGA-II]] one.

As you will see, it consists in modifying just a few parts of the standard evolutionary algorithm that you implemented in the last lab exercise.

**If you do not complete all parts during the lab time, finish the work at home.** 


===== Non-dominated fronts computation =====

The first modification is related to the way two candidate solutions are compared w.r.t. their quality. In case of a single-objective optimization, the comparison of two solutions is based just on a single fitness value assigned to each solution. Simply, the smaller the fitness value, the better the solution is in case of the minimization problem. Similarly, but using the “larger” relation for the maximization problem.

It is not that straightforward in case of multi-objective optimizations because there are multiple quality measures assigned to each solution. Various strategies for comparing two solutions are used in various MOEAs. NSGA-II algorithm compares solutions based on two performance indicators derived from the original objective values [please, refer to the lecture slides for details]:
  * **non-dominated front number**,
  * **uniqueness** of the solution within its non-dominated front (i.e., the //crowding distance//).

Your first task is to implement a function/method that calculates the non-dominated front number and the crowding distance for all individuals in the population.

^ Input | Evaluation of the whole population, i.e., set of vector of objective values for each solution. |
^ Output | The non-dominated front number and crowding distance for each solution. |

<WRAP center round download 100%>
The original test data were wrong. Now we are at attempt two!

Test data (thanks to Jan Pikman): {{:courses:a0m33eoa:labs:test_small.txt |small}}, {{ :courses:a0m33eoa:labs:test_large.txt |large}}. All objectives are minimized.

If your results are different, email to [[mailto:petr.posik@cvut.cz|Petr Pošík]].

</WRAP>

===== Binary tournament operator =====

NSGA-II uses a binary tournament operator $t(x_i, x_j)$ that returns true, meaning the $x_i$ is better than $x_j$, if one of the following conditions holds:
  * $x_i$ is from the better front than $x_j$, i.e., $front(x_i) < front(x_j)$,
  * both, $x_i$ and $x_j$ are from the same front, but $x_i$ is more unique than $x_j$ within the front, i.e., $front(x_i) == front(x_j)$ AND $crowding(x_i) > crowding(x_j)$.

Your second task is to implement this binary tournament operator.

^ Input | Two solutions $x_i$ and $x_j$ |
^ Output | True, if $x_i$ is better than $x_j$. False, otherwise. |


===== Replacement strategy =====

The last task is to implement the replacement strategy used in NSGA-II. It works so that it takes two populations
  * $P_t$ ... the current population at time $t$,
  * $Q_t$ ... the population of solutions newly created of the population $P_t$
and selects out of the $P_t \bigcup Q_t$ a new set of the best solutions for the population $P_{t+1}$, please see the lecture slides for details.


^ Input | Populations $P_t$ and $Q_t$ |
^ Output | Population $P_{t+1}$ |

**Now, you have all ingredients needed to complete the NSGA-II algorithm!**


===== Experimental evaluation =====

To test your NSGA-II implementation you can use the **Multi-objective 0/1 Knapsack Problem**. This problem suits well to our purposes as you can use the simple binary representation with the mutation and crossover operators that you have already implemented.

For the definition of a Single-objective 0/1 Knapsack Problem please consult [[https://en.wikipedia.org/wiki/Knapsack_problem|Wikipedia]]. 

The multi-objective version is well described in this [[https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=797969&tag=1|article]]. In MO variant with D-dimensional knapsack, the weight and value of each item $i$ for knapsack $d$ is given by a D-dimensional vector $w_i=(w_{i1},\dots, w_{iD})$ and $v_i=(v_{i1},\dots, v_{iD})$. Similarly, the knapsack has a D-dimensional capacity vector $W = (W_1, \dots, W_D)$. Assuming the solution is represented by a binary vector $x = (x_1, \ldots, x_m)$, the goal is to maximize 

$$\text{maximize } f(x) = (f_1(x), \dots, f_D(x)), $$

where

$$f_d(x) = \sum_{i=1}^m v_{id}x_i,$$

such that the sum of weights in each dimension $d$ does not exceed $W_d$, i.e.

$$\forall d \in \{1,\ldots,D\}: \sum_{i=1}^m w_{id}x_i \leq W_d.$$


<WRAP center round download 100%>
You can use the [[https://sop.tik.ee.ethz.ch/download/supplementary/testProblemSuite/|Test Problem Suite]] with various data sets and the best known solutions for each of them available.


In case of any issues downloading the test problems from the site above, you can download the problem definitions and Pareto fronts {{ :courses:a0m33eoa:labs:knapsack.zip |here}}.
</WRAP>


Data sets in Test Problem Suite use the following notation:
  * n-th knapsack stands for n-th dimension, $n \in \{1,\dots,D\}$.
  * Profit stands for the value.