论文标题
关于多模式问题的NSGA-II的第一个运行时间分析
A First Runtime Analysis of the NSGA-II on a Multimodal Problem
论文作者
论文摘要
最近，已经进行了多目标进化优化器NSGA-II的第一个数学运行时分析。我们通过对由两个多模式目标组成的基准问题进行了对该算法的第一个运行时分析，继续进行这一研究。我们证明，如果人口尺寸$ n $至少是帕累托阵线的四倍，则使用四种不同方法的NSGA-II选择父母和位突变，可以优化OneJumpZeroJump基准，其跳高大小〜$ 2 \ le K \ le K \ le K \ le n/4 $ in time $ o（N n n n^k）$。当使用快速突变（最近提出的重型突变算子）时，此保证将提高$ k^{ω（k）} $。总体而言，这项工作表明，NSGA-II至少与全球SEMO算法有关OnejumpZerojump问题的局部优势。
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.
