Near-Tight Runtime Guarantees for Many-Objective Evolutionary Algorithms

尽管在多目标进化算法（MOEAs）的数学运行时分析领域取得了重大进展，但MOEAs在离散的多目标问题上的表现仍不为人所知。特别是，针对经典基准测试的SEMO、全局SEMO和SMS-EMOA算法的少量现有界限都大致呈二次函数形式，与帕累托前沿的大小成正比。在本研究中，我们证明了这三种算法在任意数量目标的四种最常见基准测试问题（OneMinMax、CountingOnesCountingZeros、LeadingOnesTrailingZeros和OneJumpZeroJump）上的运行时间保证接近最优，仅与帕累托前沿的大小成线性关系，表明这些基准测试上的MOEAs在处理多目标问题时比以前的研究所认为的要好得多。我们的界限除了目标数量和位串长度的小多项式因子外是紧密的。这是第一次为这些MOEAs的多目标使用证明如此紧密的界限。虽然已知这样的结果对于NSGA-II是不成立的，但我们确实通过最近的结构结果展示了我们的界限是可转移到NSGA-III算法的。

论文试图解决多目标进化算法在离散问题上的性能问题，特别是对于经典基准测试的运行时间分析的缺乏。

论文提出了SEMO、Global SEMO和SMS-EMOA算法在四个常见基准测试问题上的近乎最紧密的运行时间保证，并且这适用于任意数量的目标。这些算法在许多目标方面的表现比以前的研究所示的要好得多，这些算法的运行时间保证仅与Pareto前沿的大小成线性关系。

论文的实验设计了多个数据集，并且提供了开源代码。此外，论文还展示了这些算法的运行时间保证可以通过最近的结构结果转换为NSGA-III算法。

最近的相关研究包括：'A Fast and Elitist Multi-Objective Genetic Algorithm: NSGA-II'，'NSGA-III: A Dominance-Based Multi-Objective Genetic Algorithm'等。