NSGA-II in MATLAB

The Non-dominated Sorting Genetic Algorithm II (NSGA-II) is a multi-objective genetic algorithm proposed by Deb, Pratap, Agarwal and Meyarivan in 2002 (paper (opens in a new tab)). It extends and improves NSGA, which Srinivas and Deb proposed in 1994 (paper (opens in a new tab)). NSGA-II is one of the most widely used multi-objective evolutionary algorithms.

The multi-objective problem

A multi-objective problem has several cost functions $f_1, \dots, f_M$ that must be minimized at the same time, usually within bounds on the decision variables $x$:

The objectives usually conflict, so there is no single best solution. Solutions are compared with Pareto dominance. A solution $x$ dominates a solution $y$ when it is no worse in every objective and strictly better in at least one:

The solutions that no other solution dominates form the Pareto set, and their objective vectors form the Pareto front. The aim of NSGA-II is to find a good approximation of this front, with solutions that are close to it and spread well along it.

How NSGA-II works

In addition to the genetic operators (crossover and mutation), NSGA-II uses two specialized multi-objective mechanisms:

• Non-dominated sorting: the population is sorted and partitioned into fronts $F_1$, $F_2$, and so on. $F_1$ holds the members that no other member dominates. When $F_1$ is set aside, the non-dominated members of the rest form $F_2$, and so on. $F_1$, the first front, approximates the Pareto front.
• Crowding distance: a measure that ranks the members within one front. Members of the same front do not dominate each other, so dominance cannot tell them apart. The crowding distance measures how close a member’s neighbors are in objective space, and a member in a less crowded region is preferred.

For a front sorted by objective $m$, the two boundary members get an infinite distance, and every other member $i$ gets

where $f_m^{(i+1)}$ and $f_m^{(i-1)}$ are the values of the two neighbors of member $i$ in that order, and $f_m^{\max}$ and $f_m^{\min}$ are the largest and smallest values of objective $m$ in the front.

In each generation, the algorithm:

1. Creates offspring with crossover and mutation.
2. Merges the parents and the offspring into one population.
3. Sorts the merged population into fronts and computes the crowding distance in each front.
4. Sorts the members by front rank first, and by crowding distance (largest first) within a front.
5. Keeps the first $N$ members as the next population.

Parents remain eligible for the next generation alongside their offspring. This is elitist environmental selection, although a finite population may still discard some non-dominated solutions. In the original paper, the parents are chosen with a binary tournament that uses the same rank and crowding distance order.

Implementation in MATLAB

This post shares the MATLAB implementation of NSGA-II as an open-source project. The algorithm is implemented in a structured way, so if you know MATLAB, you can easily use the code in your research projects.

What is in the download

The NSGA-II folder holds these files:

• nsga2.m: the main script, with the problem definition, the parameters and the main loop.
• main.m: a one line entry point that runs nsga2.m.
• NonDominatedSorting.m, CalcCrowdingDistance.m and SortPopulation.m: the three ranking steps described above.
• Dominates.m: the Pareto dominance test.
• Crossover.m: arithmetic crossover, which mixes two parents with random weights.
• Mutate.m: Gaussian mutation of a few randomly chosen variables.
• MOP2.m and MOP4.m: two test problems with two objectives. The default is MOP4, the Kursawe function.
• PlotCosts.m: plots the members of $F_1$.

To run the code, open the NSGA-II folder in MATLAB and run main.m. In each iteration the program prints the number of members of $F_1$ and plots their objective values.

In this code, the parents for crossover and mutation are picked at random from the current population. The selection pressure comes from the sorting and truncation step at the end of each iteration.

The code uses unifrnd and randsample, two functions of the Statistics and Machine Learning Toolbox, so it probably needs that toolbox.

Parameters in the code

The parameters are set at the top of nsga2.m:

To solve your own problem, write a cost function that takes a row vector and returns a column vector of objective values, and set CostFunction, nVar, VarMin and VarMax in nsga2.m.

Check the result

The first front is non-dominated within the evaluated population, not a proof of the true Pareto front. Inspect objective values, decision-variable bounds, and the spread of solutions across repeated runs. A larger front is not automatically a better approximation. When adapting the crowding-distance calculation, handle an objective whose range is zero so that the normalization does not divide by zero.

Applications

NSGA-II needs only the values of the objectives, not their gradients, so it suits problems where the trade-off between goals matters, for example cost against performance in engineering design, or several conflicting criteria in scheduling and planning.

Related posts

• NSGA-III in MATLAB extends this code to problems with many objectives.
• Multi-Objective PSO in MATLAB, SPEA2 in MATLAB, PESA-II in MATLAB and MOEA/D in MATLAB are other multi-objective algorithms on Yarpiz.

Mostapha Kalami Heris, NSGA-II in MATLAB (YPEA120), Yarpiz, 2015. https://yarpiz.com/nsga2-ypea120

@misc{yarpiz-ypea120,
  author = {{Mostapha Kalami Heris}},
  title = {{NSGA-II in MATLAB}},
  howpublished = {Yarpiz},
  year = {2015},
  note = {Code YPEA120},
  url = {https://yarpiz.com/nsga2-ypea120}
}