A First Runtime Analysis of the NSGA-II on a Multimodal Problem
This work offers incremental theoretical insights for researchers in evolutionary computation by analyzing NSGA-II's performance on a specific multimodal problem, comparing it to existing algorithms.
The paper provides the first runtime analysis of the NSGA-II algorithm on a multimodal benchmark problem with two objectives, proving it optimizes the OneJumpZeroJump problem in time O(N n^k) under certain conditions, and shows improvement with fast mutation by a factor of k^{Ω(k)}.
Very recently, the first mathematical runtime analyses of the multi-objective evolutionary optimizer 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 two multimodal objectives. We prove that if the population size $N$ is at least four times the size of the Pareto front, then the NSGA-II with four different ways to select parents and bit-wise mutation optimizes the OneJumpZeroJump benchmark with jump size~$2 \le k \le n/4$ in time $O(N n^k)$. When using fast mutation, a recently proposed heavy-tailed mutation operator, this guarantee improves by a factor of $k^{Ω(k)}$. 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.