An Improved Dimension-Sweep Algorithm for the Hypervolume Indicator

1.摘要

本文提出了一种递归的维数扫描算法，用于计算d>2维的n个非支配点质量的超体积指标。 通过对递归树进行剪枝，改进了现有的HSO (Hypervolume by Slicing Objectives)算法，避免了重复的支配检查和部分超体积的重新计算。 此外，它还结合了三维特例的最新结果。 该算法在最坏情况下达到了 O ( n d − 2 l o g n ) O(n^{d-2}logn) O(nd−2logn)时间和线性空间复杂度，但实验结果表明，所采用的剪枝技术可以进一步降低时间复杂度指数。