Solving Traveling Salesman Problem with Image-Based Classification
Solving Traveling Salesman Problem with Image-Based Classification
复制标题
DOI：
10.1109/ictai.2019.00156
复制
发表时间：
2019-11
期刊：
影响因子：
--
通讯作者：
Shoma Miki;H. Ebara
中科院分区：
文献类型：
--
作者：
Shoma Miki;H. Ebara
组合优化问题在真实的世界中有着广泛的应用，开发高质量的算法求解组合优化问题具有重要意义。本文以典型的组合优化问题之一旅行商问题为研究对象，介绍了应用深度学习的算法。应用于组合优化问题的一种方法是使用神经网络在寻找解决方案时做出决策。我们提出的像素映射分类网络（PCN）将问题视为一个图像，通过将每个顶点映射到图像上，并对顶点进行近似评估来构建一个巡回赛。这可以被视为选择适当顶点的分类。根据PCN的评价，我们考虑了贪婪选择和使用波束搜索的构造算法。我们进行实验来检验这些方法的性能，并验证提高解决方案的质量的有效性。
Combinatorial optimization is a problem with various application in the real world, and development of high-quality algorithms for solving it is important. We focus on the traveling salesman problem (TSP) which is one of typical combinatorial optimization problems, and introduce algorithms applying deep learning. One way to apply to combinatorial optimization problems is to make decisions in finding a solution using neural networks. Pixel-mapped Classification Network (PCN) we propose treats a problem as an image by mapping each vertex onto an image, and approximate evaluation of vertices to construct a tour. This can be regarded as a classification that selects the appropriate vertex. We consider construction algorithms of greedy selecting and using beam-search according to the evaluation by PCN. We conduct experiments to examine the performance of these methods, and verify the effectiveness of improving quality of solutions.