An Improved Dimension-Sweep Algorithm for the Hypervolume Indicator
Carlos M. Fonseca, Luís Paquete, Manuel López‐Ibáñez · 2006
This paper presents a recursive, dimension-sweep algorithm for computing the hypervolume indicator of the quality of a set of n non-dominated points in d > 2 dimensions. It improves upon the existing HSO (Hypervolume by Slicing Objectives) algorithm by pruning the recursion tree to avoid repeated dominance checks and the recalculation of partial hypervolumes. Additionally, it incorporates a recent result for the three-dimensional special case. The proposed algorithm achieves O(nd−2log n) time and linear space complexity in the worst-case, but experimental results show that the pruning techniques used may reduce the time complexity exponent even further.