Hardware Reference
In-Depth Information
is a fast and elitist multi-objective evolutionary algorithm which shares the basic
structure with all genetic population-based algorithms.
The basic mechanism can be summarized as follows: starting from a parent popu-
lation, some individuals are selected for generating a child population. The algorithm
applies operators that work on the input variables of the selected individuals trying to
improve their outputs: mutation and crossover are the standard choices for NSGA-II.
This procedure is iterated for the requested number of generations.
This algorithm has some peculiar and powerful characteristics:
It includes a fast non-dominated sorting procedure. Sorting the individuals of
a given population according to the level of non-domination is a complex task,
which makes in general non-dominated sorting algorithms computationally ex-
pensive for large population sizes. The adopted solution in NSGA-II performs a
clever sorting strategy.
The multi-objective search includes elitism. NSGA-II implements the multi-
objective search using an elitism-preserving approach, which is introduced storing
all non-dominated solutions discovered so far, beginning from the initial popula-
tion. Elitism enhances the convergence properties towards the true Pareto-optimal
set.
A parameter-less diversity preservation mechanism is adopted. Diversity and
spread of solutions is guaranteed without the use of extra parameters (like sharing
parameters for example). NSGA-II adopts a suitable parameter-less niching ap-
proach called crowding distance, which estimates the density of solutions in the
objective space, and a crowded comparison operator, which guides the selection
process towards a uniformly spread Pareto frontier.
The constraint handling method does not make use of penalty parameters. The
algorithm implements a modified definition of dominance in order to solve con-
strained multi-objective problems efficiently: usual dominance is the criterion to
sort feasible points. A feasible point will be always preferred to an unfeasible
one. Unfeasible points are sorted looking at the (normalized, possibly) constraint
violations sum.
The NSGA-II procedure is described graphically in Fig.
3.2
. The individuals of the
parent population
P
t
of size
N
and the new population
Q
t
of the same size (created
by applying the variation operators crossover and mutation, to individuals in
P
t
selected by binary tournament) are grouped together. The combined population
R
t
is then sorted based on its non-domination level obtaining sets of non-dominated
solutions (
F
1
,
F
2
,
...
). The new population
P
t
+
1
is created by selecting the best
non-dominated sets that can be completely inserted into the new population (with
a combined size smaller or equal than
N
) plus members from the last set (which
cannot be fully accommodated) selected using the crowded comparison operator.
NSGA-II allows both continuous (real-coded) and discrete (binary-coded) de-
sign variables. Specific mutation and crossover operators are applied to each kind of
variables. Categorical (non-ordered discrete) parameters are treated as simple dis-
crete ones. This drawback can be compensated by increasing the exploration
capabilities of the algorithm allowing a larger mutation probability. NSGA-II tests a
Search WWH ::
Custom Search