.png){kind=icon}
Return
A box decomposition algorithm to compute the hypervolume indicator
.png){kind=icon}
OA
AI
DOI：10.1016/j.cor.2016.06.021.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
We propose a new approach to the computation of the hypervolume indicator, based on partitioning the dominated region into a set of axis-parallel hyperrectangles or boxes. We present a nonincremental algorithm and an incremental algorithm, which allows insertions of points, whose time complexities are O(n[p-1/2]+1) and O(n[p/2]+1), respectively, where n is the number of points and p is the dimension of the objective space. While the theoretical complexity of such a method is lower bounded by the complexity of the partition, which is, in the worst-case, larger than the best upper bound on the complexity of the hypervolume computation, we show that it is practically efficient. In particular, the nonincremental algorithm competes with the currently most practically efficient algorithms. Finally, we prove an enhanced upper bound of O(n(P-1)) and a lower bound of Omega(n[p/2]logn) for p >= 4 on the worst-case complexity of the WFG algorithm. (C) 2016 Elsevier Ltd. All rights reserved.
Keywords:
Multi-objective optimization
Hypervolume indicator
Klee's measure problem
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
C
IF:
4.3
Papers:
6.5K
Citations:
1.8W
Organization
Cited Papers
.png){kind=icon}
ShareSaveShareSave
ShareSave
View more