Self-Adjusting Evolutionary Algorithms Are Slow on Multimodal Landscapes
<|reference_start|>Self-Adjusting Evolutionary Algorithms Are Slow on Multimodal Landscapes: The one-fifth rule and its generalizations are a classical parameter control mechanism in discrete domains. They have also been transferred to control the offspring population size of the $(1, \lambda)$-EA. This has been shown to work very well for hill-climbing, and combined with a restart mechanism it was recently shown by Hevia Fajardo and Sudholt to improve performance on the multi-modal problem Cliff drastically.   In this work we show that the positive results do not extend to other types of local optima. On the distorted OneMax benchmark, the self-adjusting $(1, \lambda)$-EA is slowed down just as elitist algorithms because self-adaptation prevents the algorithm from escaping from local optima. This makes the self-adaptive algorithm considerably worse than good static parameter choices, which do allow to escape from local optima efficiently. We show this theoretically and complement the result with empirical runtime results.<|reference_end|>
@article{lengler2024self-adjusting,
    title={Self-Adjusting Evolutionary Algorithms Are Slow on Multimodal Landscapes},
    author={Johannes Lengler, Konstantin Sturm},
    journal={arXiv preprint arXiv:2404.12047},
    year={2024},
    archivePrefix={arXiv},
    eprint={2404.12047},
    primaryClass={cs.NE}
}