旅行商问题学习范式
本文提出了一种神经组合优化方法,将学习算法与模型架构相结合,以实现在训练过程中看不到的更大规模的问题的推广。通过对零样本推广的原理研究,控制实验提供了第一手数据,并提供了深度学习的新方向。
Jun, 2020
本文介绍了一种基于深度学习算法的解决平面欧几里得图中旅行商问题的方法,通过使用图卷积网络构建 TSP 图表示,并通过高度并行化的 Beam Search 非自回归方法输出巡回路径,我们在解决相同节点规模下的问题中比最近提出的自回归深度学习技术表现更好,最终平均优化差距从 50 个节点降低到 0.01%,100 个节点从 2.26%降至 1.39%,尽管相较于标准的运筹学求解器,我们的方法还有所欠缺。
Jun, 2019
利用熵正则化最优传输技术作为深度强化学习网络中的一层,以实现更快速的学习并在端到端训练期间强制执行分配约束和规定,从而对于解决组合优化问题的效率进行优化。
Mar, 2022
本文提出了一种利用神经网络和强化学习解决组合优化问题的框架,特别关注旅行推销员问题和背包问题,证明了该方法在不需要太多工程和启发式设计的情况下在二维欧几里得图上取得接近最优结果,并且可以得到具有多达 200 个项目实例的最优解。
Nov, 2016
探讨无监督学习在解决旅行推销员问题中的泛化能力,通过训练图神经网络并使用嵌入来构建边缘的热图,同时研究不同的训练实例大小、嵌入维度和分布对无监督学习方法结果的影响,结果表明使用较大的实例规模和增加嵌入维度可以构建更有效的表示,提高解决旅行推销员问题的能力,并发现在不同分布上进行泛化评估时,选择更困难的实例作为训练数据可以使模型具备更好的泛化能力。
Mar, 2024
提出了一种基于图神经网络和引导局部搜索的 TSP(旅行商问题)混合数据驱动方法,该方法能够在不损失解决方案质量的同时,快速求解大规模 TSP 实例,经实验证明,我们将 100 个节点问题集的平均最优性差从 1.534% 减少到 0.705%,将 20 个节点实例推广到 100 个节点问题集时,我们将最优性差从 18.845% 减少到 2.622%,提高了 2 倍和 7 倍。
Oct, 2021
本研究提出使用强化学习训练的图指针网络(Graph Pointer Networks,GPNs)来解决旅行商问题。我们使用 GPNs 对输入图进行嵌入并通过学习分层策略来优化城市排列。实验结果表明,GPNs 对小规模的 TSP50/100 问题的泛化性能不错,且在 TSP500/1000 问题中获得了更短的旅行路径和更快的计算时间,同时当问题涉及时间窗口约束时,支持最优解的分层强化学习训练优于以往的基准方法。
Nov, 2019
本文设计一种神经网络方法,利用图网络方法将旅行商、城市和货站作为三个具有不同基数的集合,通过搜索方法和特定的损失函数来输出最优解,实验结果表明该方法优于现有领域最先进的元启发式算法。
Mar, 2018
基于深度强化学习的旅行购货问题(TPP)解决方案,通过使用双向图表示 TPP、策略网络逐步构建路线,并通过线性规划获取购货计划,利用元学习策略稳定训练策略网络。在综合合成和标准基准测试上,相较于已有启发式算法,我们的 DRL 方法能够显著提升解决方案质量(降低 40%-90% 的最优性差距),尤其在大型实例上具备高效性。
Apr, 2024
本文利用强化学习和 Transformer 结构设计了用于 Traveling Salesman Problem 的新型算法,相较于以往的算法在 TSP50 和 TSP100 上有了更好的表现
Mar, 2021