Fast High-Diversity Subset Selection for Multi-Objective Optimization by Riesz s-Energy

Subset selection is a key task in evolutionary multi-objective optimization. Addressing this combinatorial challenge is key to generating finite μ-point Pareto front approximations (PFAs) that accurately represent the Pareto front, regardless of its geometric shape and dimension. For instance, subset selection is used both in bounded-size archiving and in the environmental selection of an EMO algorithm. A significant challenge remains in designing algorithms for medium-and large-scale subset selection instances such as those that involve unbounded external archives (UEA). In this article, we propose two efficient algorithms based on Riesz s-energy (RSE). These algorithms employ two main strategies: greedy inclusion and iterative replacement, exhibiting linear time and space complexity for medium-and large-scale subset selection instances. Our experimental results show that our RSE-based algorithms produce target subsets with high diversity at a low processing time, outperforming six state-of-the-art subset selection algorithms. Additionally, we validated their effectiveness in extracting a representative PFA from a UEA connected to a multi-objective evolutionary algorithm, producing well-diversified subsets regardless of the Pareto front geometry and its dimension.