论文标题
非主导分类遗传算法II（NSGA-II）的近似保证
Approximation Guarantees for the Non-Dominated Sorting Genetic Algorithm II (NSGA-II)
论文作者
论文摘要
最近的理论作品表明，当人口大小足够大时，NSGA-II可以有效地计算整个帕累托前沿。在这项工作中，我们研究了当人口规模较小时它近似帕累托阵线的效果。 对于Oneminmax基准，我们指出了父母和后代在帕累托方面很好的情况，但是下一个人口在帕累托阵线上有很大的差距。我们的数学证据表明，这种不良行为的原因是，选择阶段的NSGA-II一次计算一次拥挤距离，然后删除具有最小拥挤距离的个人而不考虑删除会增加某些人的拥挤距离。 然后，我们分析两个不容易发生此问题的变体。对于每次拆除后更新拥挤距离的NSGA-II（Kukkonen and Deb（2006））和稳态NSGA-II（Nebro和Durillo（2009）），我们证明，帕雷托阵线中的差距从来没有比理论最小的小型恒定因子更大。这是关于NSGA-II近似能力和稳态NSGA-II的第一个运行时分析的第一项数学工作。实验还显示了两个NSGA-II变体的优势近似能力。
Recent theoretical works have shown that the NSGA-II efficiently computes the full Pareto front when the population size is large enough. In this work, we study how well it approximates the Pareto front when the population size is smaller. For the OneMinMax benchmark, we point out situations in which the parents and offspring cover well the Pareto front, but the next population has large gaps on the Pareto front. Our mathematical proofs suggest as reason for this undesirable behavior that the NSGA-II in the selection stage computes the crowding distance once and then removes individuals with smallest crowding distance without considering that a removal increases the crowding distance of some individuals. We then analyze two variants not prone to this problem. For the NSGA-II that updates the crowding distance after each removal (Kukkonen and Deb (2006)) and the steady-state NSGA-II (Nebro and Durillo (2009)), we prove that the gaps in the Pareto front are never more than a small constant factor larger than the theoretical minimum. This is the first mathematical work on the approximation ability of the NSGA-II and the first runtime analysis for the steady-state NSGA-II. Experiments also show the superior approximation ability of the two NSGA-II variants.
