Plus Strategies are Exponentially Slower for Planted Optima of Random Height
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911840248791040 |
|---|---|
| author | Lengler, Johannes Schiller, Leon Sieberling, Oliver |
| author_facet | Lengler, Johannes Schiller, Leon Sieberling, Oliver |
| contents | We compare the $(1,λ)$-EA and the $(1 + λ)$-EA on the recently introduced benchmark DisOM, which is the OneMax function with randomly planted local optima. Previous work showed that if all local optima have the same relative height, then the plus strategy never loses more than a factor $O(n\log n)$ compared to the comma strategy. Here we show that even small random fluctuations in the heights of the local optima have a devastating effect for the plus strategy and lead to super-polynomial runtimes. On the other hand, due to their ability to escape local optima, comma strategies are unaffected by the height of the local optima and remain efficient. Our results hold for a broad class of possible distortions and show that the plus strategy, but not the comma strategy, is generally deceived by sparse unstructured fluctuations of a smooth landscape. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_09687 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Plus Strategies are Exponentially Slower for Planted Optima of Random Height Lengler, Johannes Schiller, Leon Sieberling, Oliver Neural and Evolutionary Computing Artificial Intelligence Probability We compare the $(1,λ)$-EA and the $(1 + λ)$-EA on the recently introduced benchmark DisOM, which is the OneMax function with randomly planted local optima. Previous work showed that if all local optima have the same relative height, then the plus strategy never loses more than a factor $O(n\log n)$ compared to the comma strategy. Here we show that even small random fluctuations in the heights of the local optima have a devastating effect for the plus strategy and lead to super-polynomial runtimes. On the other hand, due to their ability to escape local optima, comma strategies are unaffected by the height of the local optima and remain efficient. Our results hold for a broad class of possible distortions and show that the plus strategy, but not the comma strategy, is generally deceived by sparse unstructured fluctuations of a smooth landscape. |
| title | Plus Strategies are Exponentially Slower for Planted Optima of Random Height |
| topic | Neural and Evolutionary Computing Artificial Intelligence Probability |
| url | https://arxiv.org/abs/2404.09687 |