A First Runtime Analysis of the NSGA-II on a Multimodal Problem
| Autor: | Benjamin Doerr, Zhongdi Qu |
|---|---|
| Rok vydání: | 2023 |
| Předmět: |
FOS: Computer and information sciences
Artificial Intelligence (cs.AI) Computational Theory and Mathematics Computer Science - Artificial Intelligence Optimization and Control (math.OC) Computer Science - Data Structures and Algorithms FOS: Mathematics Computer Science - Neural and Evolutionary Computing Data Structures and Algorithms (cs.DS) Neural and Evolutionary Computing (cs.NE) Mathematics - Optimization and Control Software Theoretical Computer Science |
| Zdroj: | IEEE Transactions on Evolutionary Computation. :1-1 |
| ISSN: | 1941-0026 1089-778X |
| DOI: | 10.1109/tevc.2023.3250552 |
| Popis: | Very recently, the first mathematical runtime analyses of the multi-objective evolutionary optimizer NSGA-II have been conducted. We continue this line of research with a first runtime analysis of this algorithm on a benchmark problem consisting of two multimodal objectives. We prove that if the population size $N$ is at least four times the size of the Pareto front, then the NSGA-II with four different ways to select parents and bit-wise mutation optimizes the OneJumpZeroJump benchmark with jump size~$2 \le k \le n/4$ in time $O(N n^k)$. When using fast mutation, a recently proposed heavy-tailed mutation operator, this guarantee improves by a factor of $k^{\Omega(k)}$. Overall, this work shows that the NSGA-II copes with the local optima of the OneJumpZeroJump problem at least as well as the global SEMO algorithm. Comment: To appear in the Transactions on Evolutionary Computation. Extended version of a paper that appeared in the proceedings of PPSN 2022 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|