Enhanced Reinforcement Learning for TSP: Proximal Policy Optimization with Graph Attention and Entropy Regularization
Chendie Yao, Xingxing Liang, Longfei Zhang, Jincai Huang · 2024
The application of reinforcement learning (RL) to combinatorial optimization problems has gained significant attention due to its strong capability, high efficiency, and fast solving speed. However, the Travelling Salesman Problem (TSP) poses considerable challenges for existing RL methods, primarily due to the exponential growth of potential routes as the number of cities increases, complicating the search for optimal solutions. To address these challenges, this paper proposes a novel solution based on an approximate policy optimization algorithm for TSP. The TSP is modeled as an RL problem, with its environment, states, rewards, and actions defined. We then introduce an approximate state value estimation method that leverages the true cost and probabilities of TSP sampling tours, offering improved accuracy as a baseline for policy guidance. Our network model employs a graph attention mechanism and introduces first-visit city policy entropy loss to update the network using the Proximal Policy Optimization (PPO) method. Experiments demonstrate that our approach outperforms heuristic algorithms and can approximate the exact solution quickly. It achieves results comparable to or better than popular RL algorithms such as EAN and GAT among instances of various sizes while converging faster with the same amount of data.