用张量网络生成器优化旅行商问题，生成的路径天然合法且性能优于传统方法。
Tensor Network Generator-Enhanced Optimization for Traveling Salesman Problem
- 用张量网络生成器直接构造合法路径，避免约束惩罚项。
- 在52个城市实例上超越交换法和2-opt等经典启发式算法。
- 基于局部片段建模的k-位变体更高效，适合大规模问题。
我们提出将张量网络生成器增强优化（TN-GEO）框架应用于旅行商问题（TSP），这一基础组合优化挑战。方法采用基于自动微分矩阵乘积态（MPS）的张量网络玻恩机作为生成模型，利用玻恩规则定义候选解的概率分布。与需$N^2$变量及惩罚项的二进制编码方法不同，本工作采用基于排列的整数变量形式，并通过带掩码的自回归采样确保生成样本均为合法路径。还引入了$k$-位MPS变体，使用滑动窗口学习$k$-元组（连续城市子序列）分布，实现大实例下的参数高效建模。在最多含52个城市的TSPLIB基准测试中，实验表明TN-GEO优于经典的交换法和2-opt爬山法。聚焦局部相关性的$k$-位变体相较全尺寸MPS表现更优。
原文摘要 · Abstract (English)
We present an application of the tensor network generator-enhanced optimization (TN-GEO) framework to address the traveling salesman problem (TSP), a fundamental combinatorial optimization challenge. Our approach employs a tensor network Born machine based on automatically differentiable matrix product states (MPS) as the generative model, using the Born rule to define probability distributions over candidate solutions. Unlike approaches based on binary encoding, which require $N^2$ variables and penalty terms to enforce valid tour constraints, we adopt a permutation-based formulation with integer variables and use autoregressive sampling with masking to guarantee that every generated sample is a valid tour by construction. We also introduce a $k$-site MPS variant that learns distributions over $k$-grams (consecutive city subsequences) using a sliding window approach, enabling parameter-efficient modeling for larger instances. Experimental validation on TSPLIB benchmark instances with up to 52 cities demonstrates that TN-GEO can outperform classical heuristics including swap and 2-opt hill-climbing. The $k$-site variants, which put more focus on local correlations, show better results compared to the full-MPS case.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。