Meta-learning-based adaptive operator selection for traveling salesman problem

초록

In evolutionary optimization, effectively leveraging knowledge about search operator performance is crucial for enhancing algorithmic results. Traditional operator selection strategies often rely on fixed heuristics or trial-and-error, which struggle to adapt to the nonstationary search dynamics of evolutionary runs-i.e., the stage-dependent, instance-dependent, and population-dependent shifts in operator effectiveness-and typically yield suboptimal performance. To address these challenges, we propose a novel meta-learning-based adaptive operator selection (AOS) framework. It leverages a Long Short-Term Memory (LSTM) neural network to learn temporal patterns of operator performance from historical data and dynamically adjust operator choice on-the-fly. The framework also integrates domain-specific biases to preserve population diversity and promote effective exploration, and it continuously updates its selection policy through dynamic online learning as the evolutionary process unfolds. Experiments on the Traveling Salesman Problem (TSP) benchmark demonstrate that the proposed LSTM-based AOS method significantly outperforms conventional approaches to operator selection. In particular, it achieved a median optimality gap of 9.87 % on a suite of TSP instances-approximately a 20 % improvement over the best fixed-operator configuration-indicating superior solution quality. Moreover, our approach consistently surpassed other state-of-the-art AOS techniques, underscoring the efficacy of the LSTM-driven framework and its significant potential to enhance evolutionary algorithm performance on complex optimization tasks.

키워드