The NSGA-II is one of the most prominent algorithms to solve multi-objective optimization problems. Despite numerous successful applications, several studies have shown that the NSGA-II is less effective for larger numbers of objectives. In this work, we use mathematical runtime analyses to rigorously demonstrate and quantify this phenomenon. We show that even on the simple OneMinMax benchmark, where every solution is Pareto optimal, the NSGA-II also with large population sizes cannot compute the full Pareto front (objective vectors of all Pareto optima) in sub-exponential time when the number of objectives is at least three. Our proofs suggest that the reason for this unexpected behavior lies in the fact that in the computation of the crowding distance, the different objectives are regarded independently. This is not a problem for two objectives, where any sorting of a pair-wise incomparable set of solutions according to one objective is also such a sorting according to the other objective (in the inverse order).
翻译:NSGA- II是解决多目标优化问题最突出的算法之一。 尽管许多应用都取得了成功, 但有几项研究显示NSGA- II对于更多的目标效果不大。 在这项工作中, 我们使用数学运行时间分析来严格地展示和量化这一现象。 我们显示, 即使在简单的 Oneminmax 基准上, 每一个解决方案都是Pareto 最佳的, NSGA- II 也是人口规模庞大的, 在目标数量至少为三个的亚爆炸性时间里, 无法计算整个Pareto front( 全部Paretoopima的目标矢量) 。 我们的证据表明, 这种意外行为的原因在于在计算挤动距离时, 不同的目标被独立地看待。 对于两个目标来说, 这不是一个问题, 任何按照一个目标对称不相匹配的一套解决方案的分类, 都无法按照另一个目标进行如此分类( 逆序 ) 。