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

to a population P t + 1 of size N by selecting n i individuals from each non-dominated
front of size n i , using crowded tournament selection to reduce each front if necessary.
This choice helps in obtaining a more uniform front, filling possible gaps with
points coming from higher ranks. It is remarkable that slight improvements are
achieved also in convergence rate and in lateral spreading of the computed front, as
reported in the cited paper.
Aittokoski and Miettinen [ 1 ] studied a different strategy called variable size popu-
lation. Their idea is to transform all first-rank points into new parents regardless their
number. The result is an algorithm that cannot perform worse than a classical elitist
one considering convergence rate (since it does not waste any useful information)
and it guarantee a better diversity maintenance.
MFGA is an algorithm that tries to manage elitism mixing the two cited ideas in
an original scheme, including also a steady state evolution. The algorithm switches
automatically between the two approaches depending on the dimension of the local
Pareto front, allowing:

￿ wider exploration of the design space: new generations are created by following

the reduced elitism approach until the local Pareto front reaches one third of the
population size (fixed by the DOE size).

￿ better exploitation of the obtained information: the parents update is done by

following the variable size scheme, only for local fronts that contain a number of
points from one to two third of the population size.

￿ diversity preservation: the reduced elitism is reintroduced for larger fronts.

The steady state evolution implemented together with this mixed procedure is quite
demanding from the computational point of view, since every time the evaluation of
a new point is performed, the parent population is completely recomputed including
the new achieved information. This choice is well suited for problems involving long
simulation time.
Classical operators govern the parents-children recombination, but they are re-
built trying to enlarge the kind of problems treatable using them [ 17 ]. Mutation
and crossover operators act in MFGA variable-wise in order to treat easily mixed
problems involving real, integer and categorical variables. MFGA was completely de-
signed by ESTECO for the MULTICUBE project. Its inclusion in future commercial
releases of modeFRONTIER is planned.

3.3.3.2 APRS

The acronym of this new algorithm stands for Adaptive-windows Pareto Random
Search. It is an iterative optimization algorithm that tries to optimize locally each
Pareto solution found up to the previous iteration.
The main characteristics of the algorithm are represented by the three keywords:
adaptive-windows , Pareto and random search .
￿ Adaptive-windows : the APRS is an algorithm that has dynamic windows size

which is reduced with the time spent in the exploration and with the goodness of
the point found in current windows.