The NSGA-II is one of the most prominent algorithms to solve multi-objective optimization problems. Despite numerous successful applications and, very recently, also competitive mathematical performance guarantees, 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 prove 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. 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算法的运行时分析：多目标问题的低效性证明、量化与解释