用解空间结构提升扩散模型，刷新神经网络解TSP的纪录
IDEQ -- Improving Diffusion Models for the Traveling Salesman Problem (TSP) by Leveraging the Structure of the Solution Space
- 利用TSP解空间的约束结构优化扩散过程
- 在500和1000城市实例上分别达0.3%和0.5%最优间隙
- 性能接近并超越经典启发式LKH3，适合大规模TSP求解
我们研究了用扩散模型求解旅行商问题（TSP）。基于DIFUSCO和T2TCO方法，提出IDEQ。IDEQ通过利用TSP状态空间的约束结构提升解的质量。其关键改进在于：将DIFUSCO课程学习的最后阶段替换为对2-opt算子轨道收敛至最优解的哈密顿环的均匀分布。实验表明，IDEQ在合成实例上优于现有神经网络方法；更重要的是，在TSPlib基准测试中表现优异：在1577和3795城市实例上甚至优于最佳启发式算法LKH3。对于500城市实例，最优间隙仅为0.3%；1000城市实例为0.5%，创下神经网络方法新SOTA。此外，IDEQ方差更低，且随城市数增加更易扩展，优于DIFUSCO和T2TCO。
原文摘要 · Abstract (English)
We investigate diffusion models to solve the Traveling Salesman Problem. Building on the recent DIFUSCO and T2TCO approaches, we propose IDEQ. IDEQ improves the quality of the solutions by leveraging the constrained structure of the state space of the TSP. Another key component of IDEQ consists in replacing the last stages of DIFUSCO curriculum learning by considering a uniform distribution over the Hamiltonian tours whose orbits by the 2-opt operator converge to the optimal solution as the training objective. Our experiments show that IDEQ improves the state of the art for such neural network based techniques on synthetic instances. More importantly, our experiments show that IDEQ performs very well on the instances of the TSPlib, a reference benchmark in the TSP community: it closely matches the performance of the best heuristics, LKH3, being even able to obtain better solutions than LKH3 on 2 instances of the TSPlib defined on 1577 and 3795 cities. IDEQ obtains 0.3% optimality gap on TSP instances made of 500 cities, and 0.5% on TSP instances with 1000 cities. This sets a new SOTA for neural based methods solving the TSP. Moreover, IDEQ exhibits a lower variance and better scales-up with the number of cities with regards to DIFUSCO and T2TCO.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。