Applying Deep Learning and Reinforcement Learning to Traveling Salesman Problem
Applying Deep Learning and Reinforcement Learning to Traveling Salesman Problem
复制标题
DOI：
10.1109/iccecome.2018.8659266
复制
发表时间：
2018-08
期刊：
影响因子：
--
通讯作者：
Shoma Miki;Daisuke Yamamoto;H. Ebara
中科院分区：
文献类型：
--
作者：
Shoma Miki;Daisuke Yamamoto;H. Ebara
本文针对一类典型的组合优化问题--旅行商问题，提出了应用深度学习和强化学习的算法。该方法通过使用卷积神经网络将最优路径作为一幅图像来学习，并获得良好边缘分布，即可以包含在最优路径中的边缘的映射。它通过使用Good-Edge值执行邻域搜索：根据分布计算出的每条边的评估。此外，还存在无法获得最优解的情况，例如大型实例或其他组合优化问题，因此使用最优解而不是最优解进行学习非常重要。因此，我们还考虑了使用强化学习的学习方法。我们通过实验检验了这些方法的性能，并验证了提高解质量的有效性。
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.