基于对称对齐的组合优化神经求解器

《Theoretical Computer Science》：Symmetry Alignment based Neural Solver for Combinatorial Optimization

　　摘要：通过采用机器学习技术，组合优化在精度和计算效率方面取得了显著进步。然而，以往的研究并未充分考虑组合优化中固有的对称性。本文提出了一种新的训练方法SA-NS，该方法利用基于正则化的手段来利用各种组合优化问题及其解中存在的普遍对称性。通过利用对称性对齐，这种方法大大提升了神经启发式求解器的泛化能力，使学习到的求解器能够有效利用同一类组合优化问题中的共同对称性。实验表明，SA-NS在不依赖特定问题领域专业知识的情况下，显著提升了两种组合优化问题——旅行商问题与带容量约束的车辆路径问题——中神经求解方法的性能。

引言：组合优化问题在计算机科学和运筹学中起着至关重要的作用。由于它们属于NP难问题，精确算法往往存在可扩展性限制，而传统的启发式方法则通常需要针对不同问题类型进行大量的人工设计和专家知识输入。近年来，利用机器学习自动学习多种组合优化问题中的启发式策略的神经网络方法引起了广泛关注[1]。通过识别多个问题实例之间的共享结构，这些模型能够在降低计算负担的同时获得高质量解决方案。本研究聚焦于车辆路径问题，这是NP难问题中一个著名的子类，在交通[2]、[3]、[4]以及物流[5]、[6]等领域有着广泛应用。

最初，用于解决车辆路径问题的早期神经启发式方法严重依赖于监督学习技术[7]、[8]。这些方法需要真实的标签来进行训练，而获取最优解可能耗费大量计算资源。相比之下，强化学习则利用来自环境的反馈，而非仅仅依赖最优解作为标签。这种方法使得神经启发式在解决车辆路径问题时更为有效[9]。强化学习常被用来训练决定在车辆路径问题中下一个访问客户或节点的网络[10]、[11]、[12]、[13]。与监督学习方法相比，这种方法在处理不同规模的问题时展现出更强的泛化能力。

尽管最近有研究尝试将深度强化学习应用于车辆路径问题，但这些方法大多忽视了一个重要特征：车辆路径问题中固有的对称性。例如，像旅行商问题这样的问题通常在二维欧几里得空间中描述，其解需要在城市坐标的几何变换下保持不变，比如旋转、反射和平移。忽略这些几何对称性会导致冗余计算和次优学习，因为强化学习可能会错误地将对称实例视为不同的实例，从而浪费计算资源。此外，强化学习通常也忽视了解的对称性，在强化学习的序列决策框架中，旅行商问题中的最优哈密顿回路可能对应多个等价的序列或路径。这种忽视意味着强化学习可能会收敛到最优解的一种表示形式，而忽略其他形式，从而可能影响所学策略的稳健性和泛化能力。

解决解的对称性问题对于确保强化学习模型能够在不同但等价的最佳解表示之间有效泛化至关重要。利用对称性作为一种强大的归纳偏见，有助于通过有效约束训练空间来促进强化学习训练。

最近有一些研究试图将对称性纳入组合优化的神经求解器中，但大多数研究都集中在利用特定类型的对称性上。例如，POMO[12]主要通过考虑游程的多个等价起点来利用解（路径）的对称性，而Sym-NCO[14]则进一步纳入了问题实例的旋转变换。还有其他研究探讨了利用旅行商问题中哈密顿游程的循环对称性的强化学习启发式方法[15]。虽然这些方法展示了考虑对称性学习的潜在优势，但它们通常只关注有限形式的对称性，且多为特定路由结构设计。相比之下，许多组合优化问题——尤其是那些在欧几里得空间中定义的问题——具有更丰富的对称性结构，包括旋转、反射、缩放、平移以及解层面的排列对称性。

为了更好地利用这些结构，我们提出了一种新方法，将对称性纳入神经启发式求解器的训练中。我们的方法基于最近提出的流匹配学习范式[16]，构建了一种生成式架构，专门用于训练能够生成与目标奖励分布相一致的有序解的随机策略。该框架以流匹配损失函数为核心，该函数能够在解层面捕捉对称性，同时还结合了均方误差项和正则化项，以对问题表述本身施加对称性约束。我们将车辆路径问题视为序列决策任务，利用自回归机制逐步确定访问地点的顺序。每个生成的序列在生成树中对应一条独特的路径，模型会在其边上分配转移概率。为保持原始实例与其对称变换后的对应物之间的一致性，我们引入了一个偏差正则化项，用以惩罚这些变体之间流值的差异。我们在包括旅行商问题和带容量约束的车辆路径问题在内的经典路由基准测试上验证了我们提出的方法——即SA-NS。实验结果表明，与传统的基于强化学习的求解器相比，我们的方法具有更出色的性能。此外，我们还进行了消融实验，以确定并确认我们框架中各组件的作用。我们的主要贡献可总结如下：——我们提出了利用对称性解决组合优化问题，尤其是车辆路径问题的构造性方法。在神经网络训练过程中，可以通过对称性对齐的方法来利用这些对称性。——我们提出了一种基于组合优化问题对称性的高效学习方法，该方法利用无监督学习和对比学习来对齐组合优化问题的对称实例和对称解。——我们使用旅行商问题和带容量约束的车辆路径问题的合成数据集以及真实世界的大规模数据集，验证了我们模型的效率和有效性。实验结果表明，与基于注意力模型的以往数据驱动方法相比，我们的模型在解决方案质量方面具有更好的泛化能力和稳定性。

章节节选：传统方法。用于解决旅行商问题和带容量约束的车辆路径问题的传统方法已经得到了深入研究，涵盖了精确方法和近似（启发式及近似）方法[17]。对于旅行商问题，著名的精确算法包括分支定界法[18]和动态规划法[19]，而像最近邻法[20]、2-opt法[21]和LKH法[22]这样的启发式方法也备受重视。同样，解决车辆路径问题也采用了诸如分支定界法之类的精确算法。

问题表述：本研究探讨了组合优化领域的车辆路径问题。车辆路径问题设定在二维欧几里得空间中。受限车辆路径问题通常可以表述为以下优化问题：

问题1：车辆路径问题。给定一组城市坐标X={x1,x2,?,xN}?R2，目标是找到一条最优路线τ={τ(1),?,τ(N)}，使得路线覆盖的总长度L(τ, X)最小。车辆路径问题的目标函数可形式化为如下：

minτ∈T

方法：本节介绍了我们的神经求解器Fθ的训练流程，该求解器是在一种具有对称性意识的学习框架下开发的，用于解决车辆路径问题。

基准与指标：我们在旅行商问题和车辆路径问题任务上，将我们提出的方法与强大的基准模型进行了对比。这些基准模型包括传统的、不可学习的启发式求解器，如Concorde[55]、LKH3[26]和Gurobi[56]，以及最近的基于学习的构造性方法，如AM[11]、POMO[12]、MDAM[57]和Sym-NCO[14]。为了评估性能，我们考虑了三个关键指标：行程成本（Obj）、与最优解的差距（Gap）以及推理时间（Time）。这些指标的数值越低越好。

结论：我们的研究解决了利用无监督学习方法解决车辆路径问题的挑战。我们通过引入用于车辆路径问题任务的原理性SA-NS决策框架，为这一领域做出了贡献。通过将概率推理与序列决策相结合，SA-NS为在车辆路径问题中发现多种高质量候选解提供了一种有前景的方法。通过全面的数值实验，我们证明了该方法的有效性。

CRediT作者贡献声明：张子珍：撰写——初稿、验证、监督、方法论、概念构思。饶国耀：撰写——审阅与编辑。李德英：撰写——审阅与编辑、资金获取。王永才：撰写——审阅与编辑。陈文平：撰写——审阅与编辑、概念构思。朱玉清：撰写——审阅与编辑、概念构思。

利益冲突声明：作者声明他们没有已知的、可能影响本文所报告工作的财务利益或个人关系。

张子珍|饶国耀|李德英|王永才|陈文平|朱玉清
中国北京网络学院