论文标题
大型候选解决方案集的懒惰贪婪的超量子集选择
Lazy Greedy Hypervolume Subset Selection from Large Candidate Solution Sets
论文作者
论文摘要
近年来，子集选择是一个流行的主题，已经提出了许多子集选择方法。在这些方法中，超量体子集选择被广泛使用。贪婪的超量子集选择算法可以实现与最佳子集的良好近似值。但是，当候选人集很大时（例如，具有大量解决方案的无限外部存档）时，该算法非常耗时。在本文中，我们提出了一种新的懒惰贪婪算法，利用了Hypervolume指示器的supporular属性。核心思想是在找到最大贡献的解决方案时避免不必要的高频贡献计算。实验结果表明，所提出的算法比原始的贪婪包容算法快几百倍，并且在许多测试问题上比最快的已知贪婪包容算法快几倍。
Subset selection is a popular topic in recent years and a number of subset selection methods have been proposed. Among those methods, hypervolume subset selection is widely used. Greedy hypervolume subset selection algorithms can achieve good approximations to the optimal subset. However, when the candidate set is large (e.g., an unbounded external archive with a large number of solutions), the algorithm is very time-consuming. In this paper, we propose a new lazy greedy algorithm exploiting the submodular property of the hypervolume indicator. The core idea is to avoid unnecessary hypervolume contribution calculation when finding the solution with the largest contribution. Experimental results show that the proposed algorithm is hundreds of times faster than the original greedy inclusion algorithm and several times faster than the fastest known greedy inclusion algorithm on many test problems.
