论文标题
NSGA-II的运行时分析：证明，量化和解释许多目标的效率低下
Runtime Analysis for the NSGA-II: Proving, Quantifying, and Explaining the Inefficiency For Many Objectives
论文作者
论文摘要
NSGA-II是解决多目标优化问题的最突出算法之一。尽管有许多成功的应用，但一些研究表明，NSGA-II对大量目标的有效性较差。在这项工作中，我们使用数学运行时分析来严格证明和量化这一现象。我们表明，即使在简单的$ m $ m $ mobigntive oneminmax基准中，每个解决方案都是Pareto最佳的，NSGA-II也具有较大的人口尺寸，在至少三个目标的数量时，在子指数时间中，在子指数时间内都无法计算完整的Pareto前部（所有Pareto Optima的目标向量）。这种出乎意料的行为的原因在于，在计算拥挤距离的计算中，不同的目标被独立考虑。对于两个目标而言，这不是一个问题，在一个目标中，根据一个目标，对成对无与伦比的解决方案集也是根据另一个目标（以反顺序）进行分类。
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 $m$-objective generalization of the discrete 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. 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).
