Applying Deep Learning and Reinforcement Learning to Traveling Salesman Problem
Shoma Miki, Daisuke Yamamoto, Hiroyuki Ebara · 2018
In this paper, we focus on the traveling salesman problem (TSP), which is one of typical combinatorial optimization problems, and propose algorithms applying deep learning and reinforcement learning. This method is marked by learning the optimal tour as an image using a convolutional neural network, and acquires the Good-Edge Distribution which is the map of edges that could be included in the optimal tour. And it performs neighborhood search by using Good-Edge Value: evaluations of each edge calculated from the distribution. In addition, there are cases where it is not possible to obtain an optimal solution such as large scale instances or other combinatorial optimization problems, so learning by using the best solution instead of the optimal solution is important. Therefore, we also consider learning methods using reinforcement learning. We conduct experiments to examine the performance of these methods, and verify the effectiveness of improving quality of solutions.