A First Runtime Analysis of the NSGA-II on a Multimodal Problem

Very recently, the first mathematical runtime analyses of the multiobjective evolutionary optimizer nondominated sorting genetic algorithm II (NSGA-II) have been conducted. We continue this line of research with a first runtime analysis of this algorithm on a benchmark problem consisting of multimodal objectives. We prove that if the population size <tex-math notation="LaTeX">N </tex-math> is at least four times the size of the Pareto front, then the NSGA-II with four standard ways to select parents, bitwise mutation, and crossover with rate less than one, optimizes the OneJumpZeroJump benchmark with jump size <tex-math notation="LaTeX">2 ≤ k ≤ n/4 </tex-math> in time <tex-math notation="LaTeX">O(N nᵏ) </tex-math> . When using fast mutation instead of bitwise mutation this guarantee improves by a factor of <tex-math notation="LaTeX">kΩ (k) </tex-math> . Overall, this work shows that the NSGA-II copes with the local optima of the OneJumpZeroJump problem at least as well as the global SEMO algorithm.