Lazy Greedy Hypervolume Subset Selection from Large Candidate Solution Sets
This work addresses a performance bottleneck in multi-objective optimization for researchers and practitioners dealing with large datasets, though it is incremental as it builds on existing greedy methods.
The paper tackles the computational inefficiency of greedy hypervolume subset selection for large candidate sets by proposing a lazy greedy algorithm that exploits submodularity to avoid unnecessary calculations, resulting in speedups of hundreds of times compared to the original algorithm and several times faster than the fastest known method.
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.