8 An Introduction to Many-Objective Evolutionary Optimization
285
Fig. 8.15 Illustration of
SMS-EMOA selection
procedure in a 2D objective
space. Each box is the
contribution of a single point
to the total hypervolume
f 1
f 2
Smallest contribution
Reference
Algorithm 3 SMS-EMOA
t = 0
P (t) ← Initial population of size μ
Evaluate P (t)
while Stopping criteria not fulfilled do
while |P (t)| < 1 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
Smallest contributor removal from P (t + 1)
t = t + 1
The hypervolume contribution of a point x is defined as the hypervolume loss
when x is removed from the non-dominated set. The simplest method to measure
it is by comparing the hypervolume size before and after removing the point. With
μ + 1 number of points, μ + 2 hypervolume calculation must be conducted (once
for the whole non-dominated set and μ + 1 times for removal of each point) using
this algorithm. The runtime of a generation of SMS-EMOA is O(μ
d
2 +1 ) [43]; the d
also is the exponential factor for the runtime.
The algorithm is shown in Algorithm 3 [19]. Again, it follows the base algorithm.
It is even similar to NSGA-II, with changes on the size of P (t), which is only one
in SMS-EMOA, and on the secondary selection.