Non-dominated sorting genetic algorithm II (NSGA-II)
In this post, I will attempt to explain some basic ideas of multi-objective optimization and the non-dominated sorting genetic algorithm II (known as NSGA-II to it’s friends). I will also provide an example in Python using the library “inspyred”.
But first let’s talk multiple objectives…
Multi-objective optimization problems deals with conflicting objectives, i.e. while one objective increases the other decreases. There is no a unique global solution but a set of solutions.
In general we are interested in the following mathematical problem type:
A solution is a vector of n decision variables :
Furthermore, the problem is subjected to J inequality constraints and K equality constraints. Additionally, each variable has an upper and/or lower bound associated with it.
A solution that satisfies all constraints and variable bounds is called a feasible solution. The set of all feasible solutions is called the feasible region, or S. The term “search space” is also used as a synonym to feasible region. The objective space is constituted by the possible values of the M objectives functions for all solutions in S.
A solution x(1) is said to dominate the other solution x(2) if both condition 1 and 2 below are true:
- Condition 1: x(1) is no worse than x(2) for all objectives
- Condition 2: x(1) is strictly better than x(2) in at least one objective
The mathematical notation for x(1) dominates x(2) is:
Among a set of solutions P, the non-dominated set of solutions P‘ are those that are not dominated by any member of the set P
Globally Pareto-optimal set:
The non-dominated set of the entire feasible search space S is the globally Pareto-optimal set.
An example from civil engineering: the design of a cantilever beam. Minimization is performed on the deflection and weight, the decision variables are length and diameter. The diagram shows the associated objective space: values for deflection and values for weight for different settings of length and diameter.
Figure 1: Weight vs Deflection. Source 
From this plot, it is easy to observe the tradeoff between deflection and weight in the Global Pareto-optimal set.
Figure 2: The left plot is the feasible decision variable space and the right is the feasible objective space. Source 
In the objective space near the origin in figure 2, a curve is formed, it is the Pareto-optimal front. No feasible solutions can produce objectives any closer to the origin. This pareto front represents the best tradeoffs possible.
Now for NSGA-II
NSGA-II is an evolutionary algorithm. Evolutionary algorithms where developed because the classical direct and gradient-based techniques have the following problems when leading with non-linearities and complex interactions:
- The convergence to an optimal solution depends on the chosen initial solution
- Most algorithms tend to get stuck to a suboptimal solution.
To understand NSGA-II. It is important to have a fundamental knowledge of genetic algorithms. See the following link https://www.analyticsvidhya.com/blog/2017/07/introduction-to-genetic-algorithm/.
NSGA-II is one evolutionary algorithm that has the following three features:
- It uses an elitist principle , i.e. the elites of a population are given the opportunity to be carried to the next generation.
- Is uses an explicit diversity preserving mechanism (Crowding distance )
- It emphasizes the non-dominated solutions.
It has the following procedure:
- Perform a non-dominated sorting in the combination of parent and offspring populations and classify them by fronts , i.e. they are sorted according to an ascending level of non-domination:
Figure 3 : Minimizing f1, f2. Three front levels. Source: 
- Fill new population according to front raking.
- If one front is taking partially like F3, perform Crowding-sort that uses crowding distance that is related with the density of solutions around each solution. The less dense are preferred
- Create offspring population from this new population using crowded tournament selection (It compares by front ranking, if equal then by crowding distance), crossover and mutation operators.
Figure 4: Schematic of the NSGA-II procedure. Source 
A code using the library “inspyred” will be explained.
- Deb, Kalyanmoy. Multi-objective optimization using evolutionary algorithms. Vol. 16. John Wiley & Sons, 2001.
- Chapter 15. Burke, Edmund K., and Graham Kendall. Search methodologies. Springer Science+ Business Media, Incorporated, 2005.
- Chapter 6. Deb, Kalyanmoy. Multi-objective optimization using evolutionary algorithms. Vol. 16. John Wiley & Sons, 2001.
- Seah, Chun-Wei, Yew-Soon Ong, Ivor W. Tsang, and Siwei Jiang. “Pareto rank learning in multi-objective evolutionary algorithms.” In Evolutionary Computation (CEC), 2012 IEEE Congress on, pp. 1-8. IEEE, 2012.