Non-dominated Sorting Differential Evolution (NSDE): An Extension of Differential Evolution for Multi- objective Optimization
Rakesh Angira, B. V. Satish Babu · Indian International Conference on Artificial Intelligence · 2005
Abstract. Most of the real world optimization problems are multi-objective in nature. Recently, Evolutionary algorithms are gaining popularity for solving Multi-Objective Optimization Problems (MOOPs) due to their inherent advan-tages over traditional methods. In this paper, Differential Evolution (an evolu-tionary algorithm that is significantly faster and robust for optimization prob-lems over continuous domain) is extended for solving MOOPs and we call this extended algorithm as Non-dominated Sorting Differential Evolution (NSDE). The proposed algorithm is applied successfully to two different benchmark test problems. Also, the effect of various key parameters on the performance of NSDE is studied. A high value of crossover constant (≅ 1) and a value of 0.5 for scaling factor are found suitable for both the problems. 1 Introduction Many engineering applications involve multiple criteria, and recently, the exploration of Evolutionary Multi-Objective Optimization (EMOO) techniques has increased [1]. The ideal approach for a multi-objective problem is the one that optimizes all con-flicting objectives simultaneously. Classical optimization methods can at best find one solution in a single run, on the other hand evolutionary algorithms can find mul-tiple optimal solutions in a single run due to their population based approach. Addi-tionally, evolutionary algorithms are less susceptible to problem dependent character-istics, such as the shape of the Pareto front (convex, concave, or even discontinuous), and the mathematical properties of the search space, whereas these issues are of con-cerns for mathematical programming techniques for mathematical tractability. Schaffer [2] proposed the first practical approach to multi-criteria optimization us-ing EAs, Vector Evaluated Genetic Algorithm (VEGA). After that there have been several other versions of evolutionary algorithms that attempt to generate multiple non-dominated solutions such as [3, 4]. The concept of Pareto-based fitness assign-ment was first proposed by [5], as a means of assigning equal probability of repro-duction to all non-dominated individuals in the population. Fonseca and Fleming [6] have proposed a multi-objective genetic algorithm (MOGA). Srinivas and Deb [7] proposed NSGA, where a sorting and fitness assignment procedure based on Gold-