Abstract-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(n d−2 log 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.
It also uses the optimal O(n log n) algorithm for 3-D REF .
An Improved Dimension-Sweep Algorithm for the Hypervolume Indicator
2006 IEEE International Conference on Evolutionary Computation
2006 IEEE International Conference on Evolutionary Computation
Mathematics Computer Science