Articulating user preferences in many-objective problems by sampling the weighted hypervolume

ABSTRACT

The hypervolume indicator has become popular in recent years both for performance assessment and to guide the search of evolutionary multiobjective optimizers. Two critical research topics can be emphasized with respect to hypervolume-based search: (i) the hypervolume indicator inherently introduces a specific preference and the question is how arbitrary user preferences can be incorporated; (ii) the exact calculation of the hypervolume indicator is expensive and efficient approaches to tackle many-objective problems are needed. In two previous studies, we addressed both issues independently: a study proposed the weighted hypervolume indicator with which user-defined preferences can be articulated; other studies exist that propose to estimate the hypervolume indicator by Monte-Carlo sampling. Here, we combine these two approaches for the first time and extend them, i.e., we present an approach of sampling the weighted hypervolume to incorporate user-defined preferences into the search for problems with many objectives. In particular, we propose weight distribution functions to stress extreme solutions and to define preferred regions of the objective space in terms of so-called preference points; sampling them allows to tackle problems with many objectives. Experiments on several test functions with up to 25 objectives show the usefulness of the approach in terms of decision making and search.

REFERENCES

• 1: Anne Auger , Johannes Bader , Dimo Brockhoff , Eckart Zitzler, Investigating and exploiting the bias of the weighted hypervolume to articulate user preferences, Proceedings of the 11th Annual conference on Genetic and evolutionary computation, July 08-12, 2009, Montreal, Québec, Canada [doi>10.1145/1569901.1569980]
• 2: Anne Auger , Johannes Bader , Dimo Brockhoff , Eckart Zitzler, Theory of the hypervolume indicator: optimal μ-distributions and the choice of the reference point, Proceedings of the tenth ACM SIGEVO workshop on Foundations of genetic algorithms, January 09-11, 2009, Orlando, Florida, USA [doi>10.1145/1527125.1527138]
• 3: J. Bader and E. Zitzler. HypE: An Algorithm for Fast Hypervolume-Based Many-Objective Optimization. TIK Report 286, Computer Engineering and Networks Laboratory (TIK), ETH Zurich, Nov. 2008.
• 4: N. Beume, B. Naujoks, andM. Emmerich. SMS-EMOA: Multiobjective Selection Based on Dominated Hypervolume. European Journal on Operational Research 181:1653--1669, 2007.
• 5: J. Branke, T. Kauβler, and H. Schmeck. Guidance in Evolutionary Multi-Objective Optimization. Advances in Engineering Software 32:499--507, 2001.
• 6: Karl Bringmann , Tobias Friedrich, Approximating the Volume of Unions and Intersections of High-Dimensional Geometric Objects, Proceedings of the 19th International Symposium on Algorithms and Computation, December 15-17, 2008, Gold Coast, Australia [doi>10.1007/978-3-540-92182-0_40]
• 7: R. E. Caflisch. Monte Carlo and Quasi-Monte Carlo Methods. Acta Numerica 7:1--49, 1998.
• 8: W. J. Conover. Practical Nonparametric Statistics John Wiley, 3 edition, 1999.
• 9: Kalyanmoy Deb , Deb Kalyanmoy, Multi-Objective Optimization Using Evolutionary Algorithms, John Wiley & Sons, Inc., New York, NY, 2001
• 10: Kalyanmoy Deb , Samir Agrawal , Amrit Pratap , T. Meyarivan, A Fast Elitist Non-dominated Sorting Genetic Algorithm for Multi-objective Optimisation: NSGA-II, Proceedings of the 6th International Conference on Parallel Problem Solving from Nature, p.849-858, September 18-20, 2000
• 11: K. Deb, J. Sundar, U. B. Rao N., and S. Chaudhuri. Reference Point Based Multi-Objective Optimization Using Evolutionary Algorithms. Int. Journal of Computational Intelligence Research 2(3):273--286, 2006.
• 12: K. Deb, L. Thiele, M. Laumanns, and E. Zitzler. Scalable Test Problems for Evolutionary Multi-Objective Optimization. In A. Abraham, R. Jain, and R. Goldberg, editors, Evolutionary Multiobjective Optimization: Theoretical Advances and Applications chapter 6, pages 105--145. Springer, 2005.
• 13: L. Devroye. Non-Uniform Random Variate Generation Springer, 1986.
• 14: R. Everson, J. Fieldsend, and S. Singh. Full Elite-Sets for Multiobjective Optimisation. In I. Parmee, editor, Conference on adaptive computing in design and manufacture (ADCM 2002)pages 343--354, London, UK, 2002. Springer.
• 15: M. Fleischer. The measure of Pareto optima. Applications to multi-objective metaheuristics. In C. M. Fonseca et al., editors, Conference on Evolutionary Multi-Criterion Optimization (EMO 2003)volume 2632 of LNCS pages 519--533, Faro, Portugal, 2003. Springer.
• 16: W. Hoeffding. Probability Inequalities for Sums of Bounded Random Variables. Journal of the American Statistical Association 58(301):13--30, 1963.
• 17: S. Huband, P. Hingston, L. White, and L. Barone. An Evolution Strategy with Probabilistic Mutation for Multi-Objective Optimisation. In Congress on Evolutionary Computation (CEC 2003) volume3, pages 2284--2291, Canberra, Australia, 2003. IEEE Press.
• 18: Christian Igel , Nikolaus Hansen , Stefan Roth, Covariance Matrix Adaptation for Multi-objective Optimization, Evolutionary Computation, v.15 n.1, p.1-28, Spring 2007 [doi>10.1162/evco.2007.15.1.1]
• 19: M. Laumanns, G. Rudolph, and H.-P. Schwefel. Approximating the Pareto Set:Concepts, Diversity Issues, and Performance Assessment. Technical Report CI-7299, University of Dortmund, 1999.
• 20: K. Miettinen. Nonlinear Multiobjective Optimization Kluwer, Boston, MA, USA, 1999.
• 21: M. Nicolini. A Two-Level Evolutionary Approach to Multi-criterion Optimization of Water Supply Systems. In Conference on Evolutionary Multi-Criterion Optimization (EMO 2005)volume 3410 of LNCS pages 736--751. Springer, 2005.
• 22: L. Rachmawati and D. Srinivasan. Preference Incorporation in Multi-objective Evolutionary Algorithms: A Survey. In Congress on Evolutionary Computation (CEC 2006)pages 962--968. IEEE Press, July 2006.
• 23: E. Zitzler, D. Brockhoff, and L. Thiele. The Hypervolume Indicator Revisited:On the Design of Pareto-compliant Indicators Via Weighted Integration. In S. Obayashi et al., editors, Conference on Evolutionary Multi-Criterion Optimization (EMO 2007)volume 4403 of LNCS pages 862--876, Berlin, 2007. Springer
• 24: 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]
• 25: E. Zitzler and S. Künzli. Indicator-Based Selection in Multiobjective Search. In X. Yao et al., editors, Conference on Parallel Problem Solving from Nature (PPSN VIII)volume 3242 of LNCS pages 832--842. Springer, 2004.
• 26: Eckart Zitzler , Lothar Thiele, Multiobjective Optimization Using Evolutionary Algorithms - A Comparative Case Study, Proceedings of the 5th International Conference on Parallel Problem Solving from Nature, p.292-304, September 27-30, 1998
• 27: Eckart Zitzler , Lothar Thiele , Johannes Bader, SPAM: Set Preference Algorithm for Multiobjective 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_84]

INDEX TERMS

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

General Terms:
Algorithms

Keywords:
hypervolume indicator, monte carlo sampling, preference articulation