论文标题
非主导分类遗传算法III（NSGA-III）的数学运行时分析
A Mathematical Runtime Analysis of the Non-dominated Sorting Genetic Algorithm III (NSGA-III)
论文作者
论文摘要
非主导的排序遗传算法II（NSGA-II）是现实世界应用最突出的多目标进化算法。尽管它在双目标优化问题上显然表现良好，但经验研究表明，当应用于两个以上目标的问题时，它的效率较低。最近的数学运行时分析证实了这一观察结果，证明了NGSA-II的指数数量迭代数量错过了简单的3个目标oneminmax问题的帕累托正面的恒定因素。 在这项工作中，我们提供了NSGA-III的第一个数学运行时分析，这是NSGA-II的改进，旨在更好地处理两个以上的目标。我们证明，具有足够多的参考点的NSGA-III（如该算法所建议的那样，一个小于帕累托前部的尺寸都要多的恒定因子 - 计算了3个目标OneMinmax基准标准的完整帕累托前部，以预期的O（n log n）迭代的预期数量。该结果适用于所有人口规模（至少是帕累托阵线的大小）。它显示了NSGA-III比该基准测试的NSGA-II的巨大优势。 NSGA-II的先前工作中使用的数学论点表明，对于具有三个或更多目标的其他基准测试标准也可能是类似的发现。
The Non-dominated Sorting Genetic Algorithm II (NSGA-II) is the most prominent multi-objective evolutionary algorithm for real-world applications. While it performs evidently well on bi-objective optimization problems, empirical studies suggest that it is less effective when applied to problems with more than two objectives. A recent mathematical runtime analysis confirmed this observation by proving the NGSA-II for an exponential number of iterations misses a constant factor of the Pareto front of the simple 3-objective OneMinMax problem. In this work, we provide the first mathematical runtime analysis of the NSGA-III, a refinement of the NSGA-II aimed at better handling more than two objectives. We prove that the NSGA-III with sufficiently many reference points -- a small constant factor more than the size of the Pareto front, as suggested for this algorithm -- computes the complete Pareto front of the 3-objective OneMinMax benchmark in an expected number of O(n log n) iterations. This result holds for all population sizes (that are at least the size of the Pareto front). It shows a drastic advantage of the NSGA-III over the NSGA-II on this benchmark. The mathematical arguments used here and in previous work on the NSGA-II suggest that similar findings are likely for other benchmarks with three or more objectives.
