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

non-dominated sorting crowding distance sorting P t+1

F 1

P t

F 2

F 3

Q t

Rejected

R t

Fig. 3.2 NSGA-II sorting procedure

wider range of candidate solutions (hence the fictitious locality is damped) and its ef-
ficient elitism and selection routines drive the optimization towards the Pareto front.
This algorithm has been implemented in Multicube Explorer while it was provided
by modeFRONTIER from early releases.

3.3.1.2 MOGA-II

MOGA-II (Multi-Objective Genetic Algorithm, with elitism) was originally formu-
lated by Poloni [ 11 ] and it reached the actual implementation with the introduction
of elitism. This second version is equipped also with an optional improved crossover
operator (directional crossover), but since it is not suited for discrete problems, its
description is omitted.
This algorithm accepts only discrete variables (possible continuous variables have
to be discretized with the desired accuracy), which are encoded as in classical genetic
algorithms. Three operators govern the reproduction phase: one-point crossover,
mutation and selection. The probabilities under which one of them is chosen are
user-defined parameters.
Elitism guarantees that the best points remain in the parent population and hence
hopefully their children will exhibit a similar behavior. MOGA-II achieves this result
keeping a record of all non-dominated points found up to the current generation. The
new population is created extracting randomly the requested number of new parents
from the union (without repetitions) of the elite set and the set of newly generated
children. This procedure gives to the algorithm a good balance between exploration
and exploitation phase. This balance is fundamental for the performance of a multi-
objective global search: the search space has to be sufficiently explored, but at the