Computing and Updating Hypervolume Contributions in Up to Four Dimensions
针对多目标优化中的超体积子集选择问题，提出了三维和四维空间中计算与更新超体积贡献的新算法，显著提升了贪心近似策略的效率。
Arising in connection with multiobjective selection and archiving, the hypervolume subset selection problem (HSSP) consists in finding a subset of size k ≤ n of a set X ⊂ ℝ <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">d</sup> of n nondominated points in d-dimensional space that maximizes the hypervolume indicator. The incremental greedy approximation to the HSSP has an approximation guarantee of 1 - 1/e, and is polynomial in n and k, while no polynomial exact algorithms are known for d ≥ 3. The decremental greedy counterpart has no known approximation guarantee, but is potentially faster for large k, and still leads to good approximations in practice. The computation and update of individual hypervolume contributions are at the core of the implementation of this greedy strategy. In this paper, new algorithms for the computation and update of hypervolume contributions are developed. In three dimensions, updating the total hypervolume and all individual contributions under single-point changes is performed in linear time, while in the 4-D case all contributions are computed in O(n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> ) time. As a consequence, the decremental greedy approximation to the HSSP can now be obtained in O(n(n - k) +n log n) and O(n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> (n - k)) time for d = 3 and d = 4, respectively. Experimental results show that the proposed algorithms significantly outperform existing ones.