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

Benjamin Doerr; Zhongdi Qu

doi:10.1109/TEVC.2023.3250552

paper

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

arXiv:2204.13750 · doi:10.1109/TEVC.2023.3250552

Abstract

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 \leq k \leq 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.

Appeared in the Transactions on Evolutionary Computation. Extends a paper that appeared in the Proceedings of PPSN 2022

References in corpus (1)

Stagnation Detection with Randomized Local Search

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

Abstract

References in corpus (1)

Cited by in corpus (13)