# Stagnation Detection in Highly Multimodal Fitness Landscapes

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Apr 2021.

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

- [A First Runtime Analysis of the NSGA-II on a Multimodal Problem](https://mlsanity.com/paper/2204.13750/) (2022)
- [Lazy Parameter Tuning and Control: Choosing All Parameters Randomly From a Power-Law Distribution](https://mlsanity.com/paper/2104.06714/) (2021)
- [How the Move Acceptance Hyper-Heuristic Copes With Local Optima: Drastic Differences Between Jumps and Cliffs](https://mlsanity.com/paper/2304.10414/) (2023)
- [An Extended Jump Functions Benchmark for the Analysis of Randomized Search Heuristics](https://mlsanity.com/paper/2105.03090/) (2021)
- [Towards a Stronger Theory for Permutation-based Evolutionary Algorithms](https://mlsanity.com/paper/2204.07637/) (2022)
- [How Well Does the Metropolis Algorithm Cope With Local Optima?](https://mlsanity.com/paper/2304.10848/) (2023)
- [Selection Hyper-heuristics Can Automatically Adjust the Learning Period to Optimally Solve Pseudo-Boolean Problems](https://mlsanity.com/paper/2605.29916/) (2026)
- [Runtime Analysis for Permutation-based Evolutionary Algorithms](https://mlsanity.com/paper/2207.04045/) (2022)

## Abstract (arXiv)

Stagnation detection has been proposed as a mechanism for randomized search heuristics to escape from local optima by automatically increasing the size of the neighborhood to find the so-called gap size, i.e., the distance to the next improvement. Its usefulness has mostly been considered in simple multimodal landscapes with few local optima that could be crossed one after another. In multimodal landscapes with a more complex location of optima of similar gap size, stagnation detection suffers from the fact that the neighborhood size is frequently reset to 1 without using gap sizes that were promising in the past. In this paper, we investigate a new mechanism called radius memory which can be added to stagnation detection to control the search radius more carefully by giving preference to values that were successful in the past. We implement this idea in an algorithm called SD-RLSm and show compared to previous variants of stagnation detection that it yields speed-ups for linear functions under uniform constraints and the minimum spanning tree problem. Moreover, its running time does not significantly deteriorate on unimodal functions and a generalization of the Jump benchmark. Finally, we present experimental results carried out to study SD-RLSm and compare it with other algorithms.