# Plus Strategies are Exponentially Slower for Planted Optima of Random Height

arXiv: https://arxiv.org/abs/2404.09687 · HTML: https://mlsanity.com/paper/2404.09687/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 31 references that are in the map.
- First posted on arXiv 15 Apr 2024.

## Builds on (most cited first, 11 of 11)

- [Fast Genetic Algorithms](https://mlsanity.com/paper/1703.03334/) (2017)
- [Does Comma Selection Help To Cope With Local Optima](https://mlsanity.com/paper/2004.01274/) (2020)
- [Comma Selection Outperforms Plus Selection on OneMax with Randomly Planted Optima](https://mlsanity.com/paper/2304.09712/) (2023)
- [Self-Adjusting Population Sizes for Non-Elitist Evolutionary Algorithms: Why Success Rates Matter](https://mlsanity.com/paper/2104.05624/) (2021)
- [Drift Analysis and Evolutionary Algorithms Revisited](https://mlsanity.com/paper/1608.03226/) (2016)
- [Self-adjusting Population Sizes for the (1, λ)-EA on Monotone Functions](https://mlsanity.com/paper/2204.00531/) (2022)
- [The Efficiency Threshold for the Offspring Population Size of the (μ, λ) EA](https://mlsanity.com/paper/1904.06981/) (2019)
- [Theoretical Study of Optimizing Rugged Landscapes with the cGA](https://mlsanity.com/paper/2211.13801/) (2022)
- [Tight Runtime Bounds for Static Unary Unbiased Evolutionary Algorithms on Linear Functions](https://mlsanity.com/paper/2302.12338/) (2023)
- [OneMax is not the Easiest Function for Fitness Improvements](https://mlsanity.com/paper/2204.07017/) (2022)
- [Hardest Monotone Functions for Evolutionary Algorithms](https://mlsanity.com/paper/2311.07438/) (2023)

## Built on by (most cited first, 1 of 1)

- [EvoPress: Accurate Dynamic Model Compression via Evolutionary Search](https://mlsanity.com/paper/2410.14649/) (2024)

## Abstract (arXiv)

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(nlog 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.