Greedy Hypervolume Subset Selection in the Three-Objective Case

ABSTRACT

Given a non-dominated point set X ⊂ R^d of size n and a suitable reference point r ∈ R^d, the Hypervolume Subset Selection Problem (HSSP) consists of finding a subset of size k > n that maximizes the hypervolume indicator. It arises in connection with multiobjective selection and archiving strategies, as well as Pareto-front approximation post-processing for visualization and/or interaction with a decision maker. Efficient algorithms to solve the HSSP are available only for the 2-dimensional case, achieving a time complexity of O(n(k+log n)). In contrast, the best upper bound available for d>2 is O(n^d/2 log n + n^n-k). Since the hypervolume indicator is a monotone submodular function, the HSSP can be approximated to a factor of (1-1/e) using a greedy strategy. Such a greedy algorithm for the 3-dimensional HSSP is proposed in this paper. The time complexity of the algorithm is shown to be O(n²), which considerably improves upon recent complexity results for this approximation problem.

References

1. A. Auger, J. Bader, D. Brockhoff, and E. Zitzler. Theory of the hypervolume indicator: Optimal-distributions and the choice of the reference point. In Foundations of Genetic Algorithms (FOGA 2009), pages 87--102, New York, NY, USA, 2009. ACM.
2. J. Bader and E. Zitzler. Hype: An algorithm for fast hypervolume-based many-objective optimization. Evol. Comput., 19(1):45--76, Mar. 2011.
3. N. Beume, C. Fonseca, M. López-Ibáñez, L. Paquete, and J. Vahrenhold. On the complexity of computing the hypervolume indicator. IEEE Trans. Evol. Comput., 13(5):1075--1082, Oct 2009.
4. L. Bradstreet, L. While, and L. Barone. Incrementally maximising hypervolume for selection in multi-objective evolutionary algorithms. In IEEE CEC 2007, pages 3203--3210, Sept 2007.
5. K. Bringmann and T. Friedrich. An efficient algorithm for computing hypervolume contributions. Evol. Comput., 18(3):383--402, Sept. 2010.
6. K. Bringmann, T. Friedrich, and P. Klitzke. Two-dimensional subset selection for hypervolume and epsilon-indicator. In Conference on Genetic and Evolutionary Computation, GECCO '14, pages 589--596, New York, NY, USA, 2014. ACM.
7. T. M. Chan. Klee's measure problem made easy. In Proc. 54th IEEE Symposium on Foundations of Computer Science (FOCS), pages 410--419, Los Alamitos, CA, USA, 2013. IEEE Computer Society.
8. M. Emmerich and C. Fonseca. Computing hypervolume contributions in low dimensions: Asymptotically optimal algorithm and complexity results. In EMO 2011, volume 6576 of LNCS, pages 121--135. Springer, 2011.
9. T. Friedrich and F. Neumann. Maximizing submodular functions under matroid constraints by multi-objective evolutionary algorithms. In PPSN XIII, volume 8672 of LNCS, pages 922--931. Springer International Publishing, 2014.
10. A. P. Guerreiro, C. M. Fonseca, and M. T. M. Emmerich. A fast dimension-sweep algorithm for the hypervolume indicator in four dimensions. In CCCG 2012, pages 77--82, 2012.
11. I. Hupkens and M. Emmerich. Logarithmic-time updates in SMS-EMOA and hypervolume-based archiving. In EVOLVE IV, volume 227 of Advances in Intelligent Systems and Computing, pages 155--169. Springer, 2013.
12. J. D. Knowles, D. W. Corne, and M. Fleischer. Bounded archiving using the Lebesgue measure. In IEEE CEC '03, volume 4, pages 2490--2497, 2003.
13. T. Kuhn, C. M. Fonseca, L. Paquete, S. Ruzika, and J. Figueira. Hypervolume subset selection in two dimensions: Formulations and algorithms. Technical report, Technische Universität Kaiserslautern, 2014.
14. G. Nemhauser, L. Wolsey, and M. Fisher. An analysis of approximations for maximizing submodular set functions--I. Mathematical Programming, 14(1):265--294, 1978.
15. T. Ulrich and L. Thiele. Bounding the effectiveness of hypervolume-based ( + )-archiving algorithms. In Learning and Intelligent Optimization, volume 7219 of LNCS, pages 235--249. Springer, 2012.
16. L. While, L. Bradstreet, and L. Barone. A fast way of calculating exact hypervolumes. IEEE Trans. Evol. Comput., 16(1):86--95, 2012.
17. E. Zitzler and L. Thiele. Multiobjective optimization using evolutionary algorithms -- A comparative case study. In PPSN V, volume 1498 of LNCS, pages 292--301. Springer, 1998.

Index Terms

• Theory of computation

  • Randomness, geometry and discrete structures

    • Computational geometry