Hypervolume

In article The Measure of Pareto Optima. Applications to Multi-objective Metaheuristics, Evolutionary Multi-Criterion Optimization, Fleischer proved that, given a finite search space and a reference point, maximisation of the hypervolume measure is equivalent to finding the Pareto set.

Use hypervolume metric in EMO:

Bad

The absolute value depends on the choice of the reference.

Good

  • The ranking of the solution is invariant to linear scaling of the objective functions.

  • The reference point only influences the relative contribution of the boundary points.

Algorithm

Steady-state algorithm

  1. Fast Non-dominated sorting is used as ranking criterion(Borrow from NSGA II).
  2. Hypervolume is applied as selection criterion to discard an individual which contributes the least hypervolume to the worst-ranked front. Only one individual is generated and one is discarded in each generation to minimize the computation cost of hypervolume.

Improved Reduce Algorithm

When there are more than one front, use criterion in NSGA II to select individual. Otherwise use hypervolume

Reference

[1] M. Fleischer, The Measure of Pareto Optima. Applications to Multi-objective Metaheuristics, Evolutionary Multi-Criterion Optimization (EMO 2003), LNCS, vol. 2632, Springer, Berlin, 2003, pp. 519–533.

[2] Nicola Beume, SMS-EMOA: Multiobjective selection based on dominated hypervolume