A First Runtime Analysis of the NSGA-II on a Multimodal Problem
分析了NSGA-II在多模态基准问题OneJumpZeroJump上的运行时间，证明当种群规模至少是帕累托前沿大小的四倍时，算法能在多项式时间内找到最优解，且快速变异可显著提升效率。
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 <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$N$ </tex-math></inline-formula> 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 <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$2 \le k \le n/4$ </tex-math></inline-formula> in time <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$O(N n^{k})$ </tex-math></inline-formula> . When using fast mutation instead of bitwise mutation this guarantee improves by a factor of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$k^{\Omega (k)}$ </tex-math></inline-formula> . 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.