图约束扩散与渐进蒸馏求解旅行商问题：从GCDTSP到GCDTSP-D

《Big Data and Cognitive Computing》：Graph-Constrained Diffusion with Progressive Distillation for Traveling Salesman Problem

　　

扩散模型在神经组合优化中展现出强大潜力，然而现有方法在全连接图上定义前向加噪过程，丢弃了旅行商问题（TSP）固有的稀疏拓扑结构，其多步推理也带来了高昂的延迟。研究人员通过一对互补模型解决了这两个局限。首先，研究人员提出GCDTSP，一种图约束扩散模型，将拓扑无关的均匀转移矩阵替换为基于实例相关的图拉普拉斯热核转移矩阵，使得边值状态的演化由每个TSP实例的拓扑结构所控制；结合节点度保持、对称性和局部性先验的可行性约束损失进一步引导GatedGCN去噪网络生成有效的哈密顿回路。GCDTSP在贪心解码下优于自回归基线和先前的扩散求解器，并可零样本泛化到真实世界的TSPLIB实例。在GCDTSP基础上，研究人员提出GCDTSP-D，一种渐进蒸馏框架，通过师生参数继承迭代地将所需去噪步数减半，并结合余弦噪声调度，将推理能力集中在约束敏感的低噪声区间。GCDTSP-D在TSP50上实现了约37倍加速，且质量-速度权衡良好；在更大的TSP500基准上，甚至在解质量和速度两方面均超过其教师模型。

旅行商问题（TSP）是组合优化中研究最广泛的NP-hard问题之一，在物流、电路设计、机器人等领域具有广泛应用。给定n个城市，TSP要求寻找访问每个城市恰好一次的最短哈密顿回路。精确求解器如分支定界和割平面法在数百个城市之外计算代价过高；经典启发式如Lin-Kernighan和Christofides算法依赖人工设计的搜索规则。神经组合优化（NCO）方法通过学习模型来求解新实例，其中自回归方法逐城构建回路，顺序解码成本随规模增长；非自回归方法并行预测边概率，但可能违反度与子回路约束。扩散模型在图像、分子等生成任务上表现优异，DIFUSCO等将图扩散引入TSP，证明其作为非自回归求解器的潜力。然而，现有扩散方法存在两个主要局限：一是使用与实例无关的均匀转移矩阵，丢弃了TSP固有的稀疏拓扑结构；二是多步去噪需要多次网络评估，推理延迟高。为此，研究人员提出GCDTSP与GCDTSP-D两个互补模型。GCDTSP用图拉普拉斯热核转移矩阵替代均匀转移矩阵，使前向加噪由实例拓扑引导，并设计可行性约束损失引导GatedGCN去噪网络生成有效回路；GCDTSP-D通过渐进蒸馏和余弦噪声调度大幅减少推理步数，在TSP50上实现约37倍加速，在TSP500上超越教师模型。该研究证明图结构先验是扩散组合优化的有效归纳偏置，且结构归纳偏置与加速蒸馏相互兼容。

研究人员使用的主要关键技术包括：基于图拉普拉斯L构造实例相关热核转移矩阵Q_t=exp(-β_tL)，利用闭式累积实现前向扩散；设计由度守恒、对称性和局部性损失组成的可行性约束损失，与交叉熵联合训练；采用GatedGCN去噪网络，在节点与边特征演化中注入时间步信息；渐进蒸馏中，学生模型以单步匹配教师两步去噪结果，并采用参数继承和余弦噪声调度；推理使用贪心边插入和2-opt局部搜索。