Novel algorithm to calculate hypervolume indicator of Pareto approximation set

2007/04/10 by Yang, Qing, Ding, Shengchao
#Computational Geometry (cs.CG) #FOS: Computer and information sciences #Neural and Evolutionary Computing (cs.NE)

paper · doi:10.48550/arxiv.0704.1196

Abstract

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 child 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 points in the child hyper-cuboids. The complexity analysis shows that the proposed algorithm achieves O(((d)/(2))ⁿ) time and O(dn²) space complexity in the worst case.

Related

• A Box Decomposition Algorithm to Compute the Hypervolume Indicator
• Improved Quick Hypervolume Algorithm
• The Hypervolume Indicator Hessian Matrix: Analytical Expression, Computational Time Complexity, and Sparsity
• Quick HyperVolume
• Learning to Approximate: Auto Direction Vector Set Generation for Hypervolume Contribution Approximation