Novel Algorithm to Calculate Hypervolume Indicator of Pareto Approximation Set

Hypervolume indicator is a commonly accepted quality measure for comparing Pareto approximation set generated by multi-objective optimizers. The best known algorithm to calculate it for n points in d-dimensional space has a run time of O(n d/2) with special data structures. This paper presents a recursive, vertex-splitting algorithm for calculating the hypervolume indicator of a set of n non-comparable points in d > 2 dimensions. It splits out multiple children hyper-cuboids which can not be dominated by a splitting reference point. In special, the splitting reference point is carefully chosen to minimize the number of vertices of the child hyper-cuboid. The complexity analysis shows that the proposed algorithm achieves \(O((\frac{d}{2})^n)\) time and O(dn 2) space complexity in the worst case.