Stagnation Detection with Randomized Local Search
Recently a mechanism called stagnation detection was proposed that automatically adjusts the mutation rate of evolutionary algorithms when they encounter local optima. The so-called $SD-(1+1)EA$ introduced by Rajabi and Witt (GECCO 2020) adds stagnation detection to the classical $(1+1)EA$ with standard bit mutation, which flips each bit independently with some mutation rate, and raises the mutation rate when the algorithm is likely to have encountered local optima. In this paper, we investigate stagnation detection in the context of the $k$-bit flip operator of randomized local search that flips $k$ bits chosen uniformly at random and let stagnation detection adjust the parameter $k$. We obtain improved runtime results compared to the $SD-(1+1)EA$ amounting to a speed-up of up to $e=2.71\dots$ Moreover, we propose additional schemes that prevent infinite optimization times even if the algorithm misses a working choice of $k$ due to unlucky events. Finally, we present an example where standard bit mutation still outperforms the local $k$-bit flip with stagnation detection.
Code (0)
등록된 구현이 없습니다.
Tasks
Evolutionary AlgorithmsMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Stagnation Detection in Highly Multimodal Fitness Landscapes
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 distan…
An Extended Jump Functions Benchmark for the Analysis of Randomized Search Heuristics
Jump functions are the {most-studied} non-unimodal benchmark in the theory of randomized search heuristics, in particular, evolutionary algorithms (EAs). They have significantly improved our understanding of how EAs esca…
Evolutionary AlgorithmsSelf-Adjusting Evolutionary Algorithms for Multimodal Optimization
Recent theoretical research has shown that self-adjusting and self-adaptive mechanisms can provably outperform static settings in evolutionary algorithms for binary search spaces. However, the vast majority of these stud…
Evolutionary AlgorithmsPUL-SLAM: Path-Uncertainty Co-Optimization with Lightweight Stagnation Detection for Efficient Robotic Exploration
Existing Active SLAM methodologies face issues such as slow exploration speed and suboptimal paths. To address these limitations, we propose a hybrid framework combining a Path-Uncertainty Co-Optimization Deep Reinforcem…
Reinforcement LearningAnomaly DetectionStagnation Detection Meets Fast Mutation
Two mechanisms have recently been proposed that can significantly speed up finding distant improving solutions via mutation, namely using a random mutation rate drawn from a heavy-tailed distribution ("fast mutation", Do…