Runtime Analyses of NSGA-III on Many-Objective Problems: Provable Exponential Speedup via Stochastic Population Update

NSGA-III is a prominent algorithm in evolutionary many-objective optimization. It is particularly well suited for optimizing problems with more than three objectives, distinguishing it from the classical NSGA-II. However, theoretical understanding of when and why NSGA-III performs well is still at an early stage. In this paper, we contribute to closing this gap by conducting rigorous runtime analyses on the classical many-objective benchmark problems d-textscLeadingOnesTrailingZeros (d-LOTZ), d-textscCountingOnesCountingZeros (d-COCZ), d-textscOneMinMax (d-OMM), and d-textscOneJumpZeroJump (d-OJZJ) for arbitrary numbers of objectives d. In particular, we improve upon previous results when the population size is asymptotically larger than the size of the Pareto front. Notably, in the bi-objective case, the derived upper runtime bounds are asymptotically tighter than those known for NSGA-II. For the problems 2-OMM and 2-OJZJ, NSGA-III even outperforms NSGA-II in terms of expected runtime for suitable population sizes μ. Further, we show that a stochastic population update mechanism provably yields an exponential speedup in the expected runtime on many-objective multimodal problems such as d-OJZJ, as well as on the function d-textscRRMO, a many-objective variant of the Real-Royal-Road function, for certain parameter regimes. To complement our analysis, we also establish tight runtime bounds for NSGA-III on 2-textscOJZJ and 4-textscOJZJ. In particular, the result for 4-OJZJ provides, to the best of our knowledge, the first lower bound for NSGA-III on a classical benchmark problem with more than two objectives. Deriving these bounds requires a substantially deeper analysis of the population dynamics of NSGA-III than has been achieved in previous work.