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$-\textsc{LeadingOnesTrailingZeros} ($d$-LOTZ), $d$-\textsc{CountingOnesCountingZeros} ($d$-COCZ), $d$-\textsc{OneMinMax} ($d$-OMM), and $d$-\textsc{OneJumpZeroJump} ($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 m