I6. Beyond NSGA-II¶
NSGA-II answers the question "which solutions survive?" with dominance ranks and crowding distances. Other algorithms answer it differently, and the answers fall into three families. Knowing them is enough to understand almost every algorithm in VAMOS.
In this lesson you will learn:
- the selection principle of Pareto-based, decomposition-based and indicator-based algorithms;
- how a Tchebycheff scalarization reaches fronts that a weighted sum cannot;
- how SMS-EMOA uses hypervolume contributions;
- which VAMOS algorithms belong to each family.
Pareto-based algorithms¶
Pareto-based algorithms rank solutions by dominance, then break ties with a density estimate. NSGA-II is one; SPEA2 [1] is the other classic:
- every solution receives a strength, the number of solutions it dominates; its raw fitness is the sum of the strengths of the solutions that dominate it (0 for non-dominated solutions);
- density is estimated from the distance to the k-th nearest neighbour, a finer measure than crowding distance;
- an external archive of fixed size keeps the best solutions; when it overflows, the solution with the closest neighbours is removed one at a time.
Pareto-based selection works well with two or three objectives and makes no assumption about the shape of the front. Its weakness appears with more objectives, when nearly every solution is non-dominated (lesson A1).
Decomposition-based algorithms¶
MOEA/D [2] decomposes the problem into N single-objective subproblems, one per weight vector w¹, …, wᴺ, and optimizes them simultaneously. Each subproblem keeps one solution. New solutions are created from neighbouring subproblems, those with the closest weight vectors, and a child replaces a neighbour's solution if it is better for that neighbour's subproblem. Neighbours share information because their optima are close on the front.
The subproblems are scalarizations. The weighted sum fails on non-convex fronts (lesson B1). The Tchebycheff scalarization [3, 4] uses the ideal point z* instead:
Its contour lines are corners, not straight lines, and every Pareto-optimal point minimizes it for some weight vector, whatever the shape of the front. Compare the two methods on the non-convex front: sweep the weights with each method and count the distinct solutions.
Evenly spaced weights do not give evenly spaced solutions: their spacing depends on the shape of the front, and Ishibuchi et al. [5] showed that the performance of decomposition-based algorithms depends strongly on how well the shape of the front matches the distribution of the weights. NSGA-III and RVEA use the same idea of a fixed set of directions with Pareto-based or angle-based selection; lesson A1 explains NSGA-III.
Indicator-based algorithms¶
If the goal is a set with a high hypervolume (lesson B4), why not select for it directly? Indicator-based algorithms do exactly that.
- IBEA [6] defines the fitness of a solution from a binary indicator, usually the additive ε, computed against every other solution, and removes the worst solution one at a time.
- SMS-EMOA [7] is steady-state: each step creates one offspring, sorts the N + 1 solutions into fronts, and removes the solution of the last front with the smallest exclusive hypervolume contribution, the one whose removal loses the least hypervolume.
Drag the points below and watch which one SMS-EMOA would discard:
Indicator-based selection inherits the Pareto compliance of the hypervolume, and it adapts the distribution of points to the front's shape. It also inherits its cost: computing contributions becomes expensive with many objectives [8].
The families in VAMOS¶
| Family | Selection principle | VAMOS algorithms | In-depth lessons |
|---|---|---|---|
| Pareto-based | Dominance rank, then density | NSGA-II, SPEA2 | I1 NSGA-II, I7 SPEA2 |
| Decomposition and reference directions | Scalarized subproblems or directions in objective space | MOEA/D, NSGA-III, RVEA | I8 MOEA/D, A2 NSGA-III, A3 RVEA |
| Indicator-based | Contribution to a quality indicator | SMS-EMOA, IBEA | I9 SMS-EMOA, I10 IBEA |
| Other survival rules | Geometry of the front, particle swarms | AGE-MOEA, SMPSO | A4 AGE-MOEA, I11 SMPSO |
| Constrained problems | Several populations, archives or stages | CCMO, C-TAEA, ToP, CMOEA-MS (lesson A5) | A6 CCMO, A7 C-TAEA, A8 ToP, A9 CMOEA-MS |
Because every algorithm receives the same problem and budget through
optimize, switching family is a one-word change:
from vamos import optimize
for algorithm in ("nsgaii", "moead", "smsemoa"):
result = optimize("zdt1", algorithm=algorithm, pop_size=100, max_evaluations=10_000, engine="numpy", seed=1)
print(f"{algorithm:<8} {result.data['evaluations']} evaluations, {result.F.shape[0]} returned solutions")
Output:
nsgaii 10000 evaluations, 100 returned solutions
moead 10000 evaluations, 100 returned solutions
smsemoa 10000 evaluations, 100 returned solutions
This loop deliberately prints no quality values. One run per algorithm on one problem with default settings says little about which algorithm is better: lesson A10 explains what a comparison needs. Each algorithm's lesson describes its configuration; the capability matrix lists the encodings, constraint handling and engines each one supports.
Key points¶
- Pareto-based algorithms select by dominance, then density (NSGA-II, SPEA2).
- Decomposition-based algorithms solve many scalarized subproblems at once (MOEA/D); the Tchebycheff scalarization reaches non-convex fronts.
- Indicator-based algorithms select for a quality indicator directly (IBEA, SMS-EMOA), at the price of computing it.
- In VAMOS all of them share one interface: changing
algorithm=changes the family.
Next: I7. SPEA2.
References¶
[1] Zitzler, E., Laumanns, M., and Thiele, L. (2001). SPEA2: Improving the strength Pareto evolutionary algorithm. TIK Report 103, Computer Engineering and Networks Laboratory, ETH Zurich.
[2] Zhang, Q., and Li, H. (2007). MOEA/D: A multiobjective evolutionary algorithm based on decomposition. IEEE Transactions on Evolutionary Computation, 11(6), 712–731.
[3] Steuer, R. E., and Choo, E.-U. (1983). An interactive weighted Tchebycheff procedure for multiple objective programming. Mathematical Programming, 26(3), 326–344.
[4] Miettinen, K. (1999). Nonlinear Multiobjective Optimization. Kluwer Academic Publishers.
[5] Ishibuchi, H., Setoguchi, Y., Masuda, H., and Nojima, Y. (2017). Performance of decomposition-based many-objective algorithms strongly depends on Pareto front shapes. IEEE Transactions on Evolutionary Computation, 21(2), 169–190.
[6] Zitzler, E., and Künzli, S. (2004). Indicator-based selection in multiobjective search. Parallel Problem Solving from Nature – PPSN VIII, Lecture Notes in Computer Science 3242, 832–842.
[7] Beume, N., Naujoks, B., and Emmerich, M. (2007). SMS-EMOA: Multiobjective selection based on dominated hypervolume. European Journal of Operational Research, 181(3), 1653–1669.
[8] Bader, J., and Zitzler, E. (2011). HypE: An algorithm for fast hypervolume-based many-objective optimization. Evolutionary Computation, 19(1), 45–76.