Jun, 2019

旅行商问题的高效图卷积网络技术

PDF
TL;DR本文介绍了一种基于深度学习算法的解决平面欧几里得图中旅行商问题的方法，通过使用图卷积网络构建 TSP 图表示，并通过高度并行化的 Beam Search 非自回归方法输出巡回路径，我们在解决相同节点规模下的问题中比最近提出的自回归深度学习技术表现更好，最终平均优化差距从 50 个节点降低到 0.01％，100 个节点从 2.26％降至 1.39％，尽管相较于标准的运筹学求解器，我们的方法还有所欠缺。
travelling salesman problem2d euclidean graphsgraph convolutional networksbeam searchdeep learning
发现论文，激发创造
  • 面向旅行商问题的图神经网络引导局部搜索

    提出了一种基于图神经网络和引导局部搜索的 TSP（旅行商问题）混合数据驱动方法，该方法能够在不损失解决方案质量的同时，快速求解大规模 TSP 实例，经实验证明，我们将 100 个节点问题集的平均最优性差从 1.534% 减少到 0.705%，将 20 个节点实例推广到 100 个节点问题集时，我们将最优性差从 18.845% 减少到 2.622%，提高了 2 倍和 7 倍。

    Oct, 2021

  • 学会解决旅行商问题要重新思考泛化

    本文提出了一种神经组合优化方法，将学习算法与模型架构相结合，以实现在训练过程中看不到的更大规模的问题的推广。通过对零样本推广的原理研究，控制实验提供了第一手数据，并提供了深度学习的新方向。

    Jun, 2020

  • 旅行商问题的 Transformer 网络

    本文利用强化学习和 Transformer 结构设计了用于 Traveling Salesman Problem 的新型算法，相较于以往的算法在 TSP50 和 TSP100 上有了更好的表现

    Mar, 2021

  • 强化学习的神经组合优化

    本文提出了一种利用神经网络和强化学习解决组合优化问题的框架，特别关注旅行推销员问题和背包问题，证明了该方法在不需要太多工程和启发式设计的情况下在二维欧几里得图上取得接近最优结果，并且可以得到具有多达 200 个项目实例的最优解。

    Nov, 2016

  • 同行之路：一种新的 TSP 求解策略

    本研究提出了一种基于模仿学习框架的策略来解决旅行商问题，并展示了所训练的图神经网络在大规模的 TSP 实例上的较快求解能力。

    Oct, 2022

  • 基于边缘感知的图自编码器用于规模不平衡数据的旅行商问题

    该论文提出了一种数据驱动的图表示学习方法，用于解决具有不同数量城市的旅行推销员问题，并通过实验证明该方法在解决旅行推销员问题方面具有与最先进的基于学习的方法相媲美的性能。

    Oct, 2023

  • 学习解决 NP 完全问题 - 用图神经网络处理决策 TSP 问题

    本文研究表明图神经网络可以通过可训练的可组装模块来解决含有符号和数值数据结构的 NP 完全问题，提供了一个解决 TSP 问题的高度自主的消息传递算法并且能够使用与目标成本 C 的偏差小于 2% 的决策实例进行训练。

    Sep, 2018

  • 使用置换不变汇聚网络学习多个旅行商问题

    本文设计一种神经网络方法，利用图网络方法将旅行商、城市和货站作为三个具有不同基数的集合，通过搜索方法和特定的损失函数来输出最优解，实验结果表明该方法优于现有领域最先进的元启发式算法。

    Mar, 2018

  • 旅行商问题学习范式

    探讨学习典范对旅行推销员问题的深度神经网络训练的影响，研究发现相较于受控实验的有标记数据的 SL 模型，强化学习（RL）模型对于变量大小的图形具有更好的紧急普遍性并是学习新组合问题的规模无关解算器的重要组成部分。

    Oct, 2019

  • 图卷积分支与界

    使用深度学习模型在优化流程中的有效性进行了论证，通过将图卷积分支限界与经典的分支限界算法相结合，实现了更快速的解决旅行商问题的路径的识别。

    Jun, 2024