NSGA-III in MATLAB

Deb and Jain extended the well-known NSGA-II to handle many-objective optimization problems, where several competing objectives make diversity preservation harder. Their method uses a reference point approach together with a non-dominated sorting mechanism. The new algorithm is called NSGA-III, and it was published in 2014. The main reference paper is available here (opens in a new tab).

Why NSGA-II needs a change

NSGA-II ranks the members of a front by their crowding distance. As the number of objectives grows, a larger share of the population can become non-dominated, weakening selection based on rank and crowding distance. NSGA-III keeps the non-dominated sorting of NSGA-II, but it replaces the crowding distance with a set of reference points. The reference points are spread evenly in objective space, and the algorithm tries to keep solutions close to each of them.

How NSGA-III works

Reference points. The points are placed on the unit simplex (the set of points with non-negative coordinates that sum to 1) with the systematic method of Das and Dennis. With $M$ objectives and $p$ divisions along each objective, every coordinate is a multiple of $1/p$, and the number of points is

Selection. In each generation, the offspring are merged with the parents, and the merged population of size $2N$ is sorted into fronts $F_1, F_2, \dots$ as in NSGA-II. Whole fronts are added to the next population until the next front $F_l$ no longer fits. The members of $F_l$ that fill the remaining places are chosen in three steps:

1. Normalization. The ideal point $z^{\min}$, the best value of each objective found so far, is subtracted from every objective vector. Extreme points are found on each objective axis with an achievement scalarizing function, and the hyperplane through them gives the intercepts $a_i$. The normalized objectives are $\tilde{f}_i(x) = \left(f_i(x) - z_i^{\min}\right) / a_i$.
2. Association. Each reference point $w$ defines a reference line from the origin. Every member is associated with the reference line closest to it, measured by the perpendicular distance $d^{\perp}(x, w) = \left\| \tilde{f}(x) - \frac{w^{\top}\tilde{f}(x)}{\|w\|^2}\, w \right\|$.
3. Niching. The niche count $\rho_j$ is the number of members associated with reference point $j$. The algorithm picks the reference point with the smallest niche count. If no member of $F_l$ is associated with that point, the point is skipped. If no chosen member is associated with it yet, the member of $F_l$ closest to its line is added. Otherwise, a random associated member of $F_l$ is added. This repeats until the population is full.

As a result, the population keeps solutions near as many reference points as possible.

Implementation in MATLAB

This post shares the MATLAB implementation of NSGA-III 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. It is also very similar to the previously published NSGA-II implementation.

The NSGA-III folder holds the main script nsga3.m, a one line entry point main.m, and these functions:

• GenerateReferencePoints.m: the reference points on the simplex.
• SortAndSelectPopulation.m: sorting, normalization, association and niching, as described above.
• NonDominatedSorting.m, NormalizePopulation.m, UpdateIdealPoint.m, PerformScalarizing.m and AssociateToReferencePoint.m: the single steps.
• Crossover.m, Mutate.m, Dominates.m and PlotCosts.m: the same operators and tools as in the NSGA-II code.
• MOP2.m: the default test problem, the Fonseca and Fleming function with two objectives.

To run the code, open the NSGA-III 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. The parents for crossover and mutation are picked at random from the current population. The code uses unifrnd and randsample, 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 nsga3.m:

With the default two objectives and 10 divisions, the code uses 11 reference points. For a problem with many objectives, choose nDivision so that the number of reference points is close to the population size. 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 nsga3.m.

Check the result

The default example has two objectives, so it demonstrates the implementation rather than a many-objective benchmark. When changing the objective count, review the reference-point count, population size, and normalization for degenerate or zero-range objectives. A source review also flagged that the code counts niches over the merged population rather than only the already-selected members. Review that difference before claiming results equivalent to the paper. No optimizer code was executed or changed in this content pass.

Related posts

• NSGA-II in MATLAB explains non-dominated sorting and the crowding distance.
• MOEA/D in MATLAB is another algorithm that uses weight vectors spread over objective space.

Mostapha Kalami Heris, NSGA-III in MATLAB (YPEA126), Yarpiz, 2016. https://yarpiz.com/nsga3-ypea126

@misc{yarpiz-ypea126,
  author = {{Mostapha Kalami Heris}},
  title = {{NSGA-III in MATLAB}},
  howpublished = {Yarpiz},
  year = {2016},
  note = {Code YPEA126},
  url = {https://yarpiz.com/nsga3-ypea126}
}