论文标题
NSGA-II的运行时分析：跨界的可证明的加速
Runtime Analysis for the NSGA-II: Provable Speed-Ups From Crossover
论文作者
论文摘要
最近，已经进行了NSGA-II的第一个数学运行时分析，这是最常见的多目标进化算法。继续进行这一研究方向，我们证明NSGA-II在使用交叉时渐近渐近地优化了OnejumpZeroJump基准测试。连同NSGA-II证明，这是Dang，Opris，Salehi和Sudholt的平行独立作品，这是跨界的第一次优势。我们的论点可以转移到单目标优化。然后，他们证明，交叉可以以不同的方式加快$（μ+1）$遗传算法的速度，并且比以前更为明显。我们的实验证实了交叉的附加值，并表明观察到的优势甚至比我们的证明所能保证的要大。
Very recently, the first mathematical runtime analyses for the NSGA-II, the most common multi-objective evolutionary algorithm, have been conducted. Continuing this research direction, we prove that the NSGA-II optimizes the OneJumpZeroJump benchmark asymptotically faster when crossover is employed. Together with a parallel independent work by Dang, Opris, Salehi, and Sudholt, this is the first time such an advantage of crossover is proven for the NSGA-II. Our arguments can be transferred to single-objective optimization. They then prove that crossover can speed up the $(μ+1)$ genetic algorithm in a different way and more pronounced than known before. Our experiments confirm the added value of crossover and show that the observed advantages are even larger than what our proofs can guarantee.
