# Selection Hyper-heuristics Can Automatically Adjust the Learning Period to Optimally Solve Pseudo-Boolean Problems

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 55 references that are in the map.
- First posted on arXiv 28 May 2026.

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

- [Self-Adjusting Evolutionary Algorithms for Multimodal Optimization](https://mlsanity.com/paper/2004.03266/) (2020)
- [Better Runtime Guarantees Via Stochastic Domination](https://mlsanity.com/paper/1801.04487/) (2018)
- [Stagnation Detection with Randomized Local Search](https://mlsanity.com/paper/2101.12054/) (2021)
- [Theory-inspired Parameter Control Benchmarks for Dynamic Algorithm Configuration](https://mlsanity.com/paper/2202.03259/) (2022)
- [Theory of Parameter Control for Discrete Black-Box Optimization: Provable Performance Gains Through Dynamic Parameter Choices](https://mlsanity.com/paper/1804.05650/) (2018)
- [Stagnation Detection in Highly Multimodal Fitness Landscapes](https://mlsanity.com/paper/2104.04395/) (2021)
- [Stagnation Detection Meets Fast Mutation](https://mlsanity.com/paper/2201.12158/) (2022)
- [Self-adaptation of Mutation Rates in Non-elitist Populations](https://mlsanity.com/paper/1606.05551/) (2016)
- [Optimal Parameter Choices Through Self-Adjustment: Applying the 1/5-th Rule in Discrete Settings](https://mlsanity.com/paper/1504.03212/) (2015)
- [How the Move Acceptance Hyper-Heuristic Copes With Local Optima: Drastic Differences Between Jumps and Cliffs](https://mlsanity.com/paper/2304.10414/) (2023)
- [The (1+λ) Evolutionary Algorithm with Self-Adjusting Mutation Rate](https://mlsanity.com/paper/1704.02191/) (2017)
- [Runtime Analysis for Self-adaptive Mutation Rates](https://mlsanity.com/paper/1811.12824/) (2018)
- [Hyper-Parameter Tuning for the (1+(λ,λ)) GA](https://mlsanity.com/paper/1904.04608/) (2019)
- [Hyper-Heuristics Can Profit From Global Variation Operators](https://mlsanity.com/paper/2407.14237/) (2024)
- [Speeding Up Hyper-Heuristics With Markov-Chain Operator Selection and the Only-Worsening Acceptance Operator](https://mlsanity.com/paper/2506.01107/) (2025)
- [A Flexible Evolutionary Algorithm With Dynamic Mutation Rate Archive](https://mlsanity.com/paper/2404.04015/) (2024)

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

- [On the Runtime Analysis of Reinforcement Learning Hyper-Heuristics](https://mlsanity.com/paper/2607.22036/) (2026)

## Abstract (arXiv)

The Random Gradient hyper-heuristic was recently shown to be able to learn the optimal neighbourhood size when optimizing the LeadingOnes benchmark via the Randomised Local Search (RLS) meta-heuristic. However, for this to happen, a learning period of a certain length τ had to be used, differently from classic hyper-heuristics, which change their behaviour based on the success of only the previous iteration. In this paper, we show how to automatically set this new parameter value, relieving the user from the non-trivial task of controlling this novel algorithm parameter. We prove that the resulting hyper-heuristic selects the optimal neighbourhood size in a 1-o(1) fraction of the iterations and, consequently, optimises the LeadingOnes benchmark in the best possible time (apart from lower-order terms) achievable with these neighborhood sizes.