A fast and elitist multiobjective genetic algorithm: …

1 182 IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, VOL. 6, NO. 2, APRIL 2002A Fast and elitist multiobjective genetic algorithm :NSGA-IIKalyanmoy Deb, Associate Member, IEEE, Amrit Pratap, Sameer Agarwal, and T. MeyarivanAbstract multiobjective evolutionary algorithms (EAs)that use nondominated sorting and sharing have been criti-cized mainly for their: 1)(3)computational complexity(whereis the number of objectives andis the populationsize); 2) nonelitism approach; and 3) the need for specifying asharing parameter. In this paper, we suggest a nondominatedsorting-based multiobjective EA (MOEA), called nondominatedsorting genetic algorithm II (NSGA-II), which alleviates allthe above three difficulties.

2 Specifically, a fast nondominatedsorting approach with(2)computational complexity ispresented. Also, a selection operator is presented that creates amating pool by combining the parent and offspring populationsand selecting the best (with respect to fitness and spread)solutions. Simulation results on difficult test problems show thatthe proposed NSGA-II, in most problems, is able to find muchbetter spread of solutions and better convergence near the truePareto-optimal front compared to Pareto-archived evolutionstrategy and strength-Pareto EA two other elitist MOEAs thatpay special attention to creating a diverse Pareto-optimal , we modify the definition of dominance in order tosolve constrained multiobjective problems efficiently.

3 Simulationresults of the constrained NSGA-II on a number of test problems,including a five-objective seven-constraint nonlinear problem, arecompared with another constrained multiobjective optimizer andmuch better performance of NSGA-II is Terms Constraint handling, elitism, genetic algorithms,multicriterion decision making, multiobjective optimization,Pareto-optimal INTRODUCTIONTHE PRESENCE of multiple objectives in a problem, inprinciple, gives rise to a set of optimal solutions (largelyknown as Pareto-optimal solutions), instead of a single optimalsolution. In the absence of any further information, one of thesePareto-optimal solutions cannot be said to be better than theother.

4 This demands a user to find as many Pareto-optimal solu-tions as possible. Classical optimization methods (including themulticriterion decision-making methods) suggest converting themultiobjective optimization problem to a single-objective opti-mization problem by emphasizing one particular Pareto-optimalsolution at a time. When such a method is to be used for findingmultiple solutions, it has to be applied many times, hopefullyfinding a different solution at each simulation the past decade, a number of multiobjective evolu-tionary algorithms (MOEAs) have been suggested [1], [7], [13],Manuscript received August 18, 2000; revised February 5, 2001 andSeptember 7, 2001.

5 The work of K. Deb was supported by the Ministryof Human Resources and Development, India, under the Research andDevelopment authors are with the Kanpur genetic Algorithms Laboratory, Indian In-stitute of Technology, Kanpur PIN 208 016, India (e-mail: Item Identifier S 1089-778X(02)04101-2.[20], [26]. The primary reason for this is their ability to findmultiple Pareto-optimal solutions in one single simulation evolutionary algorithms (EAs) work with a population ofsolutions, a simple EA can be extended to maintain a diverseset of solutions. With an emphasis for moving toward the truePareto-optimal region, an EA can be used to find multiplePareto-optimal solutions in one single simulation nondominated sorting genetic algorithm (NSGA) pro-posed in [20] was one of the first such EAs.)

6 Over the years, themain criticisms of the NSGA approach have been as )High computational complexity of nondominated sorting:The currently-used nondominated sorting algorithm has acomputational complexity of(whereis thenumber of objectives andis the population size). Thismakes NSGA computationally expensive for large popu-lation sizes. This large complexity arises because of thecomplexity involved in the nondominated sorting proce-dure in every )Lack of elitism:Recent results [25], [18] show that elitismcan speed up the performance of the GA significantly,which also can help preventing the loss of good solutionsonce they are )Need for specifying the sharing parameter:Tradi-tional mechanisms of ensuring diversity in a population soas to get a wide variety of equivalent solutions have reliedmostly on the concept of sharing.

7 The main problem withsharing is that it requires the specification of a sharingparameter (). Though there has been some work ondynamic sizing of the sharing parameter [10], a param-eter-less diversity-preservation mechanism is this paper, we address all of these issues and propose animproved version of NSGA, which we call NSGA-II. From thesimulation results on a number of difficult test problems, we findthat NSGA-II outperforms two other contemporary MOEAs:Pareto-archived evolution strategy (PAES) [14] and strength-Pareto EA (SPEA) [24] in terms of finding a diverse set of so-lutions and in converging near the true Pareto-optimal multiobjective optimization is important from thepoint of view of practical problem solving, but not much attentionhas been paid so far in this respect among the EA this paper, we suggest a simple constraint-handling strategywith NSGA-II that suits well for any EA.

8 On four problemschosen from the literature, NSGA-II has been compared withanother recently suggested constraint-handling strategy. Theseresults encourage the application of NSGA-II to more complexand real-world multiobjective optimization the remainder of the paper, we briefly mention a number ofexisting elitist MOEAs in Section II. Thereafter, in Section III,1089-778X/02$ 2002 IEEEDEBet al.: A FAST AND elitist multiobjective GA: NSGA-II183we describe the proposed NSGA-II algorithm in details. Sec-tion IV presents simulation results of NSGA-II and comparesthem with two other elitist MOEAs (PAES and SPEA). In Sec-tion V, we highlight the issue of parameter interactions, a matterthat is important in evolutionary computation research.

9 The nextsection extends NSGA-II for handling constraints and comparesthe results with another recently proposed constraint-handlingmethod. Finally, we outline the conclusions of this ELITISTMULTIOBJECTIVEEVOLUTIONARYALGORIT HMSD uring 1993 1995, a number of different EAs were sug-gested to solve multiobjective optimization problems. Of them,Fonseca and Fleming s MOGA [7], Srinivas and Deb s NSGA[20], and Hornet al. s NPGA [13] enjoyed more algorithms demonstrated the necessary additional oper-ators for converting a simple EA to a MOEA. Two commonfeatures on all three operators were the following: i) assigningfitness to population members based on nondominated sortingand ii) preserving diversity among solutions of the samenondominated front.

10 Although they have been shown to findmultiple nondominated solutions on many test problems and anumber of engineering design problems, researchers realizedthe need of introducing more useful operators (which havebeen found useful in single-objective EA s) so as to solvemultiobjective optimization problems better. Particularly,the interest has been to introduce elitism to enhance theconvergence properties of a MOEA. Reference [25] showedthat elitism helps in achieving better convergence in the existing elitist MOEAs, Zitzler and Thiele s SPEA[26], Knowles and Corne s Pareto-archived PAES [14], andRudolph s elitist GA [18] are well studied.