A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGA-II

Deb, Kalyanmoy ; Agrawal, Samir ; Pratap, Amrit ; Meyarivan, T. (2000) A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGA-II Lecture Notes in Computer Science, 1917/2 . pp. 849-858. ISSN 0302-9743

[img]
Preview
PDF - Author Version
125kB

Official URL: http://www.springerlink.com/index/181751v0v1125574...

Related URL: http://dx.doi.org/10.1007/3-540-45356-3_83

Abstract

Multi-objective evolutionary algorithms which use non-dominated sorting and sharing have been mainly criticized for their (i) O(MN3) computational complexity (where M is the number of objectives and N is the population size), (ii) non-elitism approach, and (iii) the need for specifying a sharing parameter. In this paper, we suggest a non-dominated sorting based multi-objective evolutionary algorithm (we called it the Non-dominated Sorting GA-II or NSGA-II) which alleviates all the above three difficulties. Specifically, a fast non-dominated sorting approach with O(MN2) computational complexity is presented. Second, a selection operator is presented which creates a mating pool by combining the parent and child populations and selecting the best (with respect to fitness and spread) N solutions. Simulation results on five 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 PAES and SPEA-two other elitist multi-objective EAs which pay special attention towards creating a diverse Pareto-optimal front. Because of NSGA-II's low computational requirements, elitist approach, and parameter-less sharing approach, NSGA-II should find increasing applications in the years to come.

Item Type:Article
Source:Copyright of this article belongs to Springer.
ID Code:83498
Deposited On:21 Feb 2012 07:09
Last Modified:19 May 2016 00:19

Repository Staff Only: item control page