.png){kind=icon}
返回
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}
分享.png){kind=icon}
收藏
摘要
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.
Keyword:
Multi-objective optimization
Hypervolume indicator
Klee's measure problem
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
C
IF:
4.3
论文数:
6.5K
被引数:
1.8W
机构
引用论文
.png){kind=icon}
分享收藏
查看更多内容