利用张量网络方法探索旅行商问题的解空间

《Physica A: Statistical Mechanics and its Applications》：Exploring the solution space of the traveling salesman problem using tensor network methods

　　摘要：旅行商问题是一种经典的组合优化NP难问题，其研究范围不仅限于寻找最优路径。从更广泛的角度来看，重要的一点是分析解空间的结构，包括接近最优的路径以及具有统计意义的边。在本研究中，我们提出了一种基于物理原理的张量网络框架，用于对开放型旅行商问题进行统计力学分析，该框架以二次无约束二元优化问题为起点。在该框架中，我们构建了可行路径上配分函数的张量表示，这使得可以直接从路径集合中计算热力学可观测量、边的重要性度量以及接近最优路径的统计特征。在Burma14基准测试及额外设计的实例上的数值实验表明，该精确收缩方法能够还原出最优开放路径的长度，并能捕捉到解的简并性、扰动敏感性以及接近最优路径的结构。我们还分析了收缩算法的计算复杂度，它与城市数量呈指数关系：配分函数Z的精确计算复杂度为O(N22N)。随后通过奇异值分解将绑定维度控制在D，以此平衡精度与内存使用之间的权衡。目前的实现已在小型和中等规模的开放型旅行商问题实例上得到验证，同时也探讨了将其扩展到更大规模经过剪枝的图以及相关旅行商优化问题上的可能性。总体而言，该方法为分析旅行商问题解空间的统计结构提供了一种张量网络工具。

引言：旅行商问题是一种经典的组合优化问题，也是路由规划任务的标准模型。虽然标准的旅行商问题通常被表述为闭合回路，但许多实际路径是开放的：路径从一个地点开始，到另一个地点结束，不会返回起点。例如，送货或服务路径的终点可能是与起点不同的仓库，或者机器人从入口点移动到出口点的检测路径。其他例子还包括沿定向走廊的交通或乘客调度，以及仅涉及单向行驶的路径规划任务。在这些情况下，添加人为的回程边可能会扭曲目标，因为返回起点的成本并不对应于实际的必要操作。除了找到最短的开放路径外，了解是否存在多条几乎等效的路径也很有用。此外，识别在良好解中始终稳定的路径段，以及评估路径结构对距离矩阵变化的敏感度也很重要。这就促使人们分析解空间，而不仅仅是为了寻找最短路径。

现有的旅行商问题解决方法不仅在实现方式上有所不同，其设计目的也各异。传统的精确方法，包括动态规划方法，能够提供最优性保证，但其成本会随着城市数量的增加而呈指数级上升。启发式和局部搜索方法则放宽了这类保证，因此更适合处理更大的问题实例，但它们的主要输出仍然是一条路径或一组候选路径[1]、[2]、[3]、[4]。基于学习的方法也遵循类似的路径导向逻辑。例如，指针网络将旅行商问题视为生成城市排列的问题[5]，而强化学习方法则训练一种策略，利用路径长度作为奖励信号来预测排列的分布[6]、[7]、[8]、[9]。这些方法在生成高质量路径方面效果显著，因此成为衡量路径搜索性能的重要基准。

除了传统和基于学习的算法之外，受生物启发的、智能的以及其他非传统的计算范式也被应用于旅行商问题。例如，遗传算法通过交叉和变异操作来探索路径表示，并已被系统地研究作为启发式旅行商问题求解器[10]。分子和DNA计算方法则提供了更为独特的思路。在Adleman–Lipton模型中，标准旅行商问题[11]以及一系列旅行商问题[12]都是通过分子操作来编码的。这些操作旨在利用大规模并行性。这些工作拓宽了旅行商问题计算的算法和物理层面。然而，它们的主要目标仍然是构建或提取可行的或最优的路径。相比之下，本研究的重点在于表示可行路径集合本身，并提取关于其结构的汇总信息。

二次无约束二元优化问题、伊辛模型以及统计力学公式更接近本研究的内容，因为它们都是用能量函数来表达旅行商问题或相关的组合优化问题[13]、[14]、[15]、[16]。在二次无约束二元优化问题的表述中，路径长度会影响哈密顿量，而惩罚项则用于确保路径的有效性[13]。这为与统计物理学、量子退火以及受量子启发的优化方法建立了自然的联系。不过，在大多数以优化为目的的使用此类公式的情况下，哈密顿量主要是作为寻找基态或低能量状态的目标。此时的核心任务是找到与较短路径相对应的二进制配置、自旋赋值或算法状态[17]、[18]、[19]、[20]、[21]、[22]。因此，尽管基于能量的公式形式上可以引入配分函数，但有限温度下的系综及其可观测量通常并非主要的计算对象。

张量网络方法也被应用于组合优化以及旅行商问题。现有的旅行商问题张量网络表述主要以路径搜索为导向。特别是参考文献[23]中，构建了候选路径的叠加态，并应用虚时间演化，使得低成本路径相对于高成本路径得到放大，最终目标是提取出最优或接近最优的路径。本研究在计算目标上有所不同。我们并非主要将张量网络用作路径搜索的工具，而是构建了可行开放型旅行商问题路径集合的配分函数的张量网络表示，并利用它来计算系综的可观测量。因此，关键区别不在于是否使用了张量网络，而在于张量网络计算的目标：参考文献[23]中的路径提取，而本研究则是计算配分函数及边际可观测量。

这一区别定义了本研究的创新点与研究范围。所提出的方法是对现有旅行商问题求解器的补充：它并非旨在成为一种渐进更快的一般用途旅行商问题算法。其在应用层面的贡献在于，将张量网络收缩作为一种工具，用于对开放型旅行商问题的可行路径集合进行统计力学分析。从二次无约束二元优化问题表述出发，我们将计算范围限制在可行的开放路径上，从而能够从同一路径集合中获得Z(β)、自由能、内能、熵、边的重要性度量以及接近最优路径的统计信息。

本研究的主要贡献可总结如下。理论贡献在于提出了开放型旅行商问题的路径集合表述，其中配分函数是直接在可行的开放路径上定义的，而非在不受限制的二进制配置上。这建立在标准的二次无约束二元优化问题和统计力学观点之上，但将可行路径集合作为明确的研究对象。方法论贡献在于提出了一种张量网络收缩流程，可用于计算热力学可观测量、边的重要性度量以及接近最优路径的统计信息，而无需将分析简化为单一的最优路径。数值贡献在于在Burma14基准测试及额外设计的实例上对该框架进行了验证，这些实例包括存在简并最优解的情况以及经过控制的扰动情况。我们还讨论了当前实现的局限性以及可能的扩展方向。

章节节选：用二次无约束二元优化模型表述旅行商问题

让我们用最小化哈密顿量能量的方式来表述旅行商问题[13]。引入二进制变量aik，用来确定路径中每个城市的位置：如果城市k在第i步被访问，则aik=1，否则为0。用于最小化总路径长度的目标函数形式为HA=∑k=1N∑l=1N∑i=1N?1Wklaika(i+1)l，其中Wkl为城市k和l之间的距离。我们假设Wkl=Wlk，且对于所有k，有Wkk=0。为确保路径的有效性，需满足……

通过张量网络表示旅行商问题的配分函数

用能量算子来表述旅行商问题，使得可以计算配分函数、自由能和熵等物理量。这些量能够提供有关解空间的信息，而不仅仅是寻找最短路径的信息。这里的张量网络是一种高效计算该问题配分函数的方法。已有多项研究使用张量网络来计算配分函数[24]、[25]、[26]、[27]。

通过张量网络获得物理可观测量

在上一节中，开放型旅行商问题的配分函数被表示为张量网络(15)。现在我们利用这种表示来提取描述路径集合的量，而不仅仅是单一的最短路径。本节的结构如下：首先介绍包括自由能、熵、边的重要性度量以及接近最优路径的统计信息在内的系综可观测量。其次，展示如何通过边的重要性度量来进行局部稳定性分析……

数值验证

本节介绍了所提出的张量网络构建方法的数值验证情况。我们首先以Burma14基准测试作为主要的开放型旅行商问题示例，用它来说明从配分函数中获得的温度力学可观测量、边重要性矩阵以及接近最优路径的结构。然后，我们分析了控制近似收缩过程中精度与内存使用之间平衡的SVD绑定维度D的影响；相应的收敛性测试也在……上进行。

讨论

上述结果表明，张量网络表述不仅有助于找到最优的开放路径，还有助于分析路径集合的有限温度结构。同时，该方法也存在明显的计算瓶颈：随着城市数量的增加，访问集的表示规模会呈指数级增长。因此，以下的讨论将集中在两个实际方向上。首先是通过对图进行简化来扩大可处理的实例规模……

结论

在本研究中，我们为开放型旅行商问题的有限温度路径集合开发了一种张量网络表示方法。这种构建方式从两个互补的角度重新表述了旅行商问题。它既仍然是一个关于单个路径的优化问题，同时也被视为一个统计系综。相应的配分函数使得我们可以获取温度力学和结构方面的可观测量。尤其重要的是，同样的收缩框架还可以用来计算自由能……

CRediT作者贡献声明

O. Fazliakhmetova：写作——审稿与编辑，写作——初稿撰写，可视化，验证，方法论，概念构建。A. Leonidov：监督指导。

利益冲突声明

作者声明，他们在本文的发表过程中不存在任何利益冲突。

O. Fazliakhmetova | A. Leonidov
俄罗斯莫斯科列别杰夫物理研究所