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

194
IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, VOL. 6, NO. 2, APRIL 2002
Fig. 14.
Obtained nondominated solutions with NSGA-II on the constrained
problem CONSTR.
Fig. 15.
Obtained nondominated solutions with Ray-Tai-Seow’s algorithm on
the constrained problem CONSTR.
can be maintained for a large number of generations. However,
in each case, we obtain a reasonably good spread of solutions as
early as 200 generations. Crossover and mutation probabilities
are the same as before.
Fig. 14 shows the obtained set of 100 nondominated solu-
tions after 500 generations using NSGA-II. The figure shows
that NSGA-II is able to uniformly maintain solutions in both
Pareto-optimal region. It is important to note that in order to
maintain a spread of solutions on the constraint boundary, the
solutions must have to be modified in a particular manner dic-
tated by the constraint function. This becomes a difficult task of
any search operator. Fig. 15 shows the obtained solutions using
Ray-Tai-Seow’s algorithm after 500 generations. It is clear that
NSGA-II performs better than Ray–Tai–Seow’s algorithm in
terms of converging to the true Pareto-optimal front and also
in terms of maintaining a diverse population of nondominated
solutions.
Next, we consider the test problem SRN. Fig. 16 shows the
nondominated solutions after 500 generations using NSGA-II.
Fig. 16.
Obtained nondominated solutions with NSGA-II on the constrained
problem SRN.
Fig. 17.
Obtained nondominated solutions with Ray–Tai–Seow’s algorithm on
the constrained problem SRN.
The figure shows how NSGA-II can bring a random population
on the Pareto-optimal front. Ray–Tai–Seow’s algorithm is also
able to come close to the front on this test problem (Fig. 17).
Figs. 18 and 19 show the feasible objective space and
the obtained nondominated solutions with NSGA-II and
Ray–Tai–Seow’s algorithm. Here, the Pareto-optimal region
is discontinuous and NSGA-II does not have any difficulty in
finding a wide spread of solutions over the true Pareto-optimal
region. Although Ray–Tai–Seow’s algorithm found a number
of solutions on the Pareto-optimal front, there exist many
infeasible solutions even after 500 generations. In order to
demonstrate the working of Fonseca–Fleming’s constraint-han-
dling strategy, we implement it with NSGA-II and apply on
TNK. Fig. 20 shows 100 population members at the end of
500 generations and with identical parameter setting as used in
Fig. 18. Both these figures demonstrate that the proposed and
Fonseca–Fleming’s constraint-handling strategies work well
with NSGA-II.

DEB et al.: A FAST AND ELITIST MULTIOBJECTIVE GA: NSGA-II
195
Fig. 18.
Obtained nondominated solutions with NSGA-II on the constrained
problem TNK.
Fig. 19.
Obtained nondominated solutions with Ray–Tai–Seow’s algorithm on
the constrained problem TNK.
Ray et al. [17] have used the problem WATER in their
study. They normalized the objective functions in the following
manner:
Since there are five objective functions in the problem WATER,
we observe the range of the normalized objective function
values of the obtained nondominated solutions. Table VI shows
the comparison with Ray–Tai–Seow’s algorithm. In most
objective functions, NSGA-II has found a better spread of
solutions than Ray–Tai–Seow’s approach. In order to show the
pairwise interactions among these five normalized objective
functions, we plot all
or ten interactions in Fig. 21 for both
algorithms. NSGA-II results are shown in the upper diagonal
portion of the figure and the Ray–Tai–Seow’s results are shown
in the lower diagonal portion. The axes of any plot can be
obtained by looking at the corresponding diagonal boxes and
their ranges. For example, the plot at the first row and third
column has its vertical axis as
and horizontal axis as
.
Since this plot belongs in the upper side of the diagonal, this
Fig.
20.
Obtained
nondominated
solutions
with
Fonseca–Fleming’s
constraint-handling strategy with NSGA-II on the constrained problem TNK.
plot is obtained using NSGA-II. In order to compare this plot
with a similar plot using Ray–Tai–Seow’s approach, we look
for the plot in the third row and first column. For this figure, the
vertical axis is plotted as
and the horizontal axis is plotted
as
. To get a better comparison between these two plots, we
observe Ray–Tai–Seow’s plot as it is, but turn the page 90 in
the clockwise direction for NSGA-II results. This would make
the labeling and ranges of the axes same in both cases.
We observe that NSGA-II plots have better formed patterns
than in Ray–Tai–Seow’s plots. For example, figures
-
,
-
, and
-
interactions are very clear from NSGA-II
results. Although similar patterns exist in the results obtained
using Ray–Tai–Seow’s algorithm, the convergence to the true
fronts is not adequate.
VII. C
ONCLUSION
We have proposed a computationally fast and elitist MOEA
based on a nondominated sorting approach. On nine different
difficult test problems borrowed from the literature, the pro-
posed NSGA-II was able to maintain a better spread of solu-
tions and converge better in the obtained nondominated front
compared to two other elitist MOEAs—PAES and SPEA. How-
ever, one problem, PAES, was able to converge closer to the true
Pareto-optimal front. PAES maintains diversity among solutions
by controlling crowding of solutions in a deterministic and pre-
specified number of equal-sized cells in the search space. In
that problem, it is suspected that such a deterministic crowding
coupled with the effect of mutation-based approach has been
beneficial in converging near the true front compared to the dy-
namic and parameterless crowding approach used in NSGA-II
and SPEA. However, the diversity preserving mechanism used
in NSGA-II is found to be the best among the three approaches
studied here.
On a problem having strong parameter interactions, NSGA-II
has been able to come closer to the true front than the other
two approaches, but the important matter is that all three
approaches faced difficulties in solving this so-called highly
epistatic problem. Although this has been a matter of ongoing

196
IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, VOL. 6, NO. 2, APRIL 2002
TABLE VI
L
OWER AND
U
PPER
B
OUNDS OF THE
O
BJECTIVE
F
UNCTION
V
ALUES
O
BSERVED IN THE
O
BTAINED
N
ONDOMINATED
S
OLUTIONS
Fig. 21.
Upper diagonal plots are for NSGA-II and lower diagonal plots are for Ray–Tai–Seow’s algorithm. Compare
(i; j) plot (Ray–Tai–Seow’s algorithm
with
i > j) with (j; i) plot (NSGA-II). Label and ranges used for each axis are shown in the diagonal boxes.
research in single-objective EA studies, this paper shows
that highly epistatic problems may also cause difficulties to
MOEAs. More importantly, researchers in the field should
consider such epistatic problems for testing a newly developed
algorithm for multiobjective optimization.
We have also proposed a simple extension to the definition
of dominance for constrained multiobjective optimization. Al-
though this new definition can be used with any other MOEAs,
the real-coded NSGA-II with this definition has been shown
to solve four different problems much better than another re-
cently-proposed constraint-handling approach.
With the properties of a fast nondominated sorting procedure,
an elitist strategy, a parameterless approach and a simple yet
efficient constraint-handling method, NSGA-II, should find in-
creasing attention and applications in the near future.
R
EFERENCES
[1] K. Deb, Multiobjective Optimization Using Evolutionary Algo-
rithms.
Chichester, U.K.: Wiley, 2001.
[2]
, “An efficient constraint-handling method for genetic algorithms,”

tải về 0.7 Mb.

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