A fast and elitist multiobjective genetic algorithm : NSGA-II

@article{deb02, abstract = {Multi-objective evolutionary algorithms (MOEAs) that use non-dominated sorting and sharing have been criticized mainly for: (1) their O(MN³) 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²) 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.}, author = {Deb, Kalyanmoy D. and Pratap, Amrit and Agarwal, Sameer and Meyarivan, T. }, booktitle = {Evolutionary Computation, IEEE Transactions on}, citeulike-article-id = {2418391}, doi = {http://dx.doi.org/10.1109/4235.996017}, journal = {Evolutionary Computation, IEEE Transactions on}, keywords = {genetique, multiobjectifs, optimisation}, number = {2}, pages = {182--197}, posted-at = {2008-05-20 14:49:17}, priority = {0}, title = {A fast and elitist multiobjective genetic algorithm : NSGA-II}, url = {http://dx.doi.org/10.1109/4235.996017}, volume = {6}, year = {2002} }

TY - JOUR ID - deb02 L3 - citeulike-article-id:2418391 TI - A fast and elitist multiobjective genetic algorithm : NSGA-II T2 - Evolutionary Computation, IEEE Transactions on JF - Evolutionary Computation, IEEE Transactions on VL - 6 IS - 2 SP - 182 EP - 197 N2 - Multi-objective evolutionary algorithms (MOEAs) that use non-dominated sorting and sharing have been criticized mainly for: (1) their O(MN³) 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²) 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. KW - genetique KW - multiobjectifs KW - optimisation AU - Deb, Kalyanmoy AU - Pratap, Amrit AU - Agarwal, Sameer AU - Meyarivan, T PY - 2002/// UR - http://dx.doi.org/10.1109/4235.996017 ER -