@inproceedings{dc4298645ce040b6a626f1b8bcc67fe2,
title = "Hot off the Press: From Understanding the Population Dynamics of the NSGA-II to the First Proven Lower Bounds",
abstract = "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 Ω(Nnlogn) function evaluations to find the Pareto front of the OneMinMax problem and Ω(Nnk) 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.",
keywords = "NSGA-II, multi-objective optimization, multimodal problems, runtime analysis, theory",
author = "Benjamin Doerr and Zhondi Qu",
note = "Publisher Copyright: {\textcopyright} 2023 Copyright held by the owner/author(s).; 2023 Genetic and Evolutionary Computation Conference Companion, GECCO 2023 Companion ; Conference date: 15-07-2023 Through 19-07-2023",
year = "2023",
month = jul,
day = "15",
doi = "10.1145/3583133.3595840",
language = "English",
series = "GECCO 2023 Companion - Proceedings of the 2023 Genetic and Evolutionary Computation Conference Companion",
publisher = "Association for Computing Machinery, Inc",
pages = "17--18",
booktitle = "GECCO 2023 Companion - Proceedings of the 2023 Genetic and Evolutionary Computation Conference Companion",
}