🤖 machine learning

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

本文介绍了 HeatACO，一种与预测器无关的解码器，它通过一种新颖的度感知证据因子，将非自回归 TSP 热图集成到最大-最小蚁群算法中，在无需针对特定预测器进行调优的情况下，在大型且多样化的 TSP 实例上实现了优于 MCTS 和标准基准模型的解质量与效率。

原作者： Bo-Cheng Lin, Yi Mei, Mengjie Zhang

发布于 2026-07-29

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Bo-Cheng Lin, Yi Mei, Mengjie Zhang

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你是一名快递员，手里拿着一张城市地图和一份需要完成的送货清单。你的目标是访问每一个站点且仅访问一次，最后回到家中，同时全程行驶的总距离最短。这就是著名的“旅行商问题”。这听起来很简单，但随着城市的规模扩大，可能路径的数量会爆炸式增长，以至于即使是世界上最强大的超级计算机也无法检查每一个选项来找到完美路径。因此，科学家们转向了人工智能来提供帮助。现代 AI 模型不再试图计算每一条路径，而是扮演着“资深侦察兵”的角色。它们观察地图并快速标出那些看起来很有希望的道路，创建出一张“热力图”，其中颜色最亮的部分显示了最有可能成为优秀路线的边缘。

然而，这里有一个陷阱。这些 AI 侦察兵擅长发现好的道路，但它们非常不擅长将这些道路连接成一段完整、有效的行程。它们可能会标出三条从同一间房子出发的不同道路，但真正的司机只能选一条。AI 给你的只是一堆凌乱的线索，你仍然需要一个聪明的解码器，将它们整理成一条单一的、可行的路线，而不陷入死循环或遗漏站点。大问题在于：如何在不针对每个新城市或地图规模重新训练 AI 的情况下，快速将这些模糊、凌乱的热力图转化为完美的路线？

这正是 HEATACO 背后的研究人员致力于解决的问题。他们开发了一种全新的通用解码器，充当这些 AI 热力图的“智能交通管制员”。HEATACO 并不只是盲目地跟随最亮的颜色或使用缓慢的试错法，它采用了一种受蚂蚁寻找食物启发而来的巧妙系统。

它是如何工作的呢？想象一下，一群蚂蚁正试图搭建一座桥。在旧的方法中，如果 AI 热力图说：“嘿，这条路超级亮！”解码器就会立即抓住它。但有时，这条亮的道路其实是一个陷阱。HEATACO 则更聪明。它观察热力图并询问：“这条路是否真的比其他路好得多，以至于即使我们还没尝试过，也值得去走？”它只关注那些真正具有确定性的线索，忽略噪音。然后，它让它的“蚂蚁”（实际上是计算机模拟）来构建路线。在构建过程中，它们会在使用的道路上留下数字“气味”（称为信息素）。如果一只蚂蚁发现了一条短小且优秀的路线，这种气味就会增强，告诉其他蚂蚁下次尝试那条路径。

HEATACO 的魔力在于它平衡了 AI 的初始猜测（热力图）与蚂蚁自身的经验（信息素）。它不会让 AI 的猜测完全主导一切；相反，它利用猜测来获得一个良好的开端，然后让蚂蚁在过程中不断优化路线。这意味着你可以使用来自任何训练好的 AI 模型的热力图——无论该模型是在小城镇还是大型城市中训练的——并使用 HEATACO 将其转化为优秀的路线，而无需重新训练 AI 或为每个新地图调整设置。

研究人员在一些巨大的挑战上对其进行了测试，包括拥有多达 10,000 个站点的地图。他们发现 HEATACO 比以往最好的方法更快，且能找到更好的路线，因为旧方法通常必须花费大量时间进行猜测和检查。它特别擅长在蚂蚁开始搜索之前，就将凌乱的 AI 线索转化为一个稳固的计划。然而，他们也发现了一个极限：一旦路线已经非常优秀，并且你开始使用强大的局部修正手段（比如通过交换几条道路来缩短行程），AI 最初的热力图就会变得不再那么有用。在这种情况下，传统的几何技巧同样有效。

简而言之，HEATACO 是一个多功能的工具，它弥合了凌乱的 AI 预测与完美旅行计划之间的鸿沟。它证明了你不需要为每个 AI 模型都准备一个不同的解码器；只要拥有“倾听专家”与“从经验中学习”之间的正确平衡，你就能快速高效地解决大规模的路径规划问题，无论城市规模变得多么庞大。

技术摘要：HEATACO —— 一种用于大规模 TSP 的热图引导最大-最小蚁群系统

1. 问题陈述

本文研究的是旅行商问题（TSP），特别关注非自回归（NAR）神经求解器的解码阶段。这些求解器通过单次前向传播预测边置信度热图，为潜在边分配分数。然而，热图并非有效的路径；它通常包含不连通的环路、违反度约束（节点具有超过两条入射边）以及包含假阳性。

核心挑战是热图到路径的解码问题：如何将固定的稠密热图（ $O(n^2)$ 个分数）转换为满足全局约束的可行哈密顿回路（ $n$ 条边）。现有的解码器面临权衡：

贪婪合并（Greedy Merging）： 速度快且具有确定性，但产生的路径质量较低，因为它无法修正早期可能产生误导的边选择。
MCTS 引导的 k-opt 搜索： 能产生更高质量的路径，但计算成本高昂，需要针对特定预测器调整超参数（如探索常数），并且依赖于针对每个实例的树搜索。

作者认为，需要一种与预测器无关的解码器，能够将来自不同预训练模型的热图转换为可行路径，而无需重新训练或特定调优，同时保持计算效率和高解质量。

2. 方法论：HEATACO

作者提出了 HEATACO，这是一种基于最大-最小蚁群系统（MMAS）的可扩展解码器，MMAS 是蚁群优化算法（ACO）的一种鲁棒变体。HEATACO 通过一种新颖的受限且具备度感知能力的证据因子，将固定热图集成到 MMAS 的构建规则中。

核心组件：

候选列表构建：
- 算法并不考虑所有 $O(n^2)$ 条边，而是将构建过程限制在每个节点大小为 $k=20$ 的稀疏候选列表中。
- 候选边的选择基于热图（置信度 $> \theta_h$ 的边），并在热图稀疏时使用最近邻进行填充，以确保连通性。
度感知证据偏差 ( $e_{ij}$ )：
- 热图被视为序数证据而非校准后的概率。
- 对于每个节点，根据第 $(d^*+1)$ 高的置信度边计算度基准（ $b_i$ ），其中 $d^*$ 是路径度（对称 TSP 为 2，ATSP 出度为 1）。
- 边的证据因子 $e_{ij}$ 是其置信度与该基准的比值，并设定最小值为 1。这确保了只有当边的置信度超过其接受容量时，才会获得偏差提升，从而过滤掉那些仅仅是在众多相似选项中表现较好的“噪声”高置信度边。
自动缩放 ( $\kappa$ )：
- 为了防止热图永久性地覆盖信息素反馈（信息素负责学习特定实例的结构），证据偏差的强度 ( $\kappa$ ) 会进行自动缩放。
- $\kappa$ 由信息素动态范围 ( $\tau_{max}/\tau_{min}$ ) 和证据因子对数差值的第 90 百分位数导出。
- 这种缩放确保了热图在早期采样阶段发挥作用，同时允许信息素反馈在搜索过程中纠正误导性的引导。单一配置即可适用于不同的预测器而无需重新训练。
搜索过程：
- 初始化： 使用最近邻路径初始化信息素边界。
- 构建： $m$ 只蚂蚁并行构建路径，使用结合了信息素、启发式距离和热图证据因子的伪随机比例规则。
- 更新： 信息素会发生挥发，并通过迭代中的最佳路径（或重启/全局最佳路径）进行强化。
- 局部搜索： 可选的 2-opt 或 3-opt（针对对称 TSP）或定向 2-opt（针对 ATSP）被用于在信息素更新前精炼路径。

3. 主要贡献

一个与预测器无关的解码器： HEATACO 可以解码来自多种预训练模型（AttGCN, DIMES, UTSP, DIFUSCO）的热图，而无需重新训练预测器或为每个模型单独调优解码器。
受限且度感知的证据： 一种仅在边超过节点度容量时才给予奖励的机制，防止解码器被稠密且缺乏辨别力的热图所淹没。
自动缩放： 一种将热图偏差相对于信息素动态范围进行缩放的方法，确保了在不同热图质量和实例规模下的鲁棒性。
全面的评估： 该方法在 TSP500、TSP1K、TSP10K 以及分布外（OOD）基准测试（聚类、高斯、TSPLIB）和非对称 TSP（ATSP）上进行了评估。

4. 实验结果

论文将 HEATACO 与标准 MMAS、贪婪合并以及 MCTS 引导的 k-opt 搜索在四种热图来源下进行了对比。

对比贪婪合并： HEATACO 显著优于贪婪解码，将最优性差距从 >10%（在大规模实例上通常 >30%）降低到了接近最优的水平。
对比 MCTS： 在分布内基准测试（TSP500, TSP1K, TSP10K）中，带有 2-opt 的 HEATACO 比发表的 MCTS 基准在相同的固定热图下实现了更低的最优性差距和更短的解码时间。例如，在 TSP1K 上，HEATACO+2-opt 在约 4–8 秒内达到 ~0.2–0.4% 的差距，而 MCTS 在约 100 秒内达到 ~0.5–1.5% 的差距。
对比标准 MMAS：
- 构建阶段： 热图引导显著提高了所有预测器和规模下的初始构建质量，在局部搜索之前降低了几个百分点的差距。
- 结合局部搜索：
  - 在 TSP500 和 TSP1K 上，即使使用 2-opt 和 3-opt，HEATACO 仍然保持优势，尽管随着局部搜索强度的增加，边际收益有所下降。
  - 在 TSP10K 上，在强局部搜索（3-opt）之后，热图引导的优势减弱或反转。论文将其归因于互补性降低：强大的几何修复（3-opt）可以独立恢复路径结构，使得热图的贡献变得冗余，甚至如果热图将搜索引导偏离了几何最优路径，则可能产生负面影响。
泛化能力：
- ATSP： HEATACO 很好地迁移到了非对称 TSP，在局部搜索（定向 2-opt）较弱的场景下显示出显著收益。
- 分布偏移： 在 OOD 数据（聚类、高斯、TSPLIB）上的表现与热图可靠性相关。当热图保持稀疏且具有辨别力时（例如 DIFUSCO 在 TSPLIB 上），HEATACO 表现成功。当热图变得过于稠密或失去辨别力时（例如 DIMES 在 pr1002 上），性能会下降。
- SoftDist 控制： 针对非学习型“SoftDist”热图（纯粹基于距离）的实验表明，在具有强局部搜索的大规模场景下，几何先验通常已经足够，这进一步证实了学习到的热图仅在提供超越简单邻近性的结构时才具有价值。

5. 重要性与主张

论文声称 HEATACO 提供了一个通用的、自动缩放的过程，用于将不同预训练模型的热图转换为可行路径。其重要性在于：

解耦预测与解码： 它允许研究人员重复使用现有的热图预测器，而无需重新训练它们或为每个模型调整特定的解码器。
效率： 与 MCTS 相比，它实现了最先进的解码速度和解质量，而 MCTS 在处理大规模问题时计算成本过高。
诊断见解： 该工作指出，学习到的热图的价值受限于两个因素：热图可靠性（在分布偏移下）以及与局部搜索的互补性（在大规模场景下几何修复能力较强时）。
实用价值： 它为神经组合求解器提供了一个鲁棒的后备方案或增强手段，特别是在局部搜索较弱（如 ATSP）或需要快速解码的场景下。

作者谦虚地总结道，虽然神经热图功能强大，但它们并不总是优于经典搜索；其效用取决于边证据的质量以及可用的几何修复强度。作者建议未来的工作可以将这些诊断工具结合起来，以动态选择是在 HEATACO 还是纯 MMAS 之间进行切换。