A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II

Abstract—Multiobjective evolutionary algorithms (EAs)
that use nondominated sorting and sharing have been criticized
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
results of the constrained NSGA-II on a number of test problems,
including a five-objective seven-constraint nonlinear problem, are
compared with another constrained multiobjective optimizer and
much better performance of NSGA-II is observed.