A Fast Exact Algorithm for Computing the Hypervolume Contributions in 4-D Space
Jingda Deng, Qingfu Zhang, Jianyong Sun, Hui Li · IEEE Transactions on Evolutionary Computation · 2023
The hypervolume contribution is widely used in indicator-based multiobjective algorithms. We propose an algorithm to compute exact 4-D hypervolume contributions for a set of n points in O(n32logn) time. Our algorithm improves the currently best time complexity O(n2) by O(nlogn), and it is the first algorithm of subquadratic time for this problem. Our algorithm is built upon a space partition method in computational geometry and a geometric structure called the anchored gradient. We also propose a new space partition strategy to reduce the practical running time and the space overhead of this algorithm. Experimental results on a variety of test instances show that our proposed algorithm performs better than the existing state-of-the-art algorithm especially on point sets with cliff or other irregular properties.