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

Problem
This paper addresses the gap in the optimization of pseudo-Boolean problems using hyper-heuristics, specifically focusing on the challenge of determining an optimal learning period ($τ$) for the Random Gradient hyper-heuristic. Previous work demonstrated that the Random Gradient hyper-heuristic could learn the optimal neighborhood size for the LeadingOnes benchmark using a fixed learning period, but did not provide a method for automatically adjusting this parameter. This work is presented as a preprint and has not yet undergone peer review.

Method
The authors propose a novel hyper-heuristic that automatically adjusts the learning period $τ$ to optimize the selection of neighborhood sizes during the optimization process. The core technical contribution lies in the algorithm’s ability to dynamically adapt $τ$ based on the performance of the hyper-heuristic over multiple iterations, rather than relying solely on the success of the previous iteration. The authors provide a theoretical proof that this adaptive mechanism allows the hyper-heuristic to select the optimal neighborhood size in a $1-o(1)$ fraction of iterations. The training compute required for this method is not explicitly disclosed, but the focus is on the algorithm’s efficiency in optimizing the LeadingOnes benchmark.

Results
The proposed hyper-heuristic demonstrates significant improvements over traditional methods. Specifically, it optimizes the LeadingOnes benchmark in the best possible time achievable with the selected neighborhood sizes, aside from lower-order terms. While exact numerical results and comparisons to specific baselines are not detailed in the abstract, the implication is that the adaptive learning period leads to superior performance compared to classic hyper-heuristics that do not adjust $τ$.

Limitations
The authors acknowledge that their approach is contingent on the successful implementation of the adaptive learning period and may not generalize to all pseudo-Boolean problems or other benchmarks outside of LeadingOnes. Additionally, the paper does not discuss the computational overhead introduced by the adaptive mechanism, which could impact performance in resource-constrained environments. The lack of empirical results comparing the proposed method against a wider array of baselines is also a notable limitation.

Why it matters
This work has significant implications for the field of combinatorial optimization and hyper-heuristic design. By automating the adjustment of the learning period, the proposed method reduces the burden on practitioners to manually tune hyper-parameters, potentially leading to more efficient optimization processes. The theoretical guarantees provided by the authors enhance the understanding of hyper-heuristic performance, paving the way for future research to explore adaptive mechanisms in other optimization contexts. This could lead to advancements in solving complex optimization problems across various domains, including operations research and artificial intelligence.

Authors: Benjamin Doerr, Pietro S. Oliveto, John Alasdair Warwicker
Source: arXiv:2605.29916
URL: https://arxiv.org/abs/2605.29916v1