Runtime Analyses of NSGA-III on Many-Objective Problems
Files
(Published version)
Date
2024
Authors
Opris, A.
Dang, D.-C.
Neumann, F.
Sudholt, D.
Editors
Li, X.
Handl, J.
Handl, J.
Advisors
Journal Title
Journal ISSN
Volume Title
Type:
Conference paper
Citation
Proceedings of the Genetic and Evolutionary Computation Conference (GECCO, 2024), 2024 / Li, X., Handl, J. (ed./s), pp.1596-1604
Statement of Responsibility
Andre Opris, Duc-Cuong Dang, Frank Neumann, Dirk Sudholt
Conference Name
Genetic and Evolutionary Computation Conference (GECCO) (14 Jul 2024 - 18 Jul 2024 : Melbourne, Victoria Australia and Virtual Online)
Abstract
NSGA-II and NSGA-III are two of the most popular evolutionary multi-objective algorithms used in practice. While NSGA-II is used for few objectives such as 2 and 3, NSGA-III is designed to deal with a larger number of objectives. In a recent breakthrough, Wietheger and Doerr (IJCAI 2023) gave the first runtime analysis for NSGA-III on the 3-objective OneMinMax problem, showing that this stateof-the-art algorithm can be analyzed rigorously. We advance this new line of research by presenting the first runtime analyses of NSGA-III on the popular many-objective benchmark problems 𝑚-LOTZ, 𝑚-OMM, and 𝑚-COCZ, for an arbitrary constant number 𝑚 of objectives. Our analysis provides ways to set the important parameters of the algorithm: the number of reference points and the population size, so that a good performance can be guaranteed. We show how these parameters should be scaled with the problem dimension, the number of objectives and the fitness range. To our knowledge, these are the first runtime analyses for NSGA-III for more than 3 objectives.
School/Discipline
Dissertation Note
Provenance
Description
Access Status
Rights
© 2024 Copyright held by the owner/author(s). This work is licensed under a Creative Commons Attribution-NonCommercial International 4.0 License.