282
D. Irawan and B. Naujoks
Fig. 8.12 IGD is the inverse
of GD, calculated as distance
from each reference point
(red circle) to the closest
non-dominated points (blue
star)
To measure diversity it is better to use the inverse GD (IGD) [8]: instead of
calculating the average distance of the solutions to its nearest reference point,
we calculate the average distance from all reference points to their closest nondominated point (Fig. 8.12). Similar to GD, a small IGD is desirable. However, this
is a completely different measure because if all non-dominated points converge to a
single reference point, other reference points will have a large minimum distance to
non-dominated point. Hence, the GD would be small, but the IGD will be large.
8.3.3 Algorithms Designed for Multi-Objective Optimization
Problems
Some EAs are actually designed to tackle the problem of finding the Pareto front
of multi-objective problems. These algorithms are called EMOAs (evolutionary
multi-objective optimization algorithms) or MOEAs (multi-objective evolutionary
algorithms).
8.3.3.1 NSGA-II
NSGA-II is the elitist non-dominated sorting genetic algorithm by Deb et al.
[12]. Currently it is well-known and the most frequently used EMOA. In NSGAII, broadly speaking, any recombination and mutation method can be used. The
defining feature of NSGA-II is its selection methods. The primary selection method
is called non-dominated sorting:
1. The non-dominated front is ranked as the first front.
2. Remove the first front; the second front is the non-dominated individuals when
the first front is removed.