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

182
IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, VOL. 6, NO. 2, APRIL 2002
A Fast and Elitist Multiobjective Genetic Algorithm:
NSGA-II
Kalyanmoy Deb, Associate Member, IEEE, Amrit Pratap, Sameer Agarwal, and T. Meyarivan
Abstract—Multiobjective
evolutionary
algorithms
(EAs)
that use nondominated sorting and sharing have been criti-
cized mainly for their: 1)
(
3
) computational complexity
(where
is the number of objectives and
is the population
size); 2) nonelitism approach; and 3) the need for specifying a
sharing parameter. In this paper, we suggest a nondominated
sorting-based multiobjective EA (MOEA), called nondominated
sorting genetic algorithm II (NSGA-II), which alleviates all
the above three difficulties. Specifically, a fast nondominated
sorting approach with
(
2
) computational complexity is
presented. Also, a selection operator is presented that creates a
mating pool by combining the parent and offspring populations
and selecting the best (with respect to fitness and spread)
solutions. Simulation results on difficult test problems show that
the proposed NSGA-II, in most problems, is able to find much
better spread of solutions and better convergence near the true
Pareto-optimal front compared to Pareto-archived evolution
strategy and strength-Pareto EA—two other elitist MOEAs that
pay special attention to creating a diverse Pareto-optimal front.
Moreover, we modify the definition of dominance in order to
solve constrained multiobjective problems efficiently. Simulation