Jun, 2019

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

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

    文章提出一种基于深度学习和启发式算法的图卷积网络方法，用于解决某些NP困难问题，并在四个NP困难问题和五个数据集上进行了评估，结果表明该方法在某些NP困难问题上已经达到了高度优化的最新启发式算法的水平，并具有较强的泛化性和扩展性。

    Oct, 2018

  • 旅行商问题学习范式

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

    Oct, 2019

  • 解决路径规划问题学习改进启发式方法

    本文提出一种基于self-attention的深度强化学习框架，以学习解决旅行商问题（TSP）和有容量车辆路径问题（CVRP）的改进启发式算法，实验表明该方法性能优于现有的深度学习方法，并且具有良好的泛化能力。

    Dec, 2019

  • 旅行商问题的Transformer网络

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

    Mar, 2021

  • 解决旅行推销员问题的无监督学习

    我们提出了UTSP，这是一个用于解决旅行推销员问题（TSP）的无监督学习框架，使用基于图神经网络（GNN）的代理损失。该方法在参数效率和数据效率方面优于目前的数据驱动TSP启发式方法。

    Mar, 2023

  • 一种轻量级的CNN-Transformer模型用于学习旅行商问题

    本研究提出了一种基于CNN嵌入层和局部自注意力的轻量级CNN-Transformer模型，相对于标准Transformer模型，该模型能够更好地从输入数据中学习空间特征，同时通过局部自注意力减少全连接注意模型中的冗余性。实验结果表明，我们提出的模型在解决TSP问题的质量、GPU内存使用和推理时间等方面优于其他最先进的Transformer-based模型。

    May, 2023

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

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

    Oct, 2023

  • 无监督学习中旅行商问题的规模和难度泛化

    探讨无监督学习在解决旅行推销员问题中的泛化能力，通过训练图神经网络并使用嵌入来构建边缘的热图，同时研究不同的训练实例大小、嵌入维度和分布对无监督学习方法结果的影响，结果表明使用较大的实例规模和增加嵌入维度可以构建更有效的表示，提高解决旅行推销员问题的能力，并发现在不同分布上进行泛化评估时，选择更困难的实例作为训练数据可以使模型具备更好的泛化能力。

    Mar, 2024

  • 图卷积分支与界

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

    Jun, 2024

  • 用于边缘图问题（如旅行商问题）的GREAT架构

    本研究针对图神经网络在处理密集图和非欧几里得路由问题中的局限性，提出了一种新颖的边缘基础神经模型——图边注意力网络（GREAT）。通过在旅行商问题的边分类任务中评估GREAT的性能，研究发现GREAT能够有效地生成稀疏图实例，同时保持大部分最优边，从而在处理欧几里得和非欧几里得旅行商问题时达到最先进的结果。

    Aug, 2024