Many Objective Problems Where Crossover is Provably Essential

This article addresses theory in evolutionary many-objective optimization and focuses on the role of crossover operators. The advantages of using crossover are hardly understood and rigorous runtime analyses with crossover are lagging far behind its use in practice, specifically in the case of more than two objectives. We present two many-objective problems $RR_{\text{RO}}$ and $uRR_{\text{RO}}$ together with a theoretical runtime analysis of the GSEMO and the widely used NSGA-III algorithm to demonstrate that one point crossover on $RR_{\text{RO}}$, as well as uniform crossover on $uRR_{\text{RO}}$, can yield an exponential speedup in the runtime. In particular, when the number of objectives is constant, this algorithms can find the Pareto set of both problems in expected polynomial time when using crossover while without crossover they require exponential time to even find a single Pareto-optimal point. For both problems, we also demonstrate a significant performance gap in certain superconstant parameter regimes for the number of objectives. To the best of our knowledge, this is one of the first rigorous runtime analysis in many-objective optimization which demonstrates an exponential performance gap when using crossover for more than two objectives. Additionally, it is the first runtime analysis involving crossover in many-objective optimization where the number of objectives is not necessarily constant.