Optimization Algorithms for Design Space Exploration of Embedded Systems - Multi-objective Design Space Exploration of Multiprocessor SoC Architectures - page 63

3.3.3.1 MFGA

The acronym of this new algorithm stands for Magnifying Front Genetic Algorithm
since its main purpose is to work on the local Pareto front in three directions: to-
wards (approaching the true front), laterally (obtaining a wider front) and internally
(enhancing the uniformity of the front samples).
With the introduction of elitism, genetic algorithms such as NSGA-II found a very
good answer to the problem of converging faster than previous implementations. The
question now is how to converge better, without slowing down.
Elitism is considered as the main reason of too concentrated Pareto fronts [ 1 , 4 ].
If the optimization problem is difficult, only a few points will be non-dominated and
will become a sort of basin of attraction. Indeed, elitist strategies will keep these
points in the parent population and crowding distance or similar techniques are not
useful to “dilute” them until a large number of Pareto points are found. However
without elitism the request for quality cannot even be addressed, since the algorithm
would converge too slowly. Literature reports two promising ideas in order to modify
this operator without removing it.
Deb and Goel [ 4 ] proposed a controlled elitism approach. Their algorithm selects
the new parent population accepting also dominated points with a preference for
those points coming from less crowded regions. Computed points are ranked by
domination and ordered by crowding distance. An exponentially decreasing number
of points are selected from each rank starting from the top of the list. Figure 3.3
shows how a combined population R t of size 2 N (parents plus children) is reduced

Fig. 3.3 Controlled Elitism sorting procedure vs NSGA-II