Effectiveness of scalability improvement attempts on the performance of NSGA-II for many-objective problems

ABSTRACT

Recently a number of approaches have been proposed to improve the scalability of evolutionary multiobjective optimization (EMO) algorithms to many-objective problems. In this paper, we examine the effectiveness of those approaches through computational experiments on multiobjective knapsack problems with two, four, six, and eight objectives. First we briefly review related studies on evolutionary many-objective optimization. Next we explain why Pareto dominance-based EMO algorithms do not work well on many-objective optimization problems. Then we explain various scalability improvement approaches. We examine their effects on the performance of NSGA-II through computational experiments. Experimental results clearly show that the diversity of solutions is decreased by most scalability improvement approaches while the convergence of solutions to the Pareto front is improved. Finally we conclude this paper by pointing out future research directions.

REFERENCES

• 1: Ajith Abraham , Lakhmi C. Jain , Robert Goldberg, Evolutionary Multiobjective Optimization: Theoretical Advances and Applications (Advanced Information and Knowledge Processing), Springer-Verlag New York, Inc., Secaucus, NJ, 2005
• 2: Branke, J., Kaußler, T., and Schmeck, H. Guidance in evolutionary multi-objective optimization. Advances in Engineering Software 32, 6 (2001) 499--507.
• 3: Brockhoff, D., and Zitzler, E. Are all objectives necessary? On dimensionality reduction in evolutionary multiobjective optimization. Lecture Notes in Computer Science 4193: Parallel Problem Solving from Nature - PPSN IX, Springer, Berlin (2006) 533--542.
• 4: Brockhoff, D., and Zitzler, E. Improving hypervolume-based multiobjective evolutionary algorithms by using objective reduction methods. Proc. of 2007 IEEE Congress on Evolutionary Computation (2007) 2086--2093.
• 5: Coello, C. A. C., and Lamont, G. B. Applications of Multi-Objective Evolutionary Algorithms. World Scientific, Singapore (2004).
• 6: 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
• 7: David W. Corne , Joshua D. Knowles, Techniques for highly multiobjective optimisation: some nondominated points are better than others, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England [doi>10.1145/1276958.1277115]
• 8: Kalyanmoy Deb , Deb Kalyanmoy, Multi-Objective Optimization Using Evolutionary Algorithms, John Wiley & Sons, Inc., New York, NY, 2001
• 9: Deb, K., Pratap, A., Agarwal, S., and Meyarivan, T. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans. on Evolutionary Computation 6, 2 (2002) 182--197.
• 10: Deb, K., and Saxena, D. K. On finding Pareto-optimal solutions through dimensionality reduction for certain large-dimensional multi-objective optimization problems. KanGAL Report, No. 2005011, Kanpur Genetic Algorithms Laboratory (KanGAL), Indian Institute of Technology Kanpur (2005).
• 11: Deb, K., and Saxena, K. Searching for Pareto-optimal solutions through dimensionality reduction for certain large-dimensional multi-objective optimization problems. Proc. of 2006 IEEE Congress on Evolutionary Computation (2006) 3353--3360.
• 12: Kalyanmoy Deb , J. Sundar, Reference point based multi-objective optimization using evolutionary algorithms, Proceedings of the 8th annual conference on Genetic and evolutionary computation, July 08-12, 2006, Seattle, Washington, USA [doi>10.1145/1143997.1144112]
• 13: Nicole Drechsler , Rolf Drechsler , Bernd Becker, Multi-objective Optimisation Based on Relation Favour, Proceedings of the First International Conference on Evolutionary Multi-Criterion Optimization, p.154-166, March 07-09, 2001
• 14: Fleming, P. J., Purshouse, R. C., and Lygoe, R. J. Many-objective optimization: An engineering design perspective. Lecture Notes in Computer Science 3410: Evolutionary Multi-Criterion Optimization - EMO 2005, Springer, Berlin (2005) 14--32.
• 15: Hughes, E. J. Evolutionary many-objective optimization: Many once or one many?. Proc. of 2005 IEEE Congress on Evolutionary Computation (2005) 222--227.
• 16: Hughes, E. J. MSOPS-II: A general-purpose many-objective optimizer. Proc. of 2007 IEEE Congress on Evolutionary Computation (2007) 3944--3951.
• 17: Ikeda, K., Kita, H., and Kobayashi, S. Failure of Pareto-based MOEAs: Does non-dominated really mean near to optimal?. Proc. of 2001 IEEE Congress on Evolutionary Computation (2001) 957--962.
• 18: Ishibuchi, H., Doi, T., and Nojima, Y. Incorporation of scalarizing fitness functions into evolutionary multiobjective optimization algorithms. Lecture Notes in Computer Science 4193: Parallel Problem Solving from Nature - PPSN IX, Springer, Berlin (2006) 493--502.
• 19: Ishibuchi, H., and Nojima, Y. Optimization of scalarizing functions through evolutionary multiobjective optimization. Lecture Notes in Computer Science 4403: Evolutionary Multi-Criterion Optimization - EMO 2007, Springer, Berlin (2007) 51--65.
• 20: Ishibuchi, H., Tsukamoto, N., and Nojima, Y. Iterative approach to indicator-based multiobjective optimization. Proc. of 2007 IEEE Congress on Evolutionary Computation (2007) 3697--3704.
• 21: Ishibuchi, H., Tsukamoto, N., and Nojima, Y. Evolutionary many-objective optimization: A short review. Proc. of 2008 IEEE Congress on Evolutionary Computation (in press).
• 22: Jaszkiewicz, A. On the performance of multiple-objective genetic local search on the 0/1 knapsack problem - A comparative experiment. IEEE Trans. on Evolutionary Computation 6, 4 (2002) 402--412.
• 23: Jaszkiewicz, A. On the computational efficiency of multiple objective metaheuristics: The knapsack problem case study. European Journal of Operational Research 158, 2 (2004) 418--433.
• 24: Khara, V., Yao, X., and Deb, K. Performance scaling of multi-objective evolutionary algorithms. Lecture Notes in Computer Science 2632: Evolutionary Multi-Criterion Optimization - EMO 2003, Springer, Berlin (2004) 367--390.
• 25: Köppen, M. and Yoshida, K. Substitute distance assignments in NSGA-II for handling many-objective optimization problems. Lecture Notes in Computer Science 4403: Evolutionary Multi-Criterion Optimization - EMO 2007, Springer, Berlin (2007) 727--741.
• 26: Kukkonen, S., and Lampinen, J. Ranking-dominance and many-objective optimization. Proc. of 2007 IEEE Congress on Evolutionary Computation (2007) 3983--3990.
• 27: Purshouse, R. C., and Fleming, P. J. Evolutionary many-objective optimization: An exploratory analysis. Proc. of 2003 IEEE Congress on Evolutionary Computation (2003) 2066--2073.
• 28: Sato, H., Aguirre, H. E., and Tanaka, K. Controlling dominance area of solutions and its impact on the performance of MOEAs. Lecture Notes in Computer Science 4403: Evolutionary Multi-Criterion Optimization - EMO 2007, Springer, Berlin (2007) 5--20.
• 29: Sülflow, A., Drechsler, N., and Drechsler, R. Robust multi-objective optimization in high dimensional spaces. Lecture Notes in Computer Science 4403: Evolutionary Multi-Criterion Optimization - EMO 2007, Springer, Berlin (2007) 715--726.
• 30: Thiele, L., Miettinen, K., Korhonen, P. J., and Molina, J. A preference-based interactive evolutionary algorithm for multiobjective optimization. Helsinki School of Economics, Working Paper (2007) W-412.
• 31: Wagner, T., Beume, N., and Naujoks, B. Pareto-, aggregation-, and indicator-based methods in many-objective optimization. Lecture Notes in Computer Science 4403: Evolutionary Multi-Criterion Optimization - EMO 2007, Springer, Berlin (2007) 742--756.
• 32: Zhang, Q., and Li, H. MOEA/D: A multiobjective evolutionary algorithm based on decomposition. IEEE Trans. on Evolutionary Computation 11, 6 (2007) 712--731.
• 33: Zitzler, E., and Thiele, L. Multiobjective evolutionary algorithms: A comparative case study and the strength Pareto approach. IEEE Trans. on Evolutionary Computation 3 , 4 (1999) 257--271.

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:
balance between diversity and convergence, crowding distance, evolutionary multiobjective optimization, knapsack problems, many-objective optimization, pareto dominance