An offline data-driven process for learning operator selection from metaheuristic search traces

Abstract

Trained Reward-based Action Classification Engine (TRACE) is a general process for capturing operator outcome data during metaheuristic search, training classifiers to predict whether an operator will yield an improved solution, and deploying those models to guide neighborhood selection during future search runs. This study introduces TRACE-VNS, a modular extension of General Variable Neighborhood Search (GVNS) applied to the Capacitated Vehicle Routing Problem (CVRP), where neighborhood selection is driven by these offline-trained models. Classifiers are trained on features extracted from GVNS traces, including action history, graph metrics, temporal state, and Upper Confidence Bound (UCB) indicators. Twelve classifiers, including tree ensembles, neural networks, and kernel-based models, are benchmarked using the Precision–Recall Area Under the Curve (PR-AUC) to evaluate predictive quality. Empirical results show that TRACE-VNS improves convergence speed and final solution quality over conventional GVNS across 84 CVRP instances. A detailed feature importance analysis identifies strong contributors, offering insights into the effective selection of operators. TRACE requires no runtime exploration or feedback loops and can generalize to other metaheuristics through minimal structural adaptation.