arXiv:2608.00270cs.AI2026-08

通过几何自监督预训练,提升神经组合优化模型在大规模旅行商问题上的泛化与效率。

Geometric Self-Supervised Pre-training for Neural Combinatorial Optimization

论文配图:Geometric Self-Supervised Pre-training for Neural Combinatorial Optimization
图 1 · 摘自论文原文
  • 利用旋转和镜像等等距变换进行自监督预训练,学习空间不变性特征。
  • 在TSP1,000的零样本外推中,巡游长度比基线降低7.23%。
  • 相比精确求解器Concorde,推理速度提升达两个数量级,适合大规模部署。

神经组合优化(NCO)技术已成为解决旅行商问题(TSP)等路径规划问题的高效替代方案,但基于强化学习的模型在高维实例上泛化能力严重受限。尽管计算机视觉和自然语言处理领域已通过自监督预训练缓解此问题,但对缺乏复杂拓扑结构的路由图(仅含二维坐标)的应用仍具挑战。本文提出一种几何自监督预训练框架,旨在捕捉空间不变性与全局相对距离分布。通过施加等距变换(如旋转、轴反射),模型在策略优化前学习鲁棒结构表征。实验表明,该方法在大规模零样本外推场景(TSP1,000)中,相较从头训练模型,巡游长度平均减少7.23%。此外,所提模型计算效率极高,在大规模场景下推理速度相较精确求解器Concorde最高提升两个数量级。源代码与预训练模型已公开于https://github.com/davidaguadocosano/TSP-GeoPretrain.git。

原文摘要 · Abstract (English)

Neural Combinatorial Optimization (NCO) techniques have emerged as a highly efficient alternative to traditional exact algorithms for solving routing problems such as the Traveling Salesman Problem (TSP). However, the generalization capabilities of these Reinforcement Learning-based models are severely hindered when scaling to high-dimensional instances. This issue has been mitigated in other domains, like computer vision and natural language processing, by adopting a self-supervised pre-training strategy. Nevertheless, its application to routing graphs, which lack complex topological attributes beyond 2D spatial coordinates, remains a challenge. In this paper, we propose a geometric self-supervised pre-training framework specifically designed to capture spatial invariance and global relative distance distributions. By applying isometric transformations, such as rotations and axial reflections, the model learns robust structural representations prior to the policy optimization phase. Empirical results demonstrate that this strategy consistently outperforms models trained from scratch (baselines), achieving a 7.23\% improvement in tour length for massive zero-shot extrapolation scenarios (TSP1,000). Furthermore, the proposed model exhibits remarkable computational efficiency, delivering speedups of up to two orders of magnitude over the exact solver Concorde at massive scales. The source code and pre-trained models are publicly available at https://github.com/davidaguadocosano/TSP-GeoPretrain.git.

组合优化自监督学习几何不变性旅行商问题

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。