Integrating user preferences with particle swarms for multi-objective optimization

ABSTRACT

This paper proposes a method to use reference points as preferences to guide a particle swarm algorithm to search towards preferred regions of the Pareto front. A decision maker can provide several reference points, specify the extent of the spread of solutions on the Pareto front as desired, or include any bias between the objectives as preferences within a single execution. We incorporate the reference point method into two multi-objective particle swarm algorithms, the non-dominated sorting PSO, and the maximinPSO. This paper first demonstrates the usefulness of the proposed reference point based particle swarm algorithms, then compare the two algorithms using a hyper-volume metric. Both particle swarm algorithms are able to converge to the preferred regions of the Pareto front using several feasible or infeasible reference points.

REFERENCES

• 1: R. Balling. The maximin fitness function; multi-objective city and regional planning. In Evolutionary Multiobjective Optimization (EMO), volume 2632 of Lecture Notes in Computer Science, pages 1--15. Springer, 2003.
• 2: J. Branke, T. Kausler, and H. Schmeck. Guidance in Evolutionary Multi-Objective Optimization. Advances in Engineering Software, 32:499--507, 2001.
• 3: M. Clerc and J. Kennedy. The particle swarm - explosion, stability, and convergence in a multidimensional complex space. IEEE Transactions on Evolutionary Computation, 6(1):58--73, 2002.
• 4: K. Deb. Solving goal programming problems using multi-objective genetic algorithms. In Congress on Evolutionary Computation (CEC), 1999.
• 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. Pratab, and T. Meyarivan. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6(2):182--197, 2002.
• 7: 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]
• 8: K. Deb and A. Kumar. Light beam search based multi-objective optimization using evolutionary algorithms. In Congress on Evolutionary Computation (CEC), 2007.
• 9: 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]
• 10: 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.
• 11: M. Ehrgott and X. Gandibleux. Multiple Criteria Optimization: State of the Art Annotated Bibliographic Survey, volume52 of International Series in Operations Research and Management Science. Kluwer Academic Publishers, Boston, 2002. 496 pages. ISBN 1-4020-7128-0.
• 12: M. Emmerich, N. Beume, and B. Naujoks. An emo algorithm using the hypervolume measure as selection criterion. In Evolutionary Multi-Criterion Optimization (EMO), LNCS, vol. 3410, pages 62--76, Berlin, 2005. Springer.
• 13: A. Jaszkiewicz and R.Slowinski. The light beam search approach -an overview of methodology and applications. European Journal of Operational Research, 113(2):300--314, 1999.
• 14: James Kennedy , Russell C. Eberhart, Swarm intelligence, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2001
• 15: J. Knowles and D. Corne. On metrics for comparing on-dominated sets. In Congress on Evolutionary Computation (CEC), 2002.
• 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: A. Messac and C. A. Mattson. Normal constraint method with guarantee of even representation of complete pareto frontier. American Institute of Aeronautics and Astronautic (AIAA)Journal, 2004.
• 19: 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
• 20: M. J. Osborne and A. Rubinstein. A Course in Game Theory. The MIT Press, July 1994.
• 21: M. Reyes-Sierra and C.A. Coello Coello. Multi-Objective Particle Swarm Optimizers: A Survey of the State-of-the-Art. International Journal of Computational Intelligence Research, 2(3):287--308, 2006.
• 22: L. Thiele, K. Miettinen, P. Korhonen, and J. Molina. A preference-based interactive evolutionary algorithm for multiobjective optimization. In Helsinki School of Economics Technical Report Number W-412, 2007.
• 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

General Terms:
Algorithms

Keywords:
maximin strategy, multi-objective problems, non-dominated sorting, particle swarm optimization, reference point method, user-preference methods