A First Runtime Analysis of NSGA-III on a Many-Objective Multimodal Problem: Provable Exponential Speedup via Stochastic Population Update

The NSGA-III is a prominent algorithm in evolutionary many-objective optimization. It is well-suited for optimizing functions with more than three objectives, setting it apart from the classic NSGA-II. However, theoretical insights about NSGA-III of when and why it performs well are still in its early development. This paper addresses this point and conducts a rigorous runtime analysis of NSGA-III on the many-objective OneJumpZeroJump benchmark (OJZJ for short), providing runtime bounds where the number of objectives is constant. We show that NSGA-III finds the Pareto front of OJZJ in time O(n^(k+d/2)+ N n ln(n)) where n is the problem size, d is the number of objectives, k is the gap size, a problem specific parameter, if its population size N is in 2^(O(n)) and at least (2n/d+1)^(d/2). Notably, NSGA-III is faster than NSGA-II by a factor of N/n^(d/2) for N=omega(n^(d/2)) . We also show that a stochastic population update provably guarantees a speedup of order (k/b)^(k-1) in the runtime where b>0 is a constant. Besides a paper of Wietheger and Doerr (PPSN 2024), this is the first rigorous runtime analysis of NSGA-III on OJZJ. Proving these bounds requires a much deeper understanding of the population dynamics of NSGA-III than previous papers achieved.