Abstract
This paper introduces LAST-RL (Large-State Reinforcement Learning), a novel hyper-heuristic framework designed to bridge the gap between reinforcement learning (RL) and classical search metaheuristics. By utilizing a rich set of 15 search-state features and a structured exploration strategy inspired by Iterated Local Search (ILS), LAST-RL achieves state-of-the-art performance across diverse optimization domains. Evaluated on the CHeSC 2011 benchmark and real-world personnel scheduling tasks, LAST-RL outperfroms previous RL-based approaches and several domain-specific methods, securing a first-place ranking in competitive benchmarks.
Introduction
In combinatorial optimization, hyper-heuristics function as "algorithms that choose algorithms." Operating behind a "domain barrier," these systems select and sequence low-level heuristics (LLHs) without direct access to the internal structure of the problem (e.g., vehicle routing or bin packing). Historically, hyper-heuristics have relied on "thin" state representations—typically 1 to 4 features—making it difficult for RL agents to learn sophisticated strategies. Furthermore, standard RL exploration techniques, such as $\epsilon$-greedy, often fail to discover the complex sequences of heuristics required to escape local optima.
Methodology
LAST-RL addresses these challenges through several key innovations:
- Rich State Representation: The framework utilizes 15 novel features derived from the search trajectory, including the magnitude of recent objective changes, time elapsed since the last reset, and "horizon" features tracking the success rate of the last 10 heuristic applications.
- ILS-Based Exploration: Instead of random action selection, LAST-RL employs structured exploration inspired by Iterated Local Search. It prioritizes large-scale perturbations (ruin-recreate) followed by mutations and local search intensification.
- Adaptive Solution Chains: The algorithm employs the Luby sequence to determine heuristic chain lengths before resetting, scaling these lengths based on the average length of previously successful chains.
- SARSA-lambda with Tile Coding: To manage the continuous 15-dimensional state space, the authors use tile coding for sparse feature discretization and the SARSA($\lambda$) algorithm to update the agent's policy.
Experimental Results
Benchmark Performance
LAST-RL was evaluated on the CHeSC 2011 (Cross-Domain Heuristic Search Challenge) benchmark, which includes six domains: MaxSAT, Bin Packing, Personnel Scheduling, Flowshop, Traveling Salesperson (TSP), and Vehicle Routing (VRP). Using the competition's "Formula One" scoring system, LAST-RL achieved a total score of 141.97, ranking 1st among 23 competitors and surpassing the previous state-of-the-art method, GIHH.
Ablation Study
To validate the contribution of each component, the authors conducted an ablation study comparing the full LAST-RL model against versions using only ILS-based exploration, only RL, or a simplified state representation. The results confirmed that the synergy between the rich state representation and structured exploration is critical for achieving peak performance.
Real-World Application
The framework was also tested on real-life personnel scheduling problems, including Bus Driver Scheduling and Rotating Workforce Scheduling. In the Bus Driver Scheduling domain, LAST-RL found the best average objective for 16 out of 50 instances, outperforming specialized domain-specific methods.
Conclusion
LAST-RL demonstrates that the "domain barrier" in hyper-heuristics is not as opaque as previously thought. By extracting rich information from the search trajectory and seeding RL exploration with the structural wisdom of ILS, the agent can learn highly effective heuristic schedules. Future work will explore the use of Deep Reinforcement Learning to handle even more complex state representations and conduct a more granular analysis of feature importance.
Summary updated