Hot off the Press: Runtime Analysis for State-of-the-Art Multi-objective Evolutionary Algorithms on the Subset Selection Problem

In the last few years, the mathematical runtime analysis of randomized search heuristics has made a huge step forward by analyzing the most prominent multi-objective evolutionary algorithms (MOEAs). These results confirmed that many previous results for synthetic MOEAs extend to state-of-the-art MOEAs, but also exhibited some unexpected difficulties not seen with simple MOEAs. We continue this line of research by analyzing how the NSGA-II and the SMS-EMOA (also with a recently proposed stochastic population update) solve the NP-hard subset selection problem. For these two state-of-the-art algorithms, we prove performance guarantees that agree with those previously shown for the POSS algorithm, a variant of the simplistic GSEMO, namely that they compute (1 − e^−γ)-approximate solutions in expected time O(k²n). Our experiments confirm these findings. This work is the first runtime analysis of state-of-the-art MOEAs for the subset selection problem, and also the first runtime analysis of SMS-EMOA on a combinatorial problem. This paper for the hot-off-the-press track at GECCO 2025 summarizes the work Renzhong Deng, Weijie Zheng, Mingfeng Li, Jie Liu, and Benjamin Doerr: Runtime analysis for state-of-the-art multiobjective evolutionary algorithms on the subset selection problem. Parallel Problem Solving from Nature, PPSN 2024. Springer, 264–279. 10.1007/978-3-031-70071-2_17 [8].