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

## More definitions

**Domination **

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:

**Non-Dominated set:**

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 [1]*

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 [1]*

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: [4]*

- 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 [1]*

A code using the library “inspyred” will be explained.

**Sources:**

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