Nsga-Ii

THE PRESENCE of multiple objectives in a problem, in

principle, gives rise to a set of optimal solutions (largely

known as Pareto-optimal solutions), instead of a single optimal

solution. In the absence of any further information, one of these

Pareto-optimal solutions cannot be said to be better than the

other. This demands a user to find as many Pareto-optimal solutions

as possible. Classical optimization methods (including the

multicriterion decision-making methods) suggest converting the

multiobjective optimization problem to a single-objective optimization

problem by emphasizing one particular Pareto-optimal

solution at a time. When such a method is to be used for finding

multiple solutions, it has to be applied many times, hopefully

finding a different solution at each simulation run.

Over the past decade, a number of multiobjective evolutionary

algorithms (MOEAs) have been suggested [1], [7], [13],

Manuscript received August 18, 2000; revised February 5, 2001 and

September 7, 2001. The work of K. Deb was supported by the Ministry

of Human Resources and Development, India, under the Research and

Development Scheme.

The authors are with the Kanpur Genetic Algorithms Laboratory, Indian Institute

of Technology, Kanpur PIN 208 016, India (e-mail: deb@iitk.ac.in).

Publisher Item Identifier S 1089-778X(02)04101-2.

[20], [26]. The primary reason for this is their ability to find

multiple Pareto-optimal solutions in one single simulation run.

Since evolutionary algorithms (EAs) work with a population of

solutions, a simple EA can be extended to maintain a diverse

set of solutions. With an emphasis for moving toward the true

Pareto-optimal region, an EA can be used to find multiple

Pareto-optimal solutions in one single simulation run.

The nondominated sorting genetic algorithm (NSGA) proposed

in [20] was one of the first such EAs. Over the years, the

main criticisms of the NSGA approach have been as follows.

1) High computational...