NeuFACO: Neural Focused Ant Colony Optimization for Traveling Salesman Problem

📄 arXiv: 2509.16938v2 📥 PDF

作者: Dat Thanh Tran, Khai Quang Tran, Khoi Anh Pham, Van Khu Vu, Dong Duc Do

分类: cs.NE, cs.LG

发布日期: 2025-09-21 (更新: 2025-09-23)

备注: Submitted to RIVF'25. Code is available at https://github.com/shoraaa/NeuFACO

💡 一句话要点

提出NeuFACO，结合神经启发式与蚁群优化求解旅行商问题

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)

关键词: 旅行商问题 蚁群优化 图神经网络 强化学习 近端策略优化

📋 核心要点

  1. 旅行商问题求解面临计算复杂度和解质量的挑战，传统方法难以在效率和精度间取得平衡。
  2. NeuFACO的核心在于利用图神经网络学习实例相关的启发式信息，指导蚁群算法更高效地搜索优质解。
  3. 实验表明，NeuFACO在不同规模的TSP实例上均能产生高质量的解，验证了其有效性和泛化能力。

📝 摘要（中文）

本研究提出了一种名为神经聚焦蚁群优化（NeuFACO）的非自回归框架，用于解决旅行商问题（TSP）。NeuFACO结合了先进的强化学习和增强的蚁群优化（ACO）。它利用近端策略优化（PPO）与熵正则化来训练图神经网络，从而为特定TSP实例提供启发式指导。该启发式指导被集成到一个优化的ACO框架中，该框架具有候选列表、受限路径改进和可扩展的局部搜索。通过利用摊销推理以及ACO的随机探索，NeuFACO能够有效地为各种TSP实例生成高质量的解决方案。

🔬 方法详解

问题定义：论文旨在解决旅行商问题（TSP），即寻找访问一系列城市并返回起点的最短路径。现有方法，如传统蚁群算法，在面对大规模TSP问题时，收敛速度慢，容易陷入局部最优。而基于深度学习的方法，虽然速度快，但解的质量往往不如传统算法。

核心思路：NeuFACO的核心思路是将深度学习的优势（快速生成启发式信息）与蚁群算法的优势（强大的全局搜索能力）相结合。通过训练一个图神经网络来预测每个城市之间的转移概率，从而引导蚂蚁在搜索过程中更有针对性地选择路径，加速收敛并提高解的质量。

技术框架：NeuFACO的整体框架包含两个主要部分：1) 基于PPO的图神经网络训练阶段，用于学习实例相关的启发式信息；2) 基于优化ACO的求解阶段，利用学习到的启发式信息指导蚂蚁进行路径搜索。具体流程如下：首先，使用PPO训练图神经网络，使其能够根据TSP实例的特征预测城市之间的转移概率。然后，将这些转移概率作为启发式信息融入到ACO算法中，指导蚂蚁构建路径。最后，通过局部搜索和路径重优化等技术进一步提高解的质量。

关键创新：NeuFACO的关键创新在于将深度学习的摊销推理能力与ACO的随机探索能力相结合。传统的ACO算法依赖于固定的启发式信息（如距离），而NeuFACO能够根据不同的TSP实例动态地生成启发式信息，从而更好地适应不同的问题特征。此外，NeuFACO还采用了受限路径改进和可扩展的局部搜索等优化技术，进一步提高了算法的性能。

关键设计：NeuFACO使用图神经网络来学习启发式信息，网络结构未知（原文未详细说明）。PPO算法用于训练该网络，目标是最大化蚂蚁找到高质量解的概率。损失函数包括奖励函数（基于路径长度）和熵正则化项，用于鼓励探索。ACO算法的关键参数包括信息素挥发率、启发式信息权重等，这些参数需要根据具体问题进行调整。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

论文提出的NeuFACO在多个TSP数据集上进行了实验，结果表明，NeuFACO能够生成高质量的解，并且在求解速度上优于传统的ACO算法。具体的性能数据未知（原文未提供具体的数值结果），但强调了其在效率和解质量上的提升。

🎯 应用场景

NeuFACO在物流配送、交通运输、电路设计等领域具有广泛的应用前景。它可以用于优化车辆路线、降低运输成本、提高资源利用率。此外，NeuFACO的框架也可以推广到其他组合优化问题，例如车辆路径问题、作业车间调度问题等，具有重要的实际应用价值和潜在的经济效益。

📄 摘要（原文）

This study presents Neural Focused Ant Colony Optimization (NeuFACO), a non-autoregressive framework for the Traveling Salesman Problem (TSP) that combines advanced reinforcement learning with enhanced Ant Colony Optimization (ACO). NeuFACO employs Proximal Policy Optimization (PPO) with entropy regularization to train a graph neural network for instance-specific heuristic guidance, which is integrated into an optimized ACO framework featuring candidate lists, restricted tour refinement, and scalable local search. By leveraging amortized inference alongside ACO stochastic exploration, NeuFACO efficiently produces high-quality solutions across diverse TSP instances.