On the Impact of Crossover in Many-Objective Optimization: A Runtime Analysis of NSGA-III
For researchers in multi-objective optimization, this work offers the first theoretical proof that crossover can provably accelerate many-objective optimization beyond specially designed benchmarks.
The paper provides a theoretical runtime analysis of NSGA-III on the m-Objective m-OneJumpZeroJump problem, showing that crossover leads to asymptotic speedups for any number of objectives in large parameter regimes. It also provides a lower bound for the 4-objective case without crossover.
In recent years, a theoretical understanding has rapidly advanced regarding how popular multi-objective evolutionary algorithms (MOEAs) can optimize many-objective problems. However, the benefits of using crossover in many-objective optimization are theoretically not understood, except for specifically designed benchmark functions tuned to particular crossover operators, and still lag significantly behind its practical use. In this paper, we build upon this line of research and present a theoretical runtime analysis of the widely used NSGA-III algorithm on the classical $m$-objective $m$-OneJumpZeroJump function ($m$-OJZJ for short). Our results demonstrate that NSGA-III with crossover optimizes $m$-OJZJ asymptotically faster than NSGA-III without crossover for any number $m$ of objectives for huge parameter regimes. We complement our analysis by providing a lower runtime bound on $4$-OJZJ when crossover is turned off.