Multiplicative approximations and the hypervolume indicator

ABSTRACT

Indicator-based algorithms have become a very popular approach to solve multi-objective optimization problems. In this paper, we contribute to the theoretical understanding of algorithms maximizing the hypervolume for a given problem by distributing μ points on the Pareto front. We examine this common approach with respect to the achieved multiplicative approximation ratio for a given multi-objective problem and relate it to a set of μ points on the Pareto front that achieves the best possible approximation ratio. For the class of linear fronts and a class of concave fronts, we prove that the hypervolume gives the best possible approximation ratio. In addition, we examine Pareto fronts of different shapes by numerical calculations and show that the approximation computed by the hypervolume may differ from the optimal approximation ratio.

REFERENCES

• 1: 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]
• 2: T. Bäck, D. B. Fogel, and Z. Michalewicz, editors. Handbook of Evolutionary Computation. Oxford University Press, 1997.
• 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 Zürich, 2008.
• 4: N. Beume, B. Naujoks, and M. Emmerich. SMS-EMOA: Multiobjective selection based on dominated hypervolume. European Journal of Operational Research, 181(3):1653--1669, 2007.
• 5: N. Beume and G. Rudolph. Faster S-metric calculation by considering dominated hypervolume as Klee's measure problem. In IASTED International Conference on Computational Intelligence (CI), pages 233--238. ACTA Press, 2006.
• 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: Karl Bringmann , Tobias Friedrich, Approximating the Least Hypervolume Contributor: NP-Hard in General, But Fast in Practice, 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_6]
• 8: 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
• 9: Kalyanmoy Deb , Deb Kalyanmoy, Multi-Objective Optimization Using Evolutionary Algorithms, John Wiley & Sons, Inc., New York, NY, 2001
• 10: K. Deb, L. Thiele, M. Laumanns, and E. Zitzler. Scalable multi-objective optimization test problems. In IEEE Congress on Evolutionary Computation (CEC), pages 825--830. IEEE Press, 2002.
• 11: Matthias Ehrgott, Multicriteria Optimization, Springer-Verlag New York, Inc., Secaucus, NJ, 2005
• 12: M. Emmerich, N. Beume, and B. Naujoks. An EMO algorithm using the hypervolume measure as selection criterion. In International Conference on Evolutionary Multi-Criterion Optimization (EMO), pages 62--76. Springer, 2005.
• 13: R. Fletcher, Practical methods of optimization; (2nd ed.), Wiley-Interscience, New York, NY, 1987
• 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. Properties of an adaptive archiving algorithm for storing nondominated vectors. IEEE Transactions on Evolutionary Computation, 7(2):100--116, 2003.
• 16: J. Knowles, D. Corne, and M. Fleischer. Bounded archiving using the Lebesgue measure. In IEEE Congress on Evolutionary Computation (CEC), pages 2490--2497. IEEE Press, 2003.
• 17: J. D. Knowles. Local-Search and Hybrid Evolutionary Algorithms for Pareto Optimization. PhD thesis, Department of Computer Science, University of Reading, UK, 2002.
• 18: Marco Laumanns , Lothar Thiele , Kalyanmoy Deb , Eckart Zitzler, Combining convergence and diversity in evolutionary multiobjective optimization, Evolutionary Computation, v.10 n.3, p.263-282, Fall 2002 [doi>10.1162/106365602760234108]
• 19: Giovanni Lizarraga-Lizarraga , Arturo Hernandez-Aguirre , Salvador Botello-Rionda, G-Metric: an M-ary quality indicator for the evaluation of non-dominated sets, Proceedings of the 10th annual conference on Genetic and evolutionary computation, July 12-16, 2008, Atlanta, GA, USA [doi>10.1145/1389095.1389227]
• 20: C. H. Papadimitriou , M. Yannakakis, On the approximability of trade-offs and optimal access of Web sources, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.86, November 12-14, 2000
• 21: C. M. Papadimitriou. Computational Complexity. Addison-Wesley, 1994.
• 22: E. Zitzler. Hypervolume metric calculation, 2001. Computer Engineering and Networks Laboratory (TIK), ETH Zürich, ftp://ftp.tik.ee.ethz.ch/pub/people/zitzler/hypervol.c.
• 23: E. Zitzler, D. Brockhoff, and L. Thiele. The hypervolume indicator revisited: On the design of Pareto-compliant indicators via weighted integration. In International Conference on Evolutionary Multi-Criterion Optimization (EMO), pages 862--876. Springer, 2007.
• 24: E. Zitzler and S. Künzli. Indicator-based selection in multiobjective search. In International Conference on Parallel Problem Solving from Nature (PPSN), pages 832--842. Springer, 2004.
• 25: E. Zitzler and L. Thiele. An evolutionary approach for multiobjective optimization: The strength Pareto approach. TIK Report 43, Computer Engineering and Networks Laboratory (TIK), ETH Zürich, 1998.
• 26: E. Zitzler and L. Thiele. Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach. IEEE Transactions on Evolutionary Computation, 3(4):257--271, 1999.
• 27: E. Zitzler, L. Thiele, M. Laumanns, C. M. Fonseca, and V. Grunert da Fonseca. Performance assessment of multiobjective optimizers: an analysis and review. IEEE Transactions on Evolutionary Computation, 7(2):117--132, 2003.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

General Terms:
Algorithms, Performance, Theory

Keywords:
approximation, evolutionary algorithms, hypervolume indicator, indicator-based algorithms, multi-objective optimization