A fast and elitist multiobjective genetic algorithm: nsga-ii evolutionary Computation, ieee transactions on

DEB et al.: A FAST AND ELITIST MULTIOBJECTIVE GA: NSGA-II
191
Fig. 11.
Real-coded NSGA-II finds better spread of solutions than SPEA on
ZDT6, but SPEA has a better convergence.
TABLE IV
M
EAN AND
V
ARIANCE OF THE
C
ONVERGENCE AND
D
IVERSITY
M
ETRICS
UP TO
500 G
ENERATIONS
form additional experiments to show the effect of a couple of
different parameter settings on the performance of NSGA-II.
First, we keep all other parameters as before, but increase the
number of maximum generations to 500 (instead of 250 used
before). Table IV shows the convergence and diversity metrics
for problems POL, KUR, ZDT3, ZDT4, and ZDT6. Now, we
achieve a convergence very close to the true Pareto-optimal front
and with a much better distribution. The table shows that in all
these difficult problems, the real-coded NSGA-II has converged
very close to the true optimal front, except in ZDT6, which prob-
ably requires a different parameter setting with NSGA-II. Par-
ticularly, the results on ZDT3 and ZDT4 improve with genera-
tion number.
The problem ZDT4 has a number of local Pareto-optimal
fronts, each corresponding to particular value of
. A large
change in the decision vector is needed to get out of a local
optimum. Unless mutation or crossover operators are capable
of creating solutions in the basin of another better attractor,
the improvement in the convergence toward the true Pareto-op-
timal front is not possible. We use NSGA-II (real-coded) with a
smaller distribution index
for mutation, which has an
effect of creating solutions with more spread than before. Rest
of the parameter settings are identical as before. The conver-
gence metric
and diversity measure
on problem ZDT4 at
the end of 250 generations are as follows:
Fig. 12.
Obtained nondominated solutions with NSGA-II on problem ZDT4.
These results are much better than PAES and SPEA, as shown
in Table II. To demonstrate the convergence and spread of so-
lutions, we plot the nondominated solutions of one of the runs
after 250 generations in Fig. 12. The figure shows that NSGA-II
is able to find solutions on the true Pareto-optimal front with
.
V. R
OTATED
P
ROBLEMS
It has been discussed in an earlier study [3] that interactions
among decision variables can introduce another level of dif-
ficulty to any multiobjective optimization algorithm including
EAs. In this section, we create one such problem and investi-
gate the working of previously three MOEAs on the following
epistatic problem:
minimize
minimize
where
and
for
(2)
An EA works with the decision variable vector , but the above
objective functions are defined in terms of the variable vector ,
which is calculated by transforming the decision variable vector
by a fixed rotation matrix
. This way, the objective functions
are functions of a linear combination of decision variables. In
order to maintain a spread of solutions over the Pareto-optimal
region or even converge to any particular solution requires an
EA to update all decision variables in a particular fashion. With
a generic search operator, such as the variablewise SBX operator
used here, this becomes a difficult task for an EA. However,
here, we are interested in evaluating the overall behavior of three
elitist MOEAs.
We use a population size of 100 and run each algorithm until
500 generations. For SBX, we use
and we use
for mutation. To restrict the Pareto-optimal solutions to lie

192
IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, VOL. 6, NO. 2, APRIL 2002
Fig. 13.
Obtained nondominated solutions with NSGA-II, PAES, and SPEA
on the rotated problem.
within the prescribed variable bounds, we discourage solutions
with
by adding a fixed large penalty to both objec-
tives. Fig. 13 shows the obtained solutions at the end of 500
generations using NSGA-II, PAES, and SPEA. It is observed
that NSGA-II solutions are closer to the true front compared
to solutions obtained by PAES and SPEA. The correlated pa-
rameter updates needed to progress toward the Pareto-optimal
front makes this kind of problems difficult to solve. NSGA-II’s
elite-preserving operator along with the real-coded crossover
and mutation operators is able to find some solutions close to the
Pareto-optimal front [with
resulting
].
This example problem demonstrates that one of the known dif-
ficulties (the linkage problem [11], [12]) of single-objective op-
timization algorithm can also cause difficulties in a multiobjec-
tive problem. However, more systematic studies are needed to
amply address the linkage issue in multiobjective optimization.
VI. C
ONSTRAINT
H
ANDLING
In the past, the first author and his students implemented a
penalty-parameterless constraint-handling approach for single-
objective optimization. Those studies [2], [6] have shown how
a tournament selection based algorithm can be used to handle
constraints in a population approach much better than a number
of other existing constraint-handling approaches. A similar ap-
proach can be introduced with the above NSGA-II for solving
constrained multiobjective optimization problems.

tải về 0.7 Mb.

Chia sẻ với bạn bè của bạn: