同行之路:一种新的 TSP 求解策略
本文提出了一种神经组合优化方法,将学习算法与模型架构相结合,以实现在训练过程中看不到的更大规模的问题的推广。通过对零样本推广的原理研究,控制实验提供了第一手数据,并提供了深度学习的新方向。
Jun, 2020
本文利用强化学习和 Transformer 结构设计了用于 Traveling Salesman Problem 的新型算法,相较于以往的算法在 TSP50 和 TSP100 上有了更好的表现
Mar, 2021
本研究针对组合优化问题,提出了在深度学习模型训练前进行预训练以利用相关算法对于解决 TSP 问题具有提升作用的算法推理方法,并证明该方法能够优于传统深度学习模型。
May, 2023
提出了一种基于图神经网络和引导局部搜索的 TSP(旅行商问题)混合数据驱动方法,该方法能够在不损失解决方案质量的同时,快速求解大规模 TSP 实例,经实验证明,我们将 100 个节点问题集的平均最优性差从 1.534% 减少到 0.705%,将 20 个节点实例推广到 100 个节点问题集时,我们将最优性差从 18.845% 减少到 2.622%,提高了 2 倍和 7 倍。
Oct, 2021
本文介绍了一种基于深度学习算法的解决平面欧几里得图中旅行商问题的方法,通过使用图卷积网络构建 TSP 图表示,并通过高度并行化的 Beam Search 非自回归方法输出巡回路径,我们在解决相同节点规模下的问题中比最近提出的自回归深度学习技术表现更好,最终平均优化差距从 50 个节点降低到 0.01%,100 个节点从 2.26%降至 1.39%,尽管相较于标准的运筹学求解器,我们的方法还有所欠缺。
Jun, 2019
本文设计一种神经网络方法,利用图网络方法将旅行商、城市和货站作为三个具有不同基数的集合,通过搜索方法和特定的损失函数来输出最优解,实验结果表明该方法优于现有领域最先进的元启发式算法。
Mar, 2018
本文提出了一种利用神经网络和强化学习解决组合优化问题的框架,特别关注旅行推销员问题和背包问题,证明了该方法在不需要太多工程和启发式设计的情况下在二维欧几里得图上取得接近最优结果,并且可以得到具有多达 200 个项目实例的最优解。
Nov, 2016
介绍 2021 年国际人工智能联合大会(IJCAI-21)上第一个旅行推销员问题(TSP)人工智能竞赛,关注基于学习的算法,介绍了该竞赛的问题、比赛安排、获胜方法和结果概述。竞赛的胜利方法使 AI 在随机路由问题上取得了技术进步,也使路由问题成为 AI 研究人员感兴趣的问题设定。同时,该比赛所使用的路由问题模拟器现已成为开源工具,可以成为其他研究人员使用的新 AI 方法基准测试。
Jan, 2022
本文研究了使用自适应难度方法的基于学习的旅行商问题方法,通过定义硬度测量,使用硬度自适应生成器生成不同难度的实例,再利用课程学习器完全利用这些实例来训练 TSP 求解器。实验结果表明,我们的硬度自适应生成器可以生成比现有方法更困难的实例,而我们提出的方法在最优性差距方面显著优于最先进的模型。
Apr, 2022
我们提出了 UTSP,这是一个用于解决旅行推销员问题(TSP)的无监督学习框架,使用基于图神经网络(GNN)的代理损失。该方法在参数效率和数据效率方面优于目前的数据驱动 TSP 启发式方法。
Mar, 2023