Skip to content
Tutorials Center
My learning

Topics

Lesson 21 of 36 ยท Constraints and Multi-objective

Multi-objective Optimization and Pareto Dominance

Optimize several goals at once. Learn Pareto dominance, non-dominated sorting and the Pareto front, plus the weighted-sum trap, with runnable Python examples.

Most real decisions have more than one goal. You want a car that is cheap and fast, a neural network that is accurate and small, a delivery route that is short and on time. These goals fight each other. There is rarely one best answer, but there is a set of best trade-offs. Evolutionary algorithms are excellent at finding that whole set in a single run, because a population can hold many answers at once.

This lesson introduces the vocabulary: dominance, the Pareto front, and ranking. The next lesson turns it into a full algorithm.

Why not just add the objectives?

The obvious trick is a weighted sum: score = w1 * cost + w2 * time. It works, but it hides problems:

  • You must pick the weights before you see the trade-offs, and the right weights are usually unknown.
  • A different weight means a new run.
  • A weighted sum cannot find solutions on a non-convex part of the trade-off curve, however you set the weights.

A multi-objective algorithm avoids all three: it returns the whole curve and lets a human choose afterwards.

Dominance

Assume every objective is to be minimized (negate objectives you want to maximize). Solution A dominates solution B when:

  1. A is no worse than B in every objective, and
  2. A is strictly better than B in at least one objective.

Solutions that nobody dominates are non-dominated. The set of all non-dominated solutions is the Pareto set; their objective values form the Pareto front.

flowchart LR
    subgraph obj["Two objectives, both minimized"]
      A["A = (1, 5)"]
      B["B = (3, 3)"]
      C["C = (5, 1)"]
      D["D = (4, 4)"]
    end
    B -- dominates --> D

A, B and C are non-dominated: each beats the others in one objective. D is dominated by B (3 < 4 and 3 < 4).

Python Write the dominance test and find the front

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.

Ranking by fronts: non-dominated sorting

To use dominance in selection you need a rank for every individual. Non-dominated sorting builds layers:

  1. Find all non-dominated individuals. They are front 1 (rank 1).
  2. Remove them. Among the rest, find the non-dominated ones. They are front 2.
  3. Repeat until everyone has a rank.

Selection prefers lower ranks. Individuals in the same front are equally good as far as dominance can tell, so we need a second criterion to break ties, and that criterion should favor spread. That is the topic of crowding distance, below.

Crowding distance: reward diversity

A good approximation of the Pareto front covers the whole curve, not just one corner. Crowding distance measures, for each individual in a front, how much empty space surrounds it in objective space. For each objective:

  1. Sort the front by that objective.
  2. Give the two extreme points an infinite distance (they must be kept).
  3. For every other point, add the normalized difference between its two neighbours.

A big crowding distance means a lonely point, which is valuable for diversity.

Python Non-dominated sorting and crowding distance

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.

Hypervolume: one number for a front

To compare two algorithms you need a single score for a front. The hypervolume is the area (in 2D) or volume dominated by the front and bounded by a reference point that is worse than every solution. Bigger is better, and it rewards both closeness to the true front and good spread. In two objectives it is easy: sort by the first objective and add up rectangles.

Python
def hypervolume_2d(front, ref):
    f = front[np.argsort(front[:, 0])]
    hv, prev_y = 0.0, ref[1]
    for x, y in f:
        hv += (ref[0] - x) * (prev_y - y)
        prev_y = y
    return hv

Common mistakes

  • Mixing minimize and maximize. Convert all objectives to the same direction first.
  • Unscaled objectives. If one objective ranges 0-1 and another 0-10000, crowding distance and hypervolume are dominated by the big one. Normalize.
  • Calling it "the best" solution. There is no single best. Say "a non-dominated solution" and let the decision maker choose.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. With both objectives minimized, does (2, 3) dominate (2, 5)?

    Dominance needs no-worse everywhere and strictly better somewhere. Here the second objective is strictly better.
  2. 2. What is the Pareto front?

    It is the set of non-dominated trade-offs.
  3. 3. Why do extreme points get an infinite crowding distance?

    Keeping the extremes stops the front from shrinking towards the middle.
  4. 4. Which problem can a weighted sum NOT solve, whatever weights you pick?

    Weighted sums only reach the convex hull of the front.

Summary

  • Several goals produce a set of trade-offs rather than one best solution.
  • A dominates B if it is no worse everywhere and strictly better somewhere.
  • Non-dominated sorting ranks the population in layers (fronts).
  • Crowding distance prefers lonely points, preserving diversity along the front.
  • Hypervolume compares fronts with a single number. Normalize objectives first.

Next: NSGA-II from Scratch