Accelerating the Genetic Algorithm for Large-scale Traveling Salesman Problems by Cooperative Coevolutionary Pointer Network with Reinforcement Learning
This work addresses the computational challenge of solving large-scale traveling salesman problems, which is important for logistics and optimization domains, but it appears incremental as it builds on existing methods like pointer networks and genetic algorithms.
The paper tackles large-scale traveling salesman problems by proposing a two-stage optimization strategy that uses a cooperative coevolutionary pointer network with reinforcement learning to generate an elite solution, which then accelerates a genetic algorithm. Experimental results on 10 problems show that this approach greatly accelerates optimization compared to traditional evolutionary algorithms.
In this paper, we propose a two-stage optimization strategy for solving the Large-scale Traveling Salesman Problems (LSTSPs) named CCPNRL-GA. First, we hypothesize that the participation of a well-performed individual as an elite can accelerate the convergence of optimization. Based on this hypothesis, in the first stage, we cluster the cities and decompose the LSTSPs into multiple subcomponents, and each subcomponent is optimized with a reusable Pointer Network (PtrNet). After subcomponents optimization, we combine all sub-tours to form a valid solution, this solution joins the second stage of optimization with GA. We validate the performance of our proposal on 10 LSTSPs and compare it with traditional EAs. Experimental results show that the participation of an elite individual can greatly accelerate the optimization of LSTSPs, and our proposal has broad prospects for dealing with LSTSPs.