稀疏化对于 Transformer 和 Graph 神经网络在 TSP 中的重要性

Mar, 2024

稀疏化对于 Transformer 和 Graph 神经网络在 TSP 中的重要性

Less Is More - On the Importance of Sparsification for Transformers and Graph Neural Networks for TSP

Attila Lischka, Jiaming Wu, Rafael Basso, Morteza Haghir Chehreghani, Balázs Kulcsár

TL;DR对于旅行推销员问题 (TSP) 进行路由问题的研究中，提出了一种数据预处理方法，使用图稀疏化和注意力掩码来将编码器聚焦于 TSP 实例的关键部分，实验结果显示，适当的图稀疏化和注意力掩码方法可以显著提高整体架构的性能。

Abstract

Most of the recent studies tackling routing problems like the Traveling Salesman Problem (TSP) with machine learning use a transformer or Graph Neural Network (GNN) based encoder architecture. However, many of th

routing problems traveling salesman problem machine learning graph sparsification attention masking

发现论文，激发创造

探索图转换中的稀疏性

研究论文简介：为解决图形变换器（GTs）的高计算成本问题，在现有 GT 模型特征的基础上探索了图形变换器稀疏化的可行性，并提出了一个能够减少 GTs 计算复杂度的综合框架（GTSP），通过实验验证该框架能有效降低计算成本，同时在精度上只有微弱的降低或甚至有所提升。

Dec, 2023

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

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

May, 2023

旅行商问题的 Transformer 网络

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

Mar, 2021

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

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

Oct, 2023

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

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

Sep, 2018

面向旅行商问题的图神经网络引导局部搜索

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

Oct, 2021

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

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

Jun, 2020

无位置编码的图形变换器

Eigenformer 通过一种新颖的对 Laplacian 谱意识的注意机制，在一些标准的图神经网络基准数据集上实现了与最先进的 MP-GNN 体系结构和 Graph Transformers 相当的性能，甚至在某些数据集上超越了最先进的方法。此外，我们发现我们的架构在训练速度方面要快得多，可能是由于内在的图归纳偏置。

Jan, 2024

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

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

Mar, 2024

在多个分辨率下解决路由问题的保持对称性的图注意力网络

通过多分辨率和对称性保持，我们提出了一种新的数据驱动方法来解决旅行推销员问题和车辆路径问题。实验证明，我们的模型超过了现有的基准线，并证明了对称性保持和多分辨率对于解决组合问题的重要性。

Oct, 2023