Non-dominated Sorting Genetic Algorithm II

NSGA-II is a multi-objective optimization algorithm based on genetic algorithms. It is well-suited for problems with multiple conflicting objectives, where the goal is to find the Pareto front — the set of solutions where no objective can be improved without worsening another.

What is Multi-objective Optimization?

In single-objective optimization, there is one best solution. In multi-objective optimization, there is typically no single "best" solution. Instead, there is a set of trade-off solutions.

A solution A dominates solution B if:

A is at least as good as B in all objectives, and
A is strictly better than B in at least one objective

Solutions that are not dominated by any other solution form the Pareto front.

How NSGA-II Works

STEP1: Initial Population

A population of individuals (sets of variable values) is randomly generated and evaluated.

STEP2: Non-dominated Sorting

The population is sorted into fronts based on dominance:

Front 1: solutions not dominated by any other (the current Pareto front)
Front 2: solutions dominated only by those in Front 1
And so on…

This ranking is called the non-domination rank.

STEP3: Crowding Distance

Within each front, a crowding distance is calculated for each individual. This measures how isolated an individual is from its neighbors in objective space. Individuals with a large crowding distance are preferred, which encourages diversity along the Pareto front.

STEP4: Selection, Crossover, and Mutation

A new generation is created by:

Selection: preferring individuals with a better non-domination rank; among equal ranks, preferring those with greater crowding distance
Crossover: combining two parent solutions to produce offspring
Mutation: randomly perturbing offspring to maintain diversity

Tunny supports several crossover methods: uniform (default), blxalpha, sbx, vsbx, undx, and spx.

STEP5: Elitism

The best individuals from the current and offspring populations are combined and trimmed to maintain the population size. This elitist strategy ensures that good solutions found in previous generations are never discarded.

STEP2 through STEP5 are repeated until the number of trials is reached.

When to Use NSGA-II

You have two or more objective functions
You want a diverse set of trade-off solutions (the full Pareto front)
You do not have a strong prior on the shape of the objective function
You have a sufficient evaluation budget (genetic algorithms generally require more trials than Bayesian methods to converge)

NSGA-II