How Population Diversity Influences the Efficiency of Crossover
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916212505575424 |
|---|---|
| author | Cerf, Sacha Lengler, Johannes |
| author_facet | Cerf, Sacha Lengler, Johannes |
| contents | Our theoretical understanding of crossover is limited by our ability to analyze how population diversity evolves. In this study, we provide one of the first rigorous analyses of population diversity and optimization time in a setting where large diversity and large population sizes are required to speed up progress. We give a formal and general criterion which amount of diversity is necessary and sufficient to speed up the $(μ+1)$ Genetic Algorithm on LeadingOnes. We show that the naturally evolving diversity falls short of giving a substantial speed-up for any $μ=O(\sqrt{n}/\log^2 n)$. On the other hand, we show that even for $μ=2$, if we simply break ties in favor of diversity then this increases diversity so much that optimization is accelerated by a constant factor. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_12268 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | How Population Diversity Influences the Efficiency of Crossover Cerf, Sacha Lengler, Johannes Neural and Evolutionary Computing 68W50 Our theoretical understanding of crossover is limited by our ability to analyze how population diversity evolves. In this study, we provide one of the first rigorous analyses of population diversity and optimization time in a setting where large diversity and large population sizes are required to speed up progress. We give a formal and general criterion which amount of diversity is necessary and sufficient to speed up the $(μ+1)$ Genetic Algorithm on LeadingOnes. We show that the naturally evolving diversity falls short of giving a substantial speed-up for any $μ=O(\sqrt{n}/\log^2 n)$. On the other hand, we show that even for $μ=2$, if we simply break ties in favor of diversity then this increases diversity so much that optimization is accelerated by a constant factor. |
| title | How Population Diversity Influences the Efficiency of Crossover |
| topic | Neural and Evolutionary Computing 68W50 |
| url | https://arxiv.org/abs/2404.12268 |