We present a graph neural network assisted Monte Carlo Tree Search approach for the classical traveling salesman problem (TSP). We adopt a greedy algorithm framework to construct the optimal solution to TSP by adding the nodes successively. A graph neural network (GNN) is trained to capture the local and global graph structure and give the prior probability of selecting each vertex every step. The prior probability provides a heuristics for MCTS, and the MCTS output is an improved probability for selecting the successive vertex, as it is the feedback information by fusing the prior with the scouting procedure. Experimental results on TSP up to 100 nodes demonstrate that the proposed method obtains shorter tours than other learning-based methods. Traveling Salesman Problem (TSP) is a classical combinatorial optimization problem and has many practical applications in real life, such as planning, manufacturing, genetics (Applegate et al., 2006b) . The goal of TSP is to find the shortest route that visits each city once and ends in the origin city, which is well-known as an NP-hard problem (Papadimitriou, 1977) . In the literature, approximation algorithms were proposed to solve TSP (Lawler et al., 1986; Goodrich & Tamassia, 2015) . In particular, many heuristic search algorithms were made to find a satisfactory solution within a reasonable time. However, the performance of heuristic algorithms depends on handcrafted heuristics to guide the search procedure to find competitive tours efficiently, and the design of heuristics usually requires substantial expertise of the problem (Johnson & McGeoch, 1997; Dorigo & Gambardella, 1997) . Recent advances in deep learning provide a powerful way of learning effective representations from data, leading to breakthroughs in many fields such as speech recognition (Lecun et al., 2015) . Efforts of the deep learning approach to tackling TSP has been made under the supervised learning and reinforcement learning frameworks. Vinyals et al. (Vinyals et al., 2015) introduced a pointer network based on the Recurrent Neural Network (RNN) to model the stochastic policy that assigns high probabilities to short tours given an input set of coordinates of vertices. Dai et al. (Dai et al., 2017) tackled the difficulty of designing heuristics by Deep Q-Network (DQN) based on structure2vec (Dai et al., 2016b) , and a TSP solution was constructed incrementally by the learned greedy policy. Most recently, Kool et al. (Kool et al., 2019) used Transformer-Pointer Network (Vaswani et al., 2017) to learn heuristics efficiently and got close to the optimal TSP solution for up to 100 vertices. These efforts made it possible to solve TSP by an end-to-end heuristic algorithm without special expert skills and complicated feature design. In this paper, we present a new approach to solving TSP. Our approach combines the deep neural network with the Monte Carlo Tree Search (MCTS), so that takes advantage of the powerful feature representation and scouting exploration. A graph neural network (GNN) is trained to capture the local and global graph structure and predict the prior probability, for each vertex, of whether this vertex belongs to the partial tour. Besides node features, we integrate edge information into each update-layer in order to extract features efficiently from the problem whose solution relies on the edge weight. Similar to above-learned heuristic approaches, we could greedily select the vertex according to the biggest prior probability and yet the algorithm may fall into the local optimum because the algorithm has only one shot to compute the optimal tour and never goes back and reverses the decision. To overcome this problem, we introduce a graph neural network assisted Monte Carlo Tree Search (GNN-MCTS) to make the decision more reliable by a large number of scouting simulations. The trained GNN is used to guide the MCTS procedure that effectively reduces the complexity of the search space and MCTS provides a more reliable policy to avoid stuck in a local optimum. Experimental results on TSP up to 100 vertices demonstrate that the proposed method obtains shorter tours than other learning-based methods. The remainder of the paper is organized as follows: After reviewing related work in Section 2, we briefly give a preliminary introduction to TSP in Section 3. Our approach is formulated in Section 4. Experimental results are given in Section 5, followed by the conclusion in Section 6. We proposed a graph neural network assisted Monte Carlo Tree Search (GNN-MCTS) for the classical traveling salesman problem. The core idea of our approach lies in converting the TSP into a tree search problem. To capture the local and global graph structure, we train a graph neural network (GNN) which integrates node feature and edge weight into the feature update process. Instead of using the prior probability output by GNN in a greedy way, we designed a GNN-MCTS to provide scouting simulation so that the algorithm could avoid being stuck into the local optimum. The exper-imental results show that the proposed approach can obtain shorter tours than other learning-based methods. We see the presented work as a step towards a new family of solvers for NP-hard problems that leverage both deep learning and classic heuristics. We will release code to support future progress in this direction.
A Graph Neural Network Assisted Monte Carlo Tree Search Approach to Traveling Salesman Problem
{"src": "scitldr-AIC_train", "paper_id": "Syg6fxrKDB"}