A robust evolutionary framework for multi-objective optimization

ABSTRACT

Evolutionary multi-objective optimization (EMO) methodologies, suggested in the beginning of Nineties, focussed on the task of finding a set of well-converged and well-distributed set of solutions using evolutionary optimization principles. Of the EMO methodologies, the elitist non-dominated sorting genetic algorithm or NSGA-II, suggested in 2000, is now probably the most popularly used EMO procedure. NSGA-II follows three independent principles -- domination principle, diversity preservation principle and elite preserving principle -- which make NSGA-II a flexible and robust EMO procedure in the sense of solving various multi-objective optimization problems using a common framework. In this paper, we describe NSGA-II through a functional decomposition following the implementation of these three principles and demonstrate how various multi-objective optimization tasks can be achieved by simply modifying one of the three principles. We argue that such a functionally decomposed and modular implementation of NSGA-II is probably the reason for it's popularity and robustness in solving various types of multi-objective optimization problems.

REFERENCES

• 1: J. Branke and K. Deb. Integrating user preferences into evolutionary multi-objective optimization. In Y. Jin, editor, Knowledge Incorporation in Evolutionary Computation, pages 461--477. Hiedelberg, Germany: Springer, 2004.
• 2: J. Branke, K. Deb, H. Dierolf, and M. Osswald. Finding knees in multi-objective optimization. In Parallel Problem Solving from Nature (PPSN-VIII), pages 722--731. Heidelberg, Germany: Springer, 2004.
• 3: J. Branke, T. Kauβler, and H. Schmeck. Guidance in evolutionary multi-objective optimization. Advances in Engineering Software, 32:499--507, 2001.
• 4: Carlos A. Coello Coello , Gary B. Lamont , David A. Van Veldhuizen, Evolutionary Algorithms for Solving Multi-Objective Problems (Genetic and Evolutionary Computation), Springer-Verlag New York, Inc., Secaucus, NJ, 2006
• 5: Kalyanmoy Deb , Deb Kalyanmoy, Multi-Objective Optimization Using Evolutionary Algorithms, John Wiley & Sons, Inc., New York, NY, 2001
• 6: K. Deb, S. Agrawal, A. Pratap, and T. Meyarivan. A fast and elitist multi-objective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6(2):182--197, 2002.
• 7: Kalyanmoy Deb , Shamik Chaudhuri , Kaisa Miettinen, Towards estimating nadir objective vector using evolutionary approaches, Proceedings of the 8th annual conference on Genetic and evolutionary computation, July 08-12, 2006, Seattle, Washington, USA [doi>10.1145/1143997.1144113]
• 8: Kalyanmoy Deb , Tushar Goel, Controlled Elitist Non-dominated Sorting Genetic Algorithms for Better Convergence, Proceedings of the First International Conference on Evolutionary Multi-Criterion Optimization, p.67-81, March 07-09, 2001
• 9: K. Deb and A. Kumar. Light beam search based multi-objective optimization using evolutionary algorithms. In Proc. of the Congress on Evolutionary Computation (CEC-07), pages 2125--2132, 2007.
• 10: Kalyanmoy Deb , Manikanth Mohan , Shikhar Mishra, Evaluating the ε-Domination Based Multi-Objective Evolutionary Algorithm for a Quick Computation of Pareto-Optimal Solutions, Evolutionary Computation, v.13 n.4, p.501-525, December 2005 [doi>10.1162/106365605774666895]
• 11: K. Deb and D. Saxena. Searching for pareto-optimal solutions through dimensionality reduction for certain large-dimensional multi-objective optimization problems. In Proceedings of the World Congress on Computational Intelligence (WCCI--2006), pages 3352--3360, 2006.
• 12: K. Deb, J. Sundar, N. Uday, and S. Chaudhuri. Reference point based multi-objective optimization using evolutionary algorithms. International Journal of Computational Intelligence Research (IJCIR), 2(6):273--286, 2006.
• 13: K. Deb and S. Tiwari. Omni-optimizer: A generic evolutionary algorithm for global optimization. European Journal of Operations Research (EJOR), 185(3):1062--1087, 2008.
• 14: M. Farina and P. Amato. A fuzzy definition of "optimality" for many-criteria decision-making and optimization problems. submitted to IEEE Trans. on Sys. Man and Cybern., 34(3):315--326, 2004.
• 15: A. M. Geoffrion. Proper efficiency and theory of vector maximization. Journal of Mathematical Analysis and Applications, 22(3):618--630, 1968.
• 16: David E. Goldberg , Jon Richardson, Genetic algorithms with sharing for multimodal function optimization, Proceedings of the Second International Conference on Genetic Algorithms on Genetic algorithms and their application, p.41-49, October 1987, Cambridge, Massachusetts, United States
• 17: A. Jaszkiewicz and R. Slowinski. The light beam search approach -- An overview of methodology and applications. European Journal of Operation Research, 113:300--314, 1999.
• 18: Joshua Knowles , David Corne , Kalyanmoy Deb, Multiobjective Problem Solving from Nature: From Concepts to Applications (Natural Computing Series), 2008
• 19: S. Kukkonen and K. Deb. Improved pruning of non-dominated solutions based on crowding distance for bi-objective optimization problems. In Proc. of the Congress on Evolutionary Computation (CEC--06), pages 1179 -- 1186, 2006.
• 20: Marco Laumanns , Lothar Thiele , Kalyanmoy Deb , Eckart Zitzler, Combining convergence and diversity in evolutionary multiobjective optimization, Evolutionary Computation, v.10 n.3, p.263-282, Fall 2002 [doi>10.1162/106365602760234108]
• 21: K. Miettinen. Nonlinear Multiobjective Optimization. Kluwer, Boston, 1999.
• 22: Ian C. Parmee , Dragan C. Cvetković , Andrew H. Watson , Christopher R. Bonham, Multiobjective Satisfaction within an Interactive Evolutionary Design Environment, Evolutionary Computation, v.8 n.2, p.197-222, June 2000 [doi>10.1162/106365600568176]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

General Terms:
Algorithms

Keywords:
decision-making, evolutionary optimization, functional decomposition, multi-objective optimization