Quality indicators were initially proposed as an alternative approach to the assessment of the performance of stochastic multiobjective optimisation algorithms. However, few of the many quality indicators proposed in the literature are compliant with the notion of Pareto-dominance between sets. The hypervolume indicator is strictly monotonic with respect to Pareto-dominance, a property which has motivated its use also as a selection criterion in multiobjective evolutionary algorithms.
The computation of the hypervolume indicator is a special case of Klee's measure problem, also known as measure of the union of rectangles, where all axis-aligned rectangles have the same upper vertex (assuming minimisation). However, hypervolume indicator computation is known to be simpler than the general Klee's measure problem.
In three dimensions, the hypervolume indicator can be computed in asymptotically optimal O(n log n) time [1]. A recursive dimension-sweep algorithm using this three-dimensional base case is described in [2], achieving O(nd-2 log n) worst-case complexity, where d denotes the number of dimensions. An implementation in C is available here.
A faster dimension-sweep algorithm for the four-dimensional case, with O(n2) time complexity, was proposed in [3]. The source code has now been released.
Finally, an approach based on the decomposition of the dominated region into disjoint boxes leads to an algorithm for the computation of the hypervolume indicator with a time complexity of O(n⌊(d-1)/2⌋+1) [4]. In addition, the current hypervolume can be updated in O(n⌊d/2⌋) time when a new point is added to an existing set. Source code is available here.
A related problem consists of determining the hypervolume of the region dominated exclusively by each point in a non-dominated point set. This information is used by hypervolume-based EMO algorithms, such as SMS-EMOA, in the selection and replacement mechanisms. Such hypervolume contributions may be obtained by iterating over all points in a non-dominated point set and taking the difference between the hypervolume dominated by the whole set and that dominated when the current point is excluded, but they can be computed more efficiently using dedicated algorithms. An asymptotically optimal O(n log n) time algorithm to compute all hypervolume contributions in the three-objective case is described in [5], and the corresponding C++ implementation is also available as source code.
An algorithm to update all hypervolume contributions in linear time in the three dimensional case under single-point additions or removals is proposed in [6], enabling the computation of all hypervolume contributions in O(n2) time in four dimensions. The source code is also available.
A greedy algorithm for hypervolume subset selection in the three dimensional case is proposed in [7]. The source code is available here.
| [1] | N. Beume, C. M. Fonseca, M. López-Ibáñez, L. Paquete, and J. Vahrenhold, “On the complexity of computing the hypervolume indicator,” IEEE Transactions on Evolutionary Computation, vol. 13, pp. 1075-1082, Oct. 2009. [ DOI ] |
| [2] | C. M. Fonseca, L. Paquete, and M. López-Ibáñez, “An improved dimension-sweep algorithm for the hypervolume indicator,” in CEC 2006, IEEE Congress on Evolutionary Computation, (Vancouver, Canada), pp. 1157--1163, July 2006. [ DOI | source code ] |
| [3] | A. P. Guerreiro, C. M. Fonseca, and M. T. M. Emmerich, “A fast dimension-sweep algorithm for the hypervolume indicator in four dimensions,” in Proceedings of the 24th Canadian Conference on Computational Geometry (CCCG 2012), (Charlottetown, Prince Edward Island, Canada), Aug. 2012. [ source code | .pdf ] |
| [4] | R. Lacour, K. Klamroth, and C. M. Fonseca, “A box decomposition algorithm to compute the hypervolume indicator,” Computers & Operations Research, vol. 79, pp. 347--360, Mar. 2017. [ DOI | source code ] |
| [5] | M. T. M. Emmerich and C. M. Fonseca, “Computing hypervolume contributions in low dimensions: Asymptotically optimal algorithm and complexity results,” in Evolutionary Multi-Criterion Optimization. Sixth International Conference, EMO 2011 (R. H. C. Takahashi, K. Deb, E. F. Wanner, and S. Greco, eds.), vol. 6576 of Lecture Notes in Computer Science, pp. 121--135, Berlin: Springer, 2011. [ DOI | source code ] |
| [6] | A. P. Guerreiro and C. M. Fonseca, “Computing and updating hypervolume contributions in up to four dimensions,” CISUC Technical Report TR-2017-001, University of Coimbra, 2017. [ source code | .pdf ] |
| [7] | A. P. Guerreiro, C. M. Fonseca, and L. Paquete, “Greedy hypervolume subset selection in low dimensions,” Evolutionary Computation, vol. 24, no. 3, pp. 521--544, 2016. [ DOI | source code | .pdf ] |