Investigating and exploiting the bias of the weighted hypervolume to articulate user preferences

ABSTRACT

Optimizing the hypervolume indicator within evolutionary multiobjective optimizers has become popular in the last years. Recently, the indicator has been generalized to the weighted case to incorporate various user preferences into hypervolume-based search algorithms. There are two main open questions in this context: (i) how does the specified weight influence the distribution of a fixed number of points that maximize the weighted hypervolume indicator? (ii) how can the user articulate her preferences easily without specifying a certain weight distribution function?

In this paper, we tackle both questions. First, we theoretically investigate optimal distributions of μ points that maximize the weighted hypervolume indicator. Second, based on the obtained theoretical results, we propose a new approach to articulate user preferences within biobjective hypervolume-based optimization in terms of specifying a desired density of points on a predefined (imaginary) Pareto front. Within this approach, a new exact algorithm based on dynamic programming is proposed which selects the set of μ points that maximizes the (weighted) hypervolume indicator. Experiments on various test functions show the usefulness of this new preference articulation approach and the agreement between theory and practice.

REFERENCES

• 1: Anne Auger , Johannes Bader , Dimo Brockhoff , Eckart Zitzler, Articulating user preferences in many-objective problems by sampling the weighted hypervolume, Proceedings of the 11th Annual conference on Genetic and evolutionary computation, July 08-12, 2009, Montreal, Québec, Canada [doi>10.1145/1569901.1569979]
• 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, and M. Emmerich. SMS-EMOA: Multiobjective Selection Based on Dominated Hypervolume. European Journal on Operational Research 181:1653--1669, 2007.
• 5: Nicola Beume , Boris Naujoks , Mike Preuss , Günter Rudolph , Tobias Wagner, Effects of 1-Greedy $\mathcal{S}$-Metric-Selection on Innumerably Large Pareto Fronts, Proceedings of the 5th International Conference on Evolutionary Multi-Criterion Optimization, April 07-10, 2009, Nantes, France [doi>10.1007/978-3-642-01020-0_7]
• 6: J. Branke, T. Kaußler, and H. Schmeck. Guidance in Evolutionary Multi-Objective Optimization. Advances in Engineering Software 32:499--507, 2001.
• 7: C. A. Coello Coello. Handling Preferences in Evolutionary Multiobjective Optimization: A Survey. In Congress on Evolutionary Computation (CEC 2000)pages 30--37. IEEE Press, 2000.
• 8: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 9: Kalyanmoy Deb , Deb Kalyanmoy, Multi-Objective Optimization Using Evolutionary Algorithms, John Wiley & Sons, Inc., New York, NY, 2001
• 10: 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]
• 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 Evolutionary Multiobjective Optimization: Theoretical Advances and Applications chapter 6, pages 105--145. Springer, 2005.
• 13: M. Fleischer. The measure of Pareto optima. Applications to multi-objective metaheuristics. In Conference on Evolutionary Multi-Criterion Optimization (EMO 2003) pages 519--533, Faro, Portugal, 2003. Springer.
• 14: 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]
• 15: J. Knowles and D. Corne. On Metrics for Comparing Non-Dominated Sets. In Congress on Evolutionary Computation (CEC 2002)pages 711--716. IEEE Press, 2002.
• 16: K. Miettinen. Nonlinear Multiobjective Optimization Kluwer, Boston, MA, USA, 1999.
• 17: 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, 2006.
• 18: E. Zitzler, D. Brockhoff, and L. Thiele. The Hypervolume Indicator Revisited: On the Design of Pareto-compliant Indicators Via Weighted Integration. In Conference on Evolutionary Multi-Criterion Optimization (EMO 2007) pages 862--876, Berlin, 2007. Springer.
• 19: 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]
• 20: E. Zitzler, L. Thiele, and J. Bader. On Set-Based Multiobjective Optimization (Revised Version). TIK Report 300, Computer Engineering and Networks Laboratory (TIK), ETH Zurich, Dec. 2008.

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, preference articulation