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

184
IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, VOL. 6, NO. 2, APRIL 2002
front, the solutions of the first front are discounted temporarily
and the above procedure is repeated. In the worst case, the task
of finding the second front also requires
computa-
tions, particularly when
number of solutions belong to
the second and higher nondominated levels. This argument is
true for finding third and higher levels of nondomination. Thus,
the worst case is when there are
fronts and there exists only
one solution in each front. This requires an overall
computations. Note that
storage is required for this pro-
cedure. In the following paragraph and equation shown at the
bottom of the page, we describe a fast nondominated sorting
approach which will require
computations.
First, for each solution we calculate two entities: 1) domi-
nation count
, the number of solutions which dominate the
solution , and 2)
, a set of solutions that the solution
dom-
inates. This requires
comparisons.
All solutions in the first nondominated front will have their
domination count as zero. Now, for each solution with
,
we visit each member ( ) of its set
and reduce its domina-
tion count by one. In doing so, if for any member
the domi-
nation count becomes zero, we put it in a separate list
. These
members belong to the second nondominated front. Now, the
above procedure is continued with each member of
and the
third front is identified. This process continues until all fronts
are identified.
For each solution
in the second or higher level of nondom-
ination, the domination count
can be at most
. Thus,
each solution
will be visited at most
times before its
domination count becomes zero. At this point, the solution is
assigned a nondomination level and will never be visited again.
Since there are at most
such solutions, the total com-
plexity is
. Thus, the overall complexity of the procedure
is
. Another way to calculate this complexity is to re-
alize that the body of the first inner loop (for each
) is
executed exactly
times as each individual can be the member
of at most one front and the second inner loop (for each
)
can be executed at maximum
times for each individual
[each individual dominates
individuals at maximum and
each domination check requires at most
comparisons] results
in the overall
computations. It is important to note
that although the time complexity has reduced to
, the
storage requirement has increased to
.
B. Diversity Preservation
We mentioned earlier that, along with convergence to the
Pareto-optimal set, it is also desired that an EA maintains a good
spread of solutions in the obtained set of solutions. The original
NSGA used the well-known sharing function approach, which
has been found to maintain sustainable diversity in a popula-
tion with appropriate setting of its associated parameters. The
sharing function method involves a sharing parameter
,
which sets the extent of sharing desired in a problem. This pa-
rameter is related to the distance metric chosen to calculate the
proximity measure between two population members. The pa-
rameter
denotes the largest value of that distance metric
within which any two solutions share each other’s fitness. This
parameter is usually set by the user, although there exist some
guidelines [4]. There are two difficulties with this sharing func-
tion approach.
1) The performance of the sharing function method in
maintaining a spread of solutions depends largely on the
chosen
value.
-
-
-
for each
for each
if
then
If
dominates
Add
to the set of solutions dominated by
else if
then
Increment the domination counter of
if
then
belongs to the first front
Initialize the front counter
while
Used to store the members of the next front
for each
for each
if
then
belongs to the next front

DEB et al.: A FAST AND ELITIST MULTIOBJECTIVE GA: NSGA-II
185
Fig. 1.
Crowding-distance calculation. Points marked in filled circles are
solutions of the same nondominated front.
2) Since each solution must be compared with all other so-
lutions in the population, the overall complexity of the
sharing function approach is
.
In the proposed NSGA-II, we replace the sharing function
approach with a crowded-comparison approach that eliminates
both the above difficulties to some extent. The new approach
does not require any user-defined parameter for maintaining
diversity among population members. Also, the suggested ap-
proach has a better computational complexity. To describe this
approach, we first define a density-estimation metric and then
present the crowded-comparison operator.

tải về 0.7 Mb.

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