Runtime Analysis for the NSGA-II: Proving, Quantifying, and Explaining the Inefficiency For Many Objectives. (arXiv:2211.13084v3 [cs.NE] UPDATED)

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).

DoctorMorDi

DoctorMorDi

Moderator and Editor