Skip to content
Tutorials Center
My learning

Topics

Lesson 22 of 36 ยท Constraints and Multi-objective

NSGA-II from Scratch

Build NSGA-II, the classic multi-objective genetic algorithm, in under 80 lines of Python. Covers ranking, crowding tournaments, elitism and the ZDT1 benchmark.

NSGA-II (Non-dominated Sorting Genetic Algorithm II) is the workhorse of multi-objective evolutionary optimization. It is popular because it is simple, fast enough and surprisingly hard to beat. It combines the ideas from the previous lesson: rank by Pareto front, break ties by crowding distance. In this lesson you will build it yourself and test it on a standard benchmark.

The algorithm in one picture

Each generation does the following:

  1. Create N children from the N parents using binary tournament selection, crossover and mutation. The tournament compares two random individuals: the lower rank wins; with equal ranks, the larger crowding distance wins.
  2. Merge parents and children into a pool of 2N. This gives elitism for free: no good parent is lost.
  3. Sort the pool into fronts.
  4. Fill the next generation front by front. If the last front does not fit completely, take its individuals with the largest crowding distance.
flowchart TD
    P["Parents P (N)"] --> V["Tournament + crossover + mutation"]
    V --> Q["Children Q (N)"]
    P --> M["Merge: R = P + Q (2N)"]
    Q --> M
    M --> S["Non-dominated sorting into fronts"]
    S --> F["Fill new P front by front"]
    F --> C["Last front: keep largest crowding distance"]
    C --> P2["New parents (N)"]

Elitism comes from merging parents and children before truncating.

The benchmark: ZDT1

We need a problem where the true Pareto front is known. ZDT1 has n real (we use n = 10; the classic benchmark uses 30) variables in [0, 1] and two objectives to minimize:

TEXT
f1(x) = x1
g(x)  = 1 + 9 * mean(x2 ... xn)
f2(x) = g(x) * (1 - sqrt(f1 / g))

The true front is where g = 1, i.e. all other variables are 0: f2 = 1 - sqrt(f1) for f1 in [0, 1]. This is a nice convex curve.

Operators for real numbers

The original NSGA-II uses simulated binary crossover (SBX) and polynomial mutation. Both keep children close to parents, with a tunable "distribution index" eta: a bigger eta means children stay closer. We use them here in a compact form.

Python NSGA-II on ZDT1

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The gap to the true front should be small, and the points should be spread from near f1 = 0 to near f1 = 1, thanks to crowding distance. Try GENS = 20 and compare: the front is further from the curve and less evenly spread.

Reading the code

  • fast_sort builds a dominance matrix once with NumPy broadcasting instead of nested loops, then peels off fronts by counting how many dominators remain.
  • crowding works per front, and per objective sorts the front and sums the normalized neighbour gaps.
  • np.lexsort((-pd, pr)) sorts primarily by rank (the last key) and secondarily by negative crowding distance, which puts the loneliest points first inside each front.
  • Truncation keeps the first POP entries, which is exactly "fill front by front, break the last front by crowding".

Constraints in NSGA-II

NSGA-II has a neat way to handle constraints, called constrained domination. A feasible solution always dominates an infeasible one; two infeasible solutions are compared by their total violation (smaller wins); two feasible solutions use normal dominance. No penalty coefficient is needed. To add it, replace dominates with these three rules.

Limitations and alternatives

NSGA-II works well for two or three objectives. With many objectives (4 and more), almost every individual becomes non-dominated and the ranking stops giving pressure. Alternatives such as NSGA-III (reference directions), MOEA/D (decomposes the problem into many single-objective ones) and SPEA2 (an archive and strength values) handle those cases better.

Common mistakes

  • Forgetting the merge step. Truncating only children throws away good parents.
  • Not normalizing objectives before crowding distance: the objective with the biggest range will dominate.
  • Using a tiny population. The front can only be as dense as the population is large.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. How does NSGA-II achieve elitism?

    Because parents compete with children, a good parent is only lost if enough better individuals exist.
  2. 2. In NSGA-II's binary tournament, two individuals have the same rank. Who wins?

    Preferring lonely points keeps the front spread out.
  3. 3. What is the true Pareto front of ZDT1?

    When g = 1 (all x2..xn equal 0), f2 = 1 - sqrt(f1).
  4. 4. Why does NSGA-II struggle with many (e.g. 8) objectives?

    As the number of objectives grows, dominance becomes rare.

Summary

  • NSGA-II ranks by non-dominated front and breaks ties with crowding distance.
  • Merging parents and children and then truncating gives elitism.
  • SBX and polynomial mutation are the standard real-valued operators.
  • ZDT1 has a known front, so you can measure how close you got.
  • For constraints use constrained domination; for many objectives look at NSGA-III or MOEA/D.

Next: Particle Swarm Optimization