Using a distance metric to guide PSO algorithms for many-objective optimization

ABSTRACT

In this paper we propose to use a distance metric based on user-preferences to efficiently find solutions for many-objective problems. We use a particle swarm optimization (PSO) algorithm as a baseline to demonstrate the usefulness of this distance metric, though the metric can be used in conjunction with any evolutionary multi-objective (EMO) algorithm. Existing user-preference based EMO algorithms rely on the use of dominance comparisons to explore the search-space. Unfortunately, this is ineffective and computationally expensive for many-objective problems. In the proposed distance metric based PSO, particles update their positions and velocities according to their closeness to preferred regions in the objective-space, as specified by the decision maker. The proposed distance metric allows an EMO algorithm's search to be more effective especially for many-objective problems, and to be more focused on the preferred regions, saving substantial computational cost. We demonstrate how to use a distance metric with two user-preference based PSO algorithms, which implement the reference point and light beam search methods. These algorithms are compared to a user-preference based PSO algorithm relying on the conventional dominance comparisons. Experimental results suggest that the distance metric based algorithms are more effective and efficient especially for difficult many-objective problems.

REFERENCES

• 1: M. Clerc and J. Kennedy. The particle swarm - explosion, stability, and convergence in a multidimensional complex space. IEEE Transactions on Evolutionary Computation, 6:58--73, 2002.
• 2: K. Deb, S. Agrawal, A. Pratab, and T. Meyarivan. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6:182--197, 2002.
• 3: Kalyanmoy Deb , Abhishek Kumar, Interactive evolutionary multi-objective optimization and decision-making using reference direction method, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England [doi>10.1145/1276958.1277116]
• 4: K. Deb and A. Kumar. Light beam search based multi-objective optimization using evolutionary algorithms. In IEEE Congress on Evolutionary Computation (CEC), 2007.
• 5: 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]
• 6: K. Deb, L. Thiele, M. Laumanns, and E. Zitzler. Scalable test problems for evolutionary multi-objective optimization. In Evolutionary Multiobjective Optimization (EMO): Theoretical Advances and Applications, pages 105--145. Springer, 2005.
• 7: 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
• 8: M. Ehrgott and X. Gandibleux. Multiple Criteria Optimization: State of the Art Annotated Bibliographic Survey, volume 52 of International Series in Operations Research and Management Science. Kluwer Academic Publishers, 2002.
• 9: S. Huband, P. Hingston, L. Barone, and R. L. While. A review of multiobjective test problems and a scalable test problem toolkit. IEEE Transactions on Evolutionary Computation, 10:477--506, 2006.
• 10: A. Jaszkiewicz and R. Slowinski. The light beam search approach - an overview of methodology and applications. European Journal of Operational Research, 113:300--314, 1999.
• 11: James Kennedy , Russell C. Eberhart, Swarm intelligence, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2001
• 12: M. Koppen and R. Vicente-Garcia. A fuzzy scheme for the ranking of multivariate data and its application. In North American Fuzzy Information Processing Society (NAFIPS), pages 140--145, 2004.
• 13: M. Koppen, R. Vicente-Garcia, and B. Nickolay. Fuzzy-pareto-dominance and its application in evolutionary multi-objective optimization. In Evolutionary Multiobjective Optimization (EMO), volume 3410 of Lecture Notes in Computer Science, pages 399--412. Springer, 2005.
• 14: Mario Köppen , Kaori Yoshida, Many-Objective Particle Swarm Optimization by Gradual Leader Selection, Proceedings of the 8th international conference on Adaptive and Natural Computing Algorithms, Part I, April 11-14, 2007, Warsaw, Poland [doi>10.1007/978-3-540-71618-1_36]
• 15: S. Kukkonen and J. Lampinen. Ranking-dominance and many-objective optimization. In IEEE Congress on Evolutionary Computation (CEC), pages 3983--3990, 2007.
• 16: X. Li. A non-dominated sorting particle swarm optimizer for multiobjective optimization. In Genetic and Evolutionary Computation Conference (GECCO), volume 2723 of Lecture Notes in Computer Science, pages 37--48. Springer, 2003.
• 17: X. Li. Better spread and convergence: Particle swarm multiobjective optimization using the maximin fitness function. In Genetic and Evolutionary Computation Conference (GECCO), volume 3102 of Lecture Notes in Computer Science, pages 117--128. Springer, 2004.
• 18: Kaisa Miettinen, Some Methods for Nonlinear Multi-objective Optimization, Proceedings of the First International Conference on Evolutionary Multi-Criterion Optimization, p.1-20, March 07-09, 2001
• 19: Sanaz Mostaghim , Hartmut Schmeck, Distance Based Ranking in Many-Objective Particle Swarm Optimization, Proceedings of the 10th international conference on Parallel Problem Solving from Nature: PPSN X, September 13-17, 2008, Dortmund, Germany [doi>10.1007/978-3-540-87700-4_75]
• 20: A. Sulflow, N. Drechsler, and R. Drechsler. Robust multi-objective optimization in high dimensional spaces. In Evolutionary Multiobjective Optimization (EMO), volume 4403 of Lecture Notes in Computer Science, pages 715--726. Springer, 2006.
• 21: Upali Wickramasinghe , Xiaodong Li, Choosing Leaders for Multi-objective PSO Algorithms Using Differential Evolution, Proceedings of the 7th International Conference on Simulated Evolution and Learning, December 07-10, 2008, Melbourne, Australia [doi>10.1007/978-3-540-89694-4_26]
• 22: Upali K. Wickramasinghe , Xiaodong Li, Integrating user preferences with particle swarms for multi-objective optimization, Proceedings of the 10th annual conference on Genetic and evolutionary computation, July 12-16, 2008, Atlanta, GA, USA [doi>10.1145/1389095.1389237]
• 23: Eckart Zitzler , Kalyanmoy Deb , Lothar Thiele, Comparison of Multiobjective Evolutionary Algorithms: Empirical Results, Evolutionary Computation, v.8 n.2, p.173-195, June 2000 [doi>10.1162/106365600568202]

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:
light beam search, many-objective optimization, multi-objective optimization, particle swarm optimization, reference point method, user-preference methods