6. Multi Objective Optimization & NSGA II.ipynb

{
 "cells": [
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Multi Objective Optimization & NSGA-II\n",
    "Many problems require looking at multiple costs / benefits and arriving at an aoutcome which has the greatest overall satisfaction. However, often decreasing the cost in one objective may increase it in another.\n",
    "\n",
    "## I. Formal Definition\n",
    "* Let there be $M$ functions to be optimized (minimized or maximized): $F_1(x), F_2(x), \\ldots, F_M(x)$\n",
    "* subject to $J$ inequality constraints: $g_j(x)\\geq 0, \\forall j=\\{1,\\ldots,J\\}$\n",
    "* and $K$ equality constraints: $h_k(x)=0, \\forall k=\\{1,\\ldots,K\\}$.\n",
    "* $x\\in D$, that is, the domain of the decision space is $D$. If $A_i\\leq x_i\\leq B_i, \\forall i=\\{1,\\ldots,n\\}$, then $D$ is a hypercube defined by the \"box constraints\" $(A_i, B_i)$\n",
    "\n",
    "### Dominated vs. Non-dominated solutions\n",
    "Assuming we want to *minimize* both $F_1(x)$ and $F_2(x)$. Then, a solution $x_1$ is said to **dominate** a solution $x_2$ if both of the folowing are true:\n",
    "1. $F_1(x_1)\\leq F_1(x_2)$ and $F_2(x_1)\\leq F_2(x_2)$\n",
    "2. $F_1(x_1)< F_1(x_2)$ or $F_2(x_1)< F_2(x_2)$\n",
    "\n",
    "Hence, $x_1$ dominates $x_2$ if it is not worse than $x_2$ in any of the objectives and is better in atleast any one of them.\n",
    "\n",
    "**Pareto Optimality**: A solution $x^*$ is pareto optimal if there does not exist a solution $x'\\in D$ which dominates $x^*$.\n",
    "\n",
    "**Pareto Front**: The set of all pareto optimal solutions is called the pareto front. Hence the aim of a multi objective optimization algorithm is to deduce the pareto front or a near optimal pareto front. Below is an example fo a pareto front:\n",
    "\n",
    "![A pareto front](Images/pareto_front.png)\n",
    "\n",
    "## II. Solving MOO Problems\n",
    "Solving Multi Objective Optimization (MOO) problems has two goals:\n",
    "* Convergence: Finding solutions as close as possible to the pareto front\n",
    "* Diversity: Find a good spread of solutions of the front\n",
    "\n",
    "The techniques can be broadly divided into two approaches:\n",
    "\n",
    "![Taxonomy of appraoches to solving MOO problems](Images/MOO_techniques.png)\n",
    "\n",
    "1. **Classical approach**:\n",
    "  * <u>Weighted method</u>: Use higher level information to estimate an \"importance vector\" that ranks which objective are more important than others. Using this importance vector, convert the multi-objective problem into a single objective optimization problem (eg. weighted sum). Mathematically, problem becomes: minimize $r_k F_1(x)+F_2(x)$, subject to $g_j(x)\\geq 0, \\forall j=\\{1,\\ldots,J\\}, x\\in D$. Here, $r_k$ is the ratio of weights on $F_1(x)$ and $F_2(x)$. This problem is then solved using single objective optimization methods.\n",
    "  \n",
    "    Diadvantages:\n",
    "    * You must solve a Single Objective many times for each ratio of $w_1 /w_2$.\n",
    "    * No control over area of objective space searched.\n",
    "    * Appraoch will not work on non-convex parts of the tradeoff curve (The solution is always where the tangent is $w_1/w_2$. If there are two such points, then the optima is the lower of the two points.)\n",
    "    ![Missed pareto optimal solutions in non-convex objective space](Images/weighted_moo.png)\n",
    "    Here, you can change the ration of the weights to go from A to B, but you will still miss the non-convex part of the pareto optimal.\n",
    "  * <u>Constraint Method</u>: Optimize one objective and constrain all the others. For example, minimize $F_2$, subject to $F_1\\leq R_i$ and then solve the problems from many values of $R_i$. This approach **will work** on non-convex tradeoff curves.\n",
    "    \n",
    "    Disadvantages:\n",
    "    * Must solve a single optimization problems many times.\n",
    "    * Solution highly depends on the values of $R_i$ chosen. It has to be carefully chosen so that it lies within the feasible objective space.\n",
    "\n",
    "    ![Selecting the ideal $R_i$ for constrained MOO](Images/constrained_moo.png)\n",
    "\n",
    "    Here, it can be seen that the solution will depend entirely on the value of $R_i$. For $R_i = \\epsilon_4$, then the solution will be point C. Similarly, $R_i = \\epsilon_3 \\to B$, $R_i = \\epsilon_2 \\to A$. If $R_i = \\epsilon_1$, then we will not be able to find any solution at all.\n",
    "2. **Multi Objective Approach**: Using an ideal multi-objective optimizer, achieve **multiple trade-off solutions**. Choose one among these trade off solutions using some higher level knowledge. These methods usually apply evolutionary algorithms.\n",
    "\n",
    "## III. Non Dominated Sorting Genetic Algorithm (NSGA II)\n",
    "Developed by [K. Deb et al (2000)](https://www.iitk.ac.in/kangal/Deb_NSGA-II.pdf), NSGA-II has several improtant ideas:\n",
    "* It divides the population into multiple fronts\n",
    "* It uses the frot to determine fitness\n",
    "* It examines the distance between points close together on a front to determine fitness.\n",
    "Below is the overall framework of NSGA.\n",
    "\n",
    "![NSGA-II Framework](Images/NSGA_Framework.png)\n",
    "\n",
    "### Sorting the population into \"Fronts\"\n",
    "1. Sort the  population into solutions of \"non-dominated fronts\". The first such front is the Pareto optimal solution, i.e., all the points fromFrant 1 are non-dominated by all other points in the solution  space.\n",
    "2. Generate teh 2nd frot by reomving all points from the 1st front and re-computing the pareto optimal solution. The points on this 2nd Pareto optimal curve are the 2nd front.\n",
    "3. Repeat until $n$th front, removing all the points from the $1$st to $(n-1)$th fronts and finding the Pareto optimal for the remaining points.\n",
    "For example, if we are trying to minimize two functions $f_1$ and $f_2$, then below could be the different fronts obtained.\n",
    "\n",
    "![Example of Pareto optimal fronts in NGSA](Images/nsga_fronts.png)\n",
    "\n",
    "### NSGA II - Handling Diversity\n",
    "To have **diversity**, NSGA II has a probability of seleting as a parent an individual from any of the different fronts. However, this probability of being selected is less if the individual is located on a \"worse\" front. NSGA also tries to avoid parents that are too similar to each other so it has a method of computing \"crowding\". The likelihood of selecting a point for a parent is reduced if it is crowded.\n",
    "\n",
    "### Parameters in NSGA II\n",
    "We have the following parameters to be selected in NSGA II (the 1st three are common for all genetic algorithms):\n",
    "* Population size\n",
    "* crossover location probability\n",
    "* Mutation rate\n",
    "* $\\epsilon$, the difference in base fitness between two adjacent fronts\n",
    "* $\\sigma_{share}$, the maximmum Euclidean distance between two points on the same \"front\" to consider them in the \"crowding\" calculations.\n",
    "\n",
    "### Elitism in NSGA\n",
    "Do the following at every iteration:\n",
    "1. Do crossover on the population (of size $N$) and generate a set $Q_t$ of $N$ offspring, where $t$ is the generation number.\n",
    "2. Combine the set of parents and children into a new set $R_t$\n",
    "3. Do sorting as shown below and generate a new population of parents $P_{t+1}$ of size $N$\n",
    "\n",
    "![Elistism in NSGA](Images/nsga_elitism_algo.png)\n",
    "\n",
    "This approach has the following advantages:\n",
    "* A good population is mantained by the elitism, which saves the best parents by letting them compete with the offspring.\n",
    "* Diversity among non-dominated solutions is introduced by the crowding comparison procedure, wich is used with the tournament selection during the population reduction phase.\n",
    "\n",
    "### Crowded Tournament Selection\n",
    "Each individual has the following metrics:\n",
    "* Rank $r_i$ that depends on the rank of the front it belongs to.\n",
    "* Crowding distance $d_i$ (described later)\n",
    "\n",
    "**Crowded Tournament Selection Operator:** A solution $i$ wins a tournament with another solution $j$ if any of the following conditions are true:\n",
    "1. If solution $i$ has a better rank, that is, $r_i < r_j$\n",
    "2. If they have the same rank but solution $i$ has a better crowding distance than solution $j$, that is, $r_i = r_j$ and $d_i > d_j$\n",
    "Below is defined the `crowding_distance_assignemnt()` function, which takes as input the non-dominated set (a front) $\\mathcal{I}$:\n",
    "\n",
    "![Crowd distance algorithm for NSGA II](Images/nsga_crowding_algo.png)\n",
    "\n",
    "The above function is equivalent of calculating for the $i$th solution, in it's front (marked with solid circles), the average side-length of the cuboid.\n",
    "\n",
    "![Crowd distance cuboid](Images/nsga_crowd_cuboid.png)\n",
    "\n",
    "We keep in mind that crowding is used to determine BOTH:\n",
    "1. which individuals to keep from the last allowable front. This happens when the last allowable front has for example 10 indivudals but only 4 can be carried forward into the new generation; AND\n",
    "2. in tournament secetion to generate new offspring.\n",
    "\n",
    "## IV. Visualiation of Multi-Objective Solutions for more than 2 Objectives\n",
    "For MOO problems, we have two desired properties: converge and even distribution. Therefore, for any solution, we can have two types of errors:\n",
    "\n",
    "![Types of errors in MOO problems](Images/moo_errors.png)\n",
    "\n",
    "As seen above, these errors can be easily visualized for the 2 objective function case. However, if we have more than 2 objective function, this becomes diffcult. Below are some methods that can be used to visualize solutions for more than 2 objectives:\n",
    "1. Scatter plot visualization: In each box, two objectives are plotted in any one time. The diagonal represents which function is being drawn.\n",
    "\n",
    "![Scatterplot visualization](Images/moo_scatter.png)\n",
    "\n",
    "2. Value Path visualization: Each line represents a single solution on the Pareto front. The objective values are plotted after normalization. From the example below, you see that objective 1 and 3 arerelated int eh same direction, whereas objective 2 is a competing objective.\n",
    "\n",
    "![Value Path visualization](Images/moo_valuepath.png)\n",
    "\n",
    "3. Bar Chart method: Every pareto optimal is plotted as a bar graph for each of the objective functions seperately.\n",
    "4. Star coordinate visualization: Each solution has a circle, and each of the radial line is the function value of that objective for that solution.\n",
    "\n",
    "![Star coordination visualization](Images/moo_star.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}