SERENE-MH: Sample-Efficient Reinforcement-Enhanced Neighborhood Exploration for Metaheuristics

Abstract

Adaptive operator selection, i.e., the online choice of which operator a metaheuristic applies at each iteration, is usually studied under the assumption that evaluating the objective is cheap, so a selection rule evaluates whatever it selects. Many combinatorial problems violate it: scoring a single candidate requires solving an optimization subproblem. We present SERENE-MH, a control layer for single-solution metaheuristics that spends a fixed budget of true objective evaluations efficiently. Each iteration, a Bayesian linear value model conditioned on search telemetry is sampled once to propose a slate of operators, and a cheap surrogate gate, the model’s own posterior mean, decides which proposal receives the evaluation. The policy is learned online within a single run, with no training corpus. On 41 capacitated facility location instances in four size tiers, scored against exact optima, SERENE-MH reached lower optimality gaps in fewer evaluations than five adaptive-selection baselines and a surrogate-screening selector, within every host that permits worsening moves. At one quarter of the budget, the mean gap was 0.38% to 0.56% across hosts, against 1.42% to 2.26% for a greedy selector that never explores. An ablation identifies the gate as the component that saves evaluations and Thompson exploration as the safeguard against premature commitment: removing exploration inflated the regret area under the gap curve by 154% to 253%. The configuration transferred untuned to a network restoration scheduling problem. On the traveling salesman problem, where a single operator dominates, removing exploration instead improved that area by 8.6%, which bounds when exploration repays its cost.