Fast High-Diversity Subset Selection for Multiobjective Optimization by Riesz s -Energy
针对多目标优化中的子集选择难题，提出两种基于Riesz s-能量的高效算法，能在线性时空复杂度下生成高多样性的帕累托前沿近似子集，适用于中大规模实例。
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.