Runtime Analysis for the NSGA-II: Provable Speed-Ups From Crossover
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2022
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866917796587241472 |
|---|---|
| author | Doerr, Benjamin Qu, Zhongdi |
| author_facet | Doerr, Benjamin Qu, Zhongdi |
| contents | Very recently, the first mathematical runtime analyses for the NSGA-II, the most common multi-objective evolutionary algorithm, have been conducted. Continuing this research direction, we prove that the NSGA-II optimizes the OneJumpZeroJump benchmark asymptotically faster when crossover is employed. Together with a parallel independent work by Dang, Opris, Salehi, and Sudholt, this is the first time such an advantage of crossover is proven for the NSGA-II. Our arguments can be transferred to single-objective optimization. They then prove that crossover can speed up the $(μ+1)$ genetic algorithm in a different way and more pronounced than known before. Our experiments confirm the added value of crossover and show that the observed advantages are even larger than what our proofs can guarantee. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2208_08759 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Runtime Analysis for the NSGA-II: Provable Speed-Ups From Crossover Doerr, Benjamin Qu, Zhongdi Neural and Evolutionary Computing Artificial Intelligence Data Structures and Algorithms Very recently, the first mathematical runtime analyses for the NSGA-II, the most common multi-objective evolutionary algorithm, have been conducted. Continuing this research direction, we prove that the NSGA-II optimizes the OneJumpZeroJump benchmark asymptotically faster when crossover is employed. Together with a parallel independent work by Dang, Opris, Salehi, and Sudholt, this is the first time such an advantage of crossover is proven for the NSGA-II. Our arguments can be transferred to single-objective optimization. They then prove that crossover can speed up the $(μ+1)$ genetic algorithm in a different way and more pronounced than known before. Our experiments confirm the added value of crossover and show that the observed advantages are even larger than what our proofs can guarantee. |
| title | Runtime Analysis for the NSGA-II: Provable Speed-Ups From Crossover |
| topic | Neural and Evolutionary Computing Artificial Intelligence Data Structures and Algorithms |
| url | https://arxiv.org/abs/2208.08759 |