论文标题
将小的预训练模型概括为任意大型TSP实例
Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instances
论文作者
论文摘要
对于旅行推销员问题（TSP），现有的基于监督的基于学习的算法严重遭受了缺乏泛化能力的影响。为了克服这一缺点，本文试图（以监督方式）训练一个小型模型，该模型可以重复地用于为任意大小的TSP实例构建热图，该模型基于一系列技术，例如图形采样，图形转换和热图合并。此外，热图被馈入增强学习方法（蒙特卡洛树搜索），以指导对高质量解决方案的搜索。基于大量实例（最多有10,000个顶点）的实验结果表明，这种新方法显然优于基于机器学习的TSP算法，并显着提高了训练有素的模型的概括能力。
For the traveling salesman problem (TSP), the existing supervised learning based algorithms suffer seriously from the lack of generalization ability. To overcome this drawback, this paper tries to train (in supervised manner) a small-scale model, which could be repetitively used to build heat maps for TSP instances of arbitrarily large size, based on a series of techniques such as graph sampling, graph converting and heat maps merging. Furthermore, the heat maps are fed into a reinforcement learning approach (Monte Carlo tree search), to guide the search of high-quality solutions. Experimental results based on a large number of instances (with up to 10,000 vertices) show that, this new approach clearly outperforms the existing machine learning based TSP algorithms, and significantly improves the generalization ability of the trained model.
