# A Fast Elitist Non-dominated Sorting Genetic Algorithm for Multi-objective Optimisation: NSGA-II

@inproceedings{Deb2000AFE, title={A Fast Elitist Non-dominated Sorting Genetic Algorithm for Multi-objective Optimisation: NSGA-II}, author={Kalyanmoy Deb and Samir Agrawal and Amrit Pratap and T. Meyarivan}, booktitle={PPSN}, year={2000} }

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. [...] Key Method Specifically, a fast non-dominated sorting approach with O(MN2) computational complexity is presented. Expand

#### 4,590 Citations

A Multi-objective Genetic Algorithm Based on Quick Sort

- Computer Science
- Canadian Conference on AI
- 2004

It is proved that the individuals of an evolutionary population can be sorted by quick sort, and the time complexity of the construction is O( nlog n), compared to the previous best result of O(n 2) described in the popular NSGA-II. Expand

Multi-objective evolutionary algorithms based on the summation of normalized objectives and diversified selection

- Mathematics, Computer Science
- Inf. Sci.
- 2010

With the proposed method, the performance metric has improved significantly and the speed of the parent selection process has also increased when compared with the non-domination sorting, and the proposed algorithm also outperforms ten other algorithms. Expand

Controlled Elitist Non-dominated Sorting Genetic Algorithms for Better Convergence

- Computer Science
- EMO
- 2001

By applying an elitist multi-objective EA (NSGA-II) to a number of difficult test problems, it is shown that the NS GA-II with controlled elitism has much better convergence property than the original NSGA- II. Expand

Substitute Distance Assignments in NSGA-II for Handling Many-objective Optimization Problems

- Mathematics, Computer Science
- EMO
- 2006

A study on the performance of the Fast Elitist Nondominated Sorting Genetic Algorithm (NSGA-II) for handling many-objective optimization problems is presented, and substitute distance assignment schemes are proposed that can replace the crowding distance assignment, which is normally used in NSGA- II. Expand

Improved NSGA-II Multi-objective Genetic Algorithm Based on Hybridization-encouraged Mechanism

- Mathematics
- 2008

Abstract To improve performances of multi-objective optimization algorithms, such as convergence and diversity, a hybridization- encouraged mechanism is proposed and realized in elitist nondominatedâ€¦ Expand

A fast and elitist multi-objective particle swarm algorithm: NSPSO

- Computer Science
- 2008 IEEE International Conference on Granular Computing
- 2008

A new nondominated sorting particle swarm optimisation (NSPSO) framework is proposed, that combines the operations of a known MOGA NSGA-II and the other advanced operations with a single particle Swarm optimiser (PSO). Expand

A novel diversification strategy for multi-objective evolutionary algorithms

- Mathematics, Computer Science
- GECCO '10
- 2010

A new archiving strategy based on the Convex Hull of Individual Minima (CHIM), which is intended to maintain a well-distributed set of non-dominated solutions is introduced. Expand

A New Method to Construct the Non-Dominated Set in Multi-Objective Genetic Algorithms

- Computer Science
- Intelligent Information Processing
- 2004

A new method called Dealer's Principle to construct non-dominated sets of MOGA and a clustering algorithm based on the core distance of clusters to keep the diversity of solutions is proposed. Expand

An Improved Elitist Strategy Multi-Objective Evolutionary Algorithm

- Mathematics
- 2006 International Conference on Machine Learning and Cybernetics
- 2006

NSGA II (fast elitist non-dominated sorting genetic algorithm) is one of better elitist multi-objective evolutionary algorithm. It doesn't limit the elitist extent, which will result in prematurelyâ€¦ Expand

moPGA: Towards a New Generation of Multi-objective Genetic Algorithms

- Mathematics, Computer Science
- 2006 IEEE International Conference on Evolutionary Computation
- 2006

Comparisons with well-known multi-objective GAs on scalable benchmark problems indicate that the algorithm scales well with problem size in terms of number of function evaluations and quality of solutions found. Expand

#### References

SHOWING 1-10 OF 36 REFERENCES

The Pareto archived evolution strategy: a new baseline algorithm for Pareto multiobjective optimisation

- Mathematics, Computer Science
- Proceedings of the 1999 Congress on Evolutionary Computation-CEC99 (Cat. No. 99TH8406)
- 1999

It is argued that PAES may represent the simplest possible non-trivial algorithm capable of generating diverse solutions in the Pareto optimal set, and is intended as a good baseline approach against which more involved methods may be compared. Expand

Muiltiobjective Optimization Using Nondominated Sorting in Genetic Algorithms

- Mathematics, Computer Science
- Evolutionary Computation
- 1994

Goldberg's notion of nondominated sorting in GAs along with a niche and speciation method to find multiple Pareto-optimal points simultaneously are investigated and suggested to be extended to higher dimensional and more difficult multiobjective problems. Expand

Genetic Algorithms for Multiobjective Optimization: FormulationDiscussion and Generalization

- Computer Science
- ICGA
- 1993

A rank-based fitness assignment method for Multiple Objective Genetic Algorithms (MOGAs) and the genetic algorithm is seen as the optimizing element of a multiobjective optimization loop, which also comprises the DM. Expand

A niched Pareto genetic algorithm for multiobjective optimization

- Mathematics, Computer Science
- Proceedings of the First IEEE Conference on Evolutionary Computation. IEEE World Congress on Computational Intelligence
- 1994

The Niched Pareto GA is introduced as an algorithm for finding the Pare to optimal set and its ability to find and maintain a diverse "Pareto optimal population" on two artificial problems and an open problem in hydrosystems is demonstrated. Expand

Comparison of Multiobjective Evolutionary Algorithms: Empirical Results

- Computer Science, Mathematics
- Evolutionary Computation
- 2000

This paper provides a systematic comparison of various evolutionary approaches to multiobjective optimization using six carefully chosen test functions and shows that elitism is shown to be an important factor for improving evolutionary multiobjectives search. Expand

Multiobjective optimization and multiple constraint handling with evolutionary algorithms. II. Application example

- Computer Science, Mathematics
- IEEE Trans. Syst. Man Cybern. Part A
- 1998

This study illustrates how a technique such as the multiobjective genetic algorithm can be applied and exemplifies how design requirements can be refined as the algorithm runs, and demonstrates the need for preference articulation in cases where many and highly competing objectives lead to a nondominated set too large for a finite population to sample effectively. Expand

Evolutionary algorithms for multiobjective optimization: methods and applications

- Computer Science
- 1999

The basic principles of evolutionary multiobjective optimization are discussed from an algorithm design perspective and the focus is on the major issues such as fitness assignment, diversity preservation, and elitism in general rather than on particular algorithms. Expand

Multi-objective Genetic Algorithms: Problem Difficulties and Construction of Test Problems

- Mathematics, Computer Science
- Evolutionary Computation
- 1999

The problem features that may cause a multi-objective genetic algorithm (GA) difficulty in converging to the true Pareto-optimal front are studied to enable researchers to test their algorithms for specific aspects of multi- objective optimization. Expand

Multiobjective optimization and multiple constraint handling with evolutionary algorithms. I. A unified formulation

- Mathematics, Computer Science
- IEEE Trans. Syst. Man Cybern. Part A
- 1998

The paper proposes that fitness assignment be interpreted as, or at least related to, a multicriterion decision process, and a suitable decision making framework based on goals and priorities is formulated in terms of a relational operator, characterized, and shown to encompass a number of simpler decision strategies. Expand

Multiobjective evolutionary algorithms: classifications, analyses, and new innovations

- Computer Science
- 1999

This research organizes, presents, and analyzes contemporary MultiObjective Evolutionary Algorithm research and associated Multiobjective Optimization Problems (MOPs) and uses a consistent MOEA terminology and notation to present a complete, contemporary view of current MOEA "state of the art" and possible future research. Expand