使用 HNN 和 HNN-SA 算法解决旅行推销员问题
本文介绍了一种基于深度学习算法的解决平面欧几里得图中旅行商问题的方法,通过使用图卷积网络构建 TSP 图表示,并通过高度并行化的 Beam Search 非自回归方法输出巡回路径,我们在解决相同节点规模下的问题中比最近提出的自回归深度学习技术表现更好,最终平均优化差距从 50 个节点降低到 0.01%,100 个节点从 2.26%降至 1.39%,尽管相较于标准的运筹学求解器,我们的方法还有所欠缺。
Jun, 2019
本文设计一种神经网络方法,利用图网络方法将旅行商、城市和货站作为三个具有不同基数的集合,通过搜索方法和特定的损失函数来输出最优解,实验结果表明该方法优于现有领域最先进的元启发式算法。
Mar, 2018
NeuroLKH 采用深度学习和 LKH 启发式算法相结合,通过训练 Sparse Graph Network 模型来解决旅行商问题等路由问题,得出实验结果表明能够优于传统启发式算法并泛化到更大范围问题。
Oct, 2021
本文利用强化学习和 Transformer 结构设计了用于 Traveling Salesman Problem 的新型算法,相较于以往的算法在 TSP50 和 TSP100 上有了更好的表现
Mar, 2021
本文提出了一种神经组合优化方法,将学习算法与模型架构相结合,以实现在训练过程中看不到的更大规模的问题的推广。通过对零样本推广的原理研究,控制实验提供了第一手数据,并提供了深度学习的新方向。
Jun, 2020
提出了一种基于图神经网络和引导局部搜索的 TSP(旅行商问题)混合数据驱动方法,该方法能够在不损失解决方案质量的同时,快速求解大规模 TSP 实例,经实验证明,我们将 100 个节点问题集的平均最优性差从 1.534% 减少到 0.705%,将 20 个节点实例推广到 100 个节点问题集时,我们将最优性差从 18.845% 减少到 2.622%,提高了 2 倍和 7 倍。
Oct, 2021
探讨学习典范对旅行推销员问题的深度神经网络训练的影响,研究发现相较于受控实验的有标记数据的 SL 模型,强化学习(RL)模型对于变量大小的图形具有更好的紧急普遍性并是学习新组合问题的规模无关解算器的重要组成部分。
Oct, 2019
本研究提出了一种基于层次强化学习的端到端学习框架,称为 H-TSP,用于解决大规模 TSP 问题,通过选择子集并使用深度学习模型直接生成解决方案,具有可扩展和高效性。
Apr, 2023
通过测试时间增强(TTA)作为一种有效的技术,我们提出了解决组合优化问题,包括旅行推销员问题。与学习图结构的已提出的具有不变性特性的深度学习模型不同,我们将节点索引的排列解释为一种 TTA 方案。结果表明,我们的方法能够获得比最新模型更短的解决方案。此外,我们展示了找到接近精确解的解决方案的概率随增强尺寸的增加而增加。
May, 2024