NSGA-II explained!

By | October 24, 2017

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:

\text{ minimize/maximize: } f_m(\textbf x), m = 1,2,\ldots , M
\text{Subject to: } g_j(\textbf x) \geq 0 ,j = 1,2, \ldots , J
h_k(\textbf x) = 0, k=1,2, \ldots , K
x_i^{(L)} \leq x_i \leq x_i^{(U)} ,i=1,2,\ldots , n

A solution is a vector of n decision variables :

\textbf{x}  =  (  x_1 , x_2 ,  \ldots ,  x_n )^T
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:
x^{(1)} \preceq x^{(2)}

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:

  1. It uses an elitist principle , i.e. the elites of a population are given the opportunity to be carried to the next generation.
  2. Is uses an explicit diversity preserving mechanism (Crowding distance )
  3. It emphasizes the non-dominated solutions.

It has the following procedure:

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

  1. Fill new population according to front raking.
  2. 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
  3. 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:

  1. Deb, Kalyanmoy. Multi-objective optimization using evolutionary algorithms. Vol. 16. John Wiley & Sons, 2001.
  2. Chapter 15. Burke, Edmund K., and Graham Kendall. Search methodologies. Springer Science+ Business Media, Incorporated, 2005.
  3. Chapter 6. Deb, Kalyanmoy. Multi-objective optimization using evolutionary algorithms. Vol. 16. John Wiley & Sons, 2001.
  4. 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.