284
D. Irawan and B. Naujoks
Fig. 8.14 Illustration of the
crowding distance in a 2D
objective space. The light
blue point will be removed
because its distances to the
neighboring points are the
smallest
f 1
f 2
f 1,lower
f 2,upper
f 2,lower
f 1,upper
Algorithm 2 NSGA-II
t = 0
P (t) ← Initial population of size μ
Evaluate P (t)
while Stopping criteria not fulfilled do
while |P (t)| < μ do
P (t) ← variation P (t)
Evaluate P (t)
Non-dominated sorting on P (t)
P (t)
i ← 1
K ← 0
while K < μ do
P (t + 1) ← R i
i ← i + 1
K ← K + |R i |
if K > μ then
Crowding distance selection on P (t + 1)
t = t + 1
SMS-EMOA uses a steady-state selection scheme, meaning that only 1 new
individual is produced from the mating procedure and from the parents and 1
offspring, 1 point is removed. The parents selection for mating is equiprobable. As
the primary selection operator, SMS-EMOA uses non-dominated sorting as used in
NSGA-II. The worst ranked front from non-dominated sorting can still have several
points in it; thus a secondary selection is conducted: the removed point should
have the smallest contribution on the worst-front hypervolume. Figure 8.15 depicts
a front where secondary selection is conducted. The top-left point is the smallest
contributor to the total hypervolume; thus it will be removed from the population.
Note that the contribution of the edge points can be larger or smaller depending on
the reference point location; hence different reference points could lead to different
selections.