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(k2n). 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.