A fast and elitist multiobjective genetic algorithm: NSGA-II
Top Cited Papers
- 7 August 2002
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Evolutionary Computation
- Vol. 6 (2) , 182-197
- https://doi.org/10.1109/4235.996017
Abstract
Multi-objective evolutionary algorithms (MOEAs) that use non-dominated sorting and sharing have been criticized mainly for: (1) their O(MN/sup 3/) computational complexity (where M is the number of objectives and N is the population size); (2) their non-elitism approach; and (3) the need to specify a sharing parameter. In this paper, we suggest a non-dominated sorting-based MOEA, called NSGA-II (Non-dominated Sorting Genetic Algorithm II), which alleviates all of the above three difficulties. Specifically, a fast non-dominated sorting approach with O(MN/sup 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 N solutions (with respect to fitness and spread). Simulation results on difficult test problems show that NSGA-II is able, for most problems, to find a much better spread of solutions and better convergence near the true Pareto-optimal front compared to the Pareto-archived evolution strategy and the strength-Pareto evolutionary algorithm - 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 multi-objective 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 multi-objective optimizer, and the much better performance of NSGA-II is observed.Keywords
This publication has 11 references indexed in Scilit:
- The Pareto archived evolution strategy: a new baseline algorithm for Pareto multiobjective optimisationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- A niched Pareto genetic algorithm for multiobjective optimizationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- MULTIOBJECTIVE DESIGN OPTIMIZATION BY AN EVOLUTIONARY ALGORITHMEngineering Optimization, 2001
- An efficient constraint handling method for genetic algorithmsComputer Methods in Applied Mechanics and Engineering, 2000
- Multi-objective Genetic Algorithms: Problem Difficulties and Construction of Test ProblemsEvolutionary Computation, 1999
- Multiobjective optimization and multiple constraint handling with evolutionary algorithms. II. Application exampleIEEE Transactions on Systems, Man, and Cybernetics - Part A: Systems and Humans, 1998
- Multiobjective optimization using evolutionary algorithms — A comparative case studyPublished by Springer Nature ,1998
- Multiobjective optimization and multiple constraint handling with evolutionary algorithms. I. A unified formulationIEEE Transactions on Systems, Man, and Cybernetics - Part A: Systems and Humans, 1998
- On the performance assessment and comparison of stochastic multiobjective optimizersPublished by Springer Nature ,1996
- Muiltiobjective Optimization Using Nondominated Sorting in Genetic AlgorithmsEvolutionary Computation, 1994