From Understanding the Population Dynamics of the NSGA-II to the First Proven Lower Bounds
This provides foundational theoretical insights for evolutionary multi-objective optimization, addressing a gap in runtime analysis for a widely used algorithm.
The authors tackled the lack of proven lower bounds for the runtime of the NSGA-II algorithm by analyzing its population dynamics, showing it requires Ω(Nn log n) evaluations for the OneMinMax problem and Ω(Nn^k) for the OneJumpZeroJump problem, matching known upper bounds and indicating no benefit from larger population sizes.
Due to the more complicated population dynamics of the NSGA-II, none of the existing runtime guarantees for this algorithm is accompanied by a non-trivial lower bound. Via a first mathematical understanding of the population dynamics of the NSGA-II, that is, by estimating the expected number of individuals having a certain objective value, we prove that the NSGA-II with suitable population size needs $Ω(Nn\log n)$ function evaluations to find the Pareto front of the OneMinMax problem and $Ω(Nn^k)$ evaluations on the OneJumpZeroJump problem with jump size $k$. These bounds are asymptotically tight (that is, they match previously shown upper bounds) and show that the NSGA-II here does not even in terms of the parallel runtime (number of iterations) profit from larger population sizes. For the OneJumpZeroJump problem and when the same sorting is used for the computation of the crowding distance contributions of the two objectives, we even obtain a runtime estimate that is tight including the leading constant.