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

Benjamin Doerr; Pietro S. Oliveto; John Alasdair Warwicker

cs.NEMay 28, 2026

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

Authors: Benjamin Doerr, Pietro S. Oliveto, John Alasdair Warwicker

Organizations: Laboratoire d’Informatique (LIX), CNRS, École Polytechnique, Institut Polytechnique de Paris,2026 Palaiseau, 91120, France · Department of Computer Science and Engineering, Southern University of Science and Technology, Shenzhen, 518055, China · School of Computing & Communications, Lancaster University Leipzig, Leipzig, 04109, Germany

Abstract

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.

Explore similar work

On the Runtime Analysis of Reinforcement Learning Hyper-Heuristics
Jul 24, 2026Pietro S. Oliveto, Zhenyu Wang, Peizhou Wu +1Heuristics Hierarchical Reinforcement Learning
Regularized Large Neighborhood Search
Jun 1, 2026Germain Vivier-Ardisson, Laurent Demonet, Axel Parmentier +1Parallel Continuous Local Search Gibbs Measures
RAISE: LLM-based Automated Heuristic Design with Robust Adversary Instance Search
Jun 30, 2026Fei Liu, Alessio Figalli, Patrick Owen +1Heuristics Evolutionary Search

Jul 24, 2026 · cs.NEJ/K move · Enter open · S save

On the Runtime Analysis of Reinforcement Learning Hyper-Heuristics

Pietro S. Oliveto, Zhenyu Wang, Peizhou Wu, Mengqing Xu

Southern University of Science and Technology, 518055 Shenzhen, China

Selection Hyper-heuristics (HHs) automate algorithmic design by selecting from a set of low-level heuristics which one to apply at each stage of the optimisation process. Several impressive results have been recently rigorously proven regarding the performance of selection hyper-heuristics (HHs) for standard benchmark functions. However, the learning mechanisms employed by these HHs are considerably simplified compared to the machine learning techniques typically used in real world applications. In this paper we analyse a Reinforcement Learning Hyper-heuristic (RLHH) from the literature. The only previous result available proved that for a wide range of parameter settings, RLHH does not learn to select heuristics appropriately for the standard LeadingOnes benchmark function. In this paper, we rigorously prove that with appropriate parameter values RLHH equipped with two random local search operators, RLS_1 and RLS_2 optimises the LeadingOnes benchmark function in the best possible expected runtime achievable with the two operators up to lower order terms. Experiments show that for realistic problem sizes it is faster than the Generalised Random Gradient HH which was previously proven to also have optimal expected runtime up to lower order terms.

Heuristics Hierarchical Reinforcement Learning

Open paper Ask about it PDF

Abstract

Explore similar work

On the Runtime Analysis of Reinforcement Learning Hyper-Heuristics

Regularized Large Neighborhood Search

RAISE: LLM-based Automated Heuristic Design with Robust Adversary Instance Search