论文标题
将加固学习与Lin-Kernighan-Helsgaun算法相结合，用于旅行推销员问题
Combining Reinforcement Learning with Lin-Kernighan-Helsgaun Algorithm for the Traveling Salesman Problem
论文作者
论文摘要
我们解决了旅行推销员问题（TSP），这是一个著名的NP-HARD组合优化问题。我们提出了一种可变策略加强方法，称为VSR-LKH，该方法结合了三种增强学习方法（Q-Learning，Sarsa和Monte Carlo）与众所周知的TSP算法，称为Lin-Kernighan-Helsgaun（LKH）。 VSR-LKH取代了LKH中僵化的遍历操作，并让程序学会通过强化学习在每个搜索步骤中做出选择。来自TSPLIB的111个TSP基准的实验结果具有多达85,900个城市，证明了该方法的出色性能。
We address the Traveling Salesman Problem (TSP), a famous NP-hard combinatorial optimization problem. And we propose a variable strategy reinforced approach, denoted as VSR-LKH, which combines three reinforcement learning methods (Q-learning, Sarsa and Monte Carlo) with the well-known TSP algorithm, called Lin-Kernighan-Helsgaun (LKH). VSR-LKH replaces the inflexible traversal operation in LKH, and lets the program learn to make choice at each search step by reinforcement learning. Experimental results on 111 TSP benchmarks from the TSPLIB with up to 85,900 cities demonstrate the excellent performance of the proposed method.
