.png){kind=icon}
.png){kind=icon}
Return
A Fast Exact Algorithm for Computing the Hypervolume Contributions in 4-D Space
.png){kind=icon}
PRE
AI
DOI：10.1109/TEVC.2023.3271679.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
The hypervolume (HV) contribution is widely used in indicator-based multiobjective algorithms. We propose an algorithm to compute exact 4-D HV contributions for a set of O(n([3/2])logn) time. Our algorithm improves the currently best time complexity O(n(2))byO(root n/logn) , 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.
Keywords:
Hypervolume (HV) contribution
Klee's measure problem (KMP)
multiobjective optimization
space partition method
Hypervolume (HV) contribution
Klee's measure problem (KMP)
multiobjective optimization
space partition method
Journal
IF:
12
Papers:
1.8K
Citations:
2.4W