An offline data-driven process for learning operator selection from metaheuristic search traces
Panagiotis Kalatzantonakis, Angelo Sifaleras, Nikolaos Samaras · Swarm and Evolutionary Computation · 2025
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. • TRACE learns decision policies from features extracted during metaheuristic execution. • TRACE-VNS improves convergence and solution quality over conventional GVNS. • Offline-trained models guide operator selection with zero runtime tuning. • Models generalize across 84 CVRP instances with strong PR-AUC performance. • Learns to adapt across problems by modeling search dynamics, not problem rules.