arXiv:2601.19041cs.NEcs.LG2026-01

用热力图指导蚁群算法,高效求解大规模旅行商问题。

HeatACO: A Heatmap-Guided Max--Min Ant System for Large-Scale Travelling Salesman Problems

  • 设计基于热力图的蚁群算法,自动融合边缘置信度与节点度数约束。
  • 在TSP500/1K/10K上比MCTS更快生成更优解,且无需调参。
  • 适用于多种预测器和分布外场景,可迁移性强。

非自回归神经求解器可在一次前向传播中预测旅行商问题(TSP)的边置信度热力图,但需通过解码器生成可行哈密顿环。随着实例规模增大,必须协调二次数量的边评分与全局路径约束。贪婪合并速度快但质量低,而基于k-opt移动的蒙特卡洛树搜索(MCTS)虽能恢复高质量解,但计算开销大且需针对预测器调参。我们提出HeatACO,一种不依赖预测器的热力图到路径解码器。其核心是一个有界、度数感知的证据因子,将固定热力图融入最大-最小蚁群系统(MMAS)。该因子仅奖励超出节点路径度容量的边置信度,其强度自动按信息素动态范围缩放,使单一配置可解码不同预测器的热力图,无需重训练或逐预测器调参。在四个热力图来源上,HeatACO在TSP500、TSP1K和TSP10K上均以更短解码时间生成更高质量解,优于MCTS基线。与相同搜索预算的标准MMAS基线相比,热力图引导在所有四个预测器的两个尺度下均提升构造质量,并在局部搜索后仍具优势。HeatACO在多种分布偏移及对称性缺失的TSP(ATSP)上也表现良好。后验分析识别出与性能变化相关的可测量热力图特性。

原文摘要 · Abstract (English)

Non-autoregressive neural solvers predict an edge-confidence heatmap for the Travelling Salesman Problem (TSP) in one forward pass, but a decoder must still produce a feasible Hamiltonian cycle. As instance size grows, this stage must reconcile a quadratic number of edge scores with global tour constraints. Greedy edge merging is fast and deterministic but produces low-quality tours, whereas Monte Carlo Tree Search (MCTS) over k-opt moves recovers better tours at high computational cost and requires predictor-specific tuning. We propose HeatACO, a predictor-agnostic heatmap-to-tour decoder. Its key is a capped, degree-aware evidence factor that integrates a fixed heatmap into a Max--Min Ant System (MMAS). The factor rewards only edge confidence beyond a node's tour-degree capacity, and its strength is scaled automatically from the pheromone dynamic range, allowing one configuration to decode heatmaps from different predictors without retraining or per-predictor tuning. Across four heatmap sources, HeatACO produces higher-quality solutions in less decoding time than the MCTS baseline on TSP500, TSP1K and TSP10K. Against matched standard MMAS baselines with the same search budget, heatmap guidance improves construction for all four predictors at both scales and remains beneficial with local search. HeatACO also transfers competitively to several distribution shifts and the asymmetric TSP (ATSP). Our post-hoc analysis identifies measurable heatmap properties associated with the observed performance variation.

旅行商问题蚁群算法热力图解码器

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