8 An Introduction to Many-Objective Evolutionary Optimization
283
Fig. 8.13 Illustration of
non-dominated sorting in a
2D objective space. The stars,
pentagons, and circles are
members of the first, second,
and third fronts, respectively
3. Remove the first and second front; the third front is the non-dominated individuals when the first and second front are removed.
4. Continue removing and ranking until all points are ranked.
The ranking goes on until all individuals assigned a rank. An example is shown in
Fig. 8.13.
Starting from a population/parent P with size μ, a set of offspring P with
same size μ is created. Non-dominated sorting is then applied to the combined
P
P . After assigning ranks, individuals that will be used on the next generation
are selected. The member of each ranked front is counted, and these counts are
summed from the first front to lower ranks until it is equal or exceeds μ, and we
call the final sum result as K. All other fronts will not be used as parents for the
next generations; hence, they are discarded. If the sum of the counts K is equal to
μ, no further selection is required, and we have the parents for the next generation.
However, if K is larger than μ, i.e., we still have too many population member, a
further, secondary selection is conducted.
NSGA-II uses a secondary selection called crowding distance. The crowding
distance is calculated as the sum of distances to the next higher and lower values
in each dimension (Fig. 8.14). The individuals with the smallest distances to its
neighbors will be removed. The overall runtime for NSGA-II is O(μ log
d−1 μ) per
generation [43]; we can see that the number of dimension d causes an exponential
increase for the runtime.
As a summary, the NSGA-II algorithm is shown in Algorithm 2. Notice that the
NSGA-II algorithm follows the base algorithm shown in Sect. 8.2, only expanding
the selection procedure right after P (t) is evaluated. R i in the algorithm are the
individuals with non-dominated sorting rank i.
8.3.3.2 SMS-EMOA
SMS-EMOA stands for S-metric selection EMOA by Emmerich et al. [19]; the
goal is to maximize the S-metric value of the population. S-metric is simply the
hypervolume.
283
Fig. 8.13 Illustration of
non-dominated sorting in a
2D objective space. The stars,
pentagons, and circles are
members of the first, second,
and third fronts, respectively
3. Remove the first and second front; the third front is the non-dominated individuals when the first and second front are removed.
4. Continue removing and ranking until all points are ranked.
The ranking goes on until all individuals assigned a rank. An example is shown in
Fig. 8.13.
Starting from a population/parent P with size μ, a set of offspring P with
same size μ is created. Non-dominated sorting is then applied to the combined
P
P . After assigning ranks, individuals that will be used on the next generation
are selected. The member of each ranked front is counted, and these counts are
summed from the first front to lower ranks until it is equal or exceeds μ, and we
call the final sum result as K. All other fronts will not be used as parents for the
next generations; hence, they are discarded. If the sum of the counts K is equal to
μ, no further selection is required, and we have the parents for the next generation.
However, if K is larger than μ, i.e., we still have too many population member, a
further, secondary selection is conducted.
NSGA-II uses a secondary selection called crowding distance. The crowding
distance is calculated as the sum of distances to the next higher and lower values
in each dimension (Fig. 8.14). The individuals with the smallest distances to its
neighbors will be removed. The overall runtime for NSGA-II is O(μ log
d−1 μ) per
generation [43]; we can see that the number of dimension d causes an exponential
increase for the runtime.
As a summary, the NSGA-II algorithm is shown in Algorithm 2. Notice that the
NSGA-II algorithm follows the base algorithm shown in Sect. 8.2, only expanding
the selection procedure right after P (t) is evaluated. R i in the algorithm are the
individuals with non-dominated sorting rank i.
8.3.3.2 SMS-EMOA
SMS-EMOA stands for S-metric selection EMOA by Emmerich et al. [19]; the
goal is to maximize the S-metric value of the population. S-metric is simply the
hypervolume.