Hardware Reference
In-Depth Information
A point is said to be
feasible
, if it satisfies all the constraints addressed in
g
and
h
. If the number of objectives is
M
, then given two feasible points
x
and
y
, the point
x
is said to
dominate
y
if
f
i
(
x
)
≤
f
i
(
y
) for
i
=
1,
...
,
M
and there exists at least one
index
j
∈
[1,
M
] such that
f
i
(
x
)
<
f
i
(
y
). Dominance induces a partial ordering onto
the design and the objective space.
A vector of input parameters
x
is said to be a
Pareto design
if there is not any
other point dominating it. The corresponding point in the objective space
f
(
¯
x
) is said
to be a
Pareto point
. The set containing all the Pareto points is the
Pareto front
and
it is the solution of problem
3.1
.
¯
3.3
Algorithms
This section presents a brief description of the multi-objective optimization algo-
rithms that have been tested within the project and implemented in the Design
Space Exploration tools, highlighting the algorithm characteristics that are related to
the specific properties of the optimization of an embedded system. The algorithms
presented in this section can be divided in three groups:
Standard algorithms. This first group includes the algorithms that are well known
in the multi-objective optimization field and have been implemented in the De-
sign Space Exploration tools by following the models proposed by their original
designers with none or minimal enhancements. The algorithms NSGA-II and
MOGA-II belong to this group.
Enhanced algorithms. This group includes all algorithms that are based on a
previously defined algorithm but include noticeable enhancements that make them
adequate for the specific problems addressed. The algorithms Enhanced-MOSA,
Enhanced-ES and Enhanced-MOPSO belong to this group.
New algorithms. This group includes all algorithms that have been specifically
defined in the MULTICUBE project for multi-objective optimization in the context
of System-on-Chip (SoC) design optimization. The algorithms MFGA and APRS
belong to this group.
3.3.1
Standard Algorithms
The algorithms described in this section have been employed successfully in multi-
objective optimization for years. They were not precisely designed for categorical
variables, but they can treat them as simply discrete ones without excessively
deteriorating their performances.
3.3.1.1
NSGA-II
The Non-dominated Sorting Genetic Algorithm II (NSGA-II) was developed by
Prof. Deb et al. [
3
] at Kanpur Genetic Algorithms Laboratory (KanGAL). NSGA-II
Search WWH ::
Custom Search