Hot off the Press: Runtime Analysis of the SMS-EMOA for Many-Objective Optimization

The NSGA-II was recently proven to have difficulties in many-objective optimization. In contrast, the literature experimentally shows a good performance of the SMS-EMOA, which can be seen as a steady-state NSGA-II that uses the hypervolume contribution instead of the crowding distance as the second selection criterion.This paper conducts the first rigorous runtime analysis of the SMS-EMOA for many-objective optimization. To this aim, we first propose a many-objective counterpart, the m-objective mOJZJ problem, of the bi-objective OneJumpZeroJump benchmark, which is the first many-objective multimodal benchmark used in a mathematical runtime analysis. We prove that SMS-EMOA computes the full Pareto front of this benchmark in an expected number of O(M2nk) iterations, where n denotes the problem size (length of the bit-string representation), k the gap size (a difficulty parameter of the problem), and M = (2n/m - 2k + 3)m/2 the size of the Pareto front. This result together with the existing negative result on the original NSGA-II shows that in principle, the general approach of the NSGA-II is suitable for many-objective optimization, but the crowding distance as tie-breaker has deficiencies.We obtain three additional insights on the SMS-EMOA. Different from a recent result for the bi-objective OneJumpZeroJump benchmark, the stochastic population update often does not help for mOJZJ. It results in a l/Θ(min{Mk1/2/2k/2, 1}) speed-up, which is Θ(1) for large m such as m > k. On the positive side, we prove that heavy-tailed mutation still results in a speed-up of order kk+0.5 - β. Finally, we conduct the first runtime analyses of the SMS-EMOA on the bi-objective OneMinMax and LOTZ benchmarks and show that it has a performance comparable to the GSEMO and the NSGA-II.This paper for the Hot-off-the-Press track at GECCO 2024 summarizes the work Weijie Zheng, Benjamin Doerr: Runtime Analysis of the SMS-EMOA for Many-Objective Optimization. AAAI 2024, 20874 - 20882 [20].