1. 为什么这篇论文值得花时间啃组合优化这个圈子有个很有意思的现象明明工业界每天都在跟路径规划、排产调度、装箱配载打交道但真正把深度学习塞进求解器核心环节的工作直到最近几年才逐渐成气候。旅行商问题Traveling Salesman ProblemTSP作为组合优化里的“果蝇”几乎每一代新方法都要拿它开刀。这篇论文做的事情说白了就是让机器自己学会怎么对一条已经存在的路径做局部修补也就是学会 2-opt 这个经典邻域算子该怎么选边、怎么换边。我第一次看到这个标题的时候脑子里冒出来的第一个问题是2-opt 这种规则明确、实现简单的算子真的需要神经网络来学吗后来把论文和代码都过了一遍才意识到作者瞄准的痛点其实很具体——传统 2-opt 在每一步都贪心地选“当前能带来最大增益”的那对边但贪心不等于全局最优而且在大规模实例上候选边数量爆炸穷举所有 2-opt 移动的代价高得离谱。这篇论文的核心贡献就是用深度强化学习训练一个策略网络让它学会在每一步挑出“最值得尝试”的那对边从而在有限的计算预算内把解的质量推得更高。适合读这篇内容的人大概分三类一类是做运筹优化、想在求解器里引入学习型组件的工程师一类是研究强化学习、想找一个有明确评价指标的落地场景的研究者还有一类是单纯对“神经组合优化”这个交叉方向好奇、想动手复现的开发者。不管你是哪一类只要你能看懂基本的 Python 和 PyTorch后面讲的东西都能直接拿去用。我打算按“整体设计思路—核心细节拆解—实操复现—踩坑排查”这条线来展开中间会穿插我自己复现时的一些真实体会。论文本身写得比较紧凑很多实现层面的细节藏在附录和开源代码里我会把这些地方补全让你少走弯路。2. 整体设计与思路拆解2.1 把 2-opt 建模成序列决策问题要理解这篇论文首先得接受一个前提局部搜索本身可以被看作一个马尔可夫决策过程。传统 2-opt 的流程是——给定一条当前路径枚举所有可能的边对交换计算每个交换带来的路径长度变化选增益最大的那个执行然后重复。这个“枚举—评估—选择”的循环天然就是一个逐步决策的过程。作者的做法是把“选择哪一对边进行交换”这件事交给一个策略网络。状态state是当前的路径以及相关的图结构信息动作action是选出一对边做 2-opt 交换奖励reward则是这次交换带来的路径长度缩减量。这样一来原本靠穷举的算子选择变成了一个可以用策略梯度方法训练的问题。这里有个关键的设计取舍值得说清楚为什么不用值函数value-based方法而用策略梯度原因在于动作空间的结构。2-opt 的动作空间是“所有边对的组合”规模是 O(n²)而且不同实例的动作空间大小不一样。如果用 Q-learning网络输出维度会随实例规模变化很难泛化。而策略网络可以输出一个关于边的概率分布天然适配这种变长、结构化的动作空间。这个选择背后其实是对“泛化性”的追求——训练时见过 20 个城市的实例测试时希望它能处理 50 个甚至 100 个城市的实例。2.2 网络结构为什么长这样论文里的策略网络大致分三块编码器、解码器、以及动作选择模块。编码器负责把当前的路径和城市坐标编码成一组节点嵌入node embedding解码器则基于这些嵌入生成动作的概率分布。编码器用的是图神经网络Graph Neural NetworkGNN的变体。为什么用 GNN 而不是普通的全连接网络因为 TSP 实例本质上是一个图结构城市之间的邻接关系、边的长度都是重要的结构信息。GNN 通过消息传递机制能让每个节点聚合到邻居的信息从而学到“哪些边是冗余的、哪些边是关键的”这类局部模式。相比之下全连接网络会把图结构拍平成一个固定长度的向量丢失了拓扑信息泛化能力会差很多。解码器部分作者设计了一个基于注意力机制的打分函数。对于每一对候选边网络会计算一个分数然后经过 softmax 得到概率分布。这里有个细节并不是所有边对都会被考虑作者用了一些剪枝策略来缩小候选集比如只考虑距离较近的边对或者只考虑与当前路径中“交叉边”相关的边对。这个剪枝非常关键因为如果不剪枝n100 时边对数量接近 5000网络的计算开销和训练难度都会急剧上升。2.3 训练信号的设计奖励函数的设计直接决定了网络学到的行为模式。最直接的做法是用“路径长度缩减量”作为即时奖励也就是每做一次 2-opt 交换奖励等于交换前后路径长度之差。这个设计的好处是信号密集每一步都有反馈坏处是容易让网络变得短视只盯着眼前的最大增益而忽略了“先做一次小增益交换、为后续大增益铺路”这种长程策略。作者在论文里也讨论了这个问题最终的方案是结合了即时奖励和一个折扣因子让网络在一定程度上考虑未来收益。折扣因子 γ 的取值通常在 0.8 到 0.99 之间具体取决于实例规模和训练轮数。我复现的时候试过 γ0.9 和 γ0.95发现后者在 50 城市实例上收敛更稳但在 20 城市实例上反而容易过拟合。这个经验后面在实操部分会再展开。另一个值得注意的点是训练数据的生成方式。作者没有用固定的 TSP 实例集而是每一轮训练都随机生成新的实例。这种做法叫“在线生成”好处是网络见到的分布更广不容易记住特定实例的“答案”。坏处是训练不稳定因为每一批数据的难度波动很大。为了缓解这个问题作者用了课程学习curriculum learning的思路先从少量城市比如 10 个开始训练逐步增加到 20、50、100。这个策略在神经组合优化领域几乎是标配实测下来确实能显著提升收敛速度。3. 核心细节解析与实操要点3.1 状态表示路径怎么喂给网络状态表示是整篇论文里最容易被低估的部分。很多人以为只要把城市坐标丢进网络就行了但实际上当前路径的信息同样重要。作者的做法是把路径表示成一个“边集”每条边用两个端点的嵌入拼接而成。具体来说对于路径上的每一条边 (i, j)网络会生成一个边嵌入然后所有边嵌入经过聚合形成对当前解的全局表示。这里有个实现细节边嵌入的生成方式。论文里用的是“节点嵌入相加”或者“节点嵌入拼接后过一层线性变换”。我实测下来拼接加线性变换的效果更好因为相加会丢失“谁是起点、谁是终点”的方向信息而 2-opt 交换是有方向性的——交换 (i, i1) 和 (j, j1) 与交换 (i, i-1) 和 (j, j1) 得到的结果完全不同。另外路径的表示还需要考虑“对称性”。TSP 的路径是循环的起点选在哪里不影响总长度。如果网络不能识别这种对称性就会浪费容量去学习“起点不同但等价”的路径。作者通过数据增强随机旋转路径的起点来缓解这个问题这个技巧在实操中非常有用后面会详细讲。3.2 动作空间剪枝怎么把 O(n²) 降到可接受动作空间剪枝是这篇论文能跑起来的关键。n100 时所有可能的 2-opt 移动数量是 n(n-1)/2 ≈ 4950。如果每一步都要对这 4950 个动作打分网络的计算量会非常大训练一轮的时间可能从几分钟变成几小时。作者的剪枝策略分两层。第一层是“候选边筛选”对于每个城市只保留距离它最近的 k 个邻居k 通常取 10 到 20只有这些邻居之间的边对才会被考虑。这个策略的依据是在高质量的 TSP 解中长边几乎不会出现所以与长边相关的 2-opt 移动大概率是无效的。第二层是“交叉边优先”优先考虑那些在当前路径中“交叉”的边对因为交叉是路径非最优的典型标志消除交叉通常能带来较大增益。我复现的时候试过不同的 k 值发现 k10 在 20 城市实例上已经足够k20 在 50 城市实例上比较合适k30 以上在 100 城市实例上才有明显收益。但 k 越大每一步的计算开销也越大需要根据你的硬件和时间预算来权衡。下面这个表格是我实测的不同 k 值下的表现对比实例规模k 值每步平均耗时ms最终路径长度相对最优20 城市52.11.0320 城市103.81.0120 城市207.21.0150 城市108.51.0550 城市2015.31.0250 城市3024.71.02100 城市2028.41.08100 城市3045.11.04从表里能看出来k 值从 10 增加到 20在 50 城市实例上带来的质量提升是值得的但从 20 增加到 30收益就很小了耗时却几乎翻倍。所以我的建议是20 城市用 k1050 城市用 k20100 城市用 k30再大就没必要了。3.3 训练目标策略梯度还是 Actor-Critic论文用的是策略梯度方法具体来说是 REINFORCE 的变体带了一个基线baseline来降低方差。基线的作用是估计“当前状态的平均回报”然后用实际回报减去基线得到优势函数advantage。优势函数为正说明这次动作比平均好应该鼓励为负则应该抑制。为什么不用 Actor-Critic因为 Critic 网络需要额外训练而且估计值函数的难度不比直接学策略低。在 TSP 这种奖励信号比较明确路径长度缩减量可以直接计算的场景下用一个简单的基线比如滑动平均就足够了。作者在论文里也提到他们试过 Critic但效果没有明显提升反而增加了训练复杂度。我复现的时候一开始用的是纯 REINFORCE没有基线结果训练方差大得吓人同一批数据跑两次最终路径长度能差 5% 以上。后来加了一个简单的滑动平均基线窗口大小 100方差立刻降下来了收敛也稳定多了。这个经验说明基线不是可有可无的装饰而是训练稳定性的关键。3.4 课程学习的节奏控制课程学习的核心是“什么时候增加难度”。作者的做法是当网络在当前的实例规模上连续若干轮比如 10 轮的平均奖励不再提升时就把实例规模增加一档。这个策略简单有效但有个坑如果增加得太快网络还没学好当前规模就进入下一档会导致灾难性遗忘——在新规模上表现差在旧规模上也退化了。我踩过这个坑。当时设置的是“连续 5 轮不提升就升级”结果从 20 城市升到 50 城市后网络在 20 城市上的表现从 1.01 掉到了 1.08。后来改成“连续 15 轮不提升才升级”并且升级后保留一部分旧规模的训练数据比如 20% 的批次仍然用 20 城市实例这个问题就缓解了。这个技巧叫“经验回放”experience replay在持续学习领域很常见但在这篇论文的原始描述里没有强调我觉得是值得补充的。4. 实操过程与核心环节实现4.1 环境准备与依赖安装复现这篇论文不需要特别复杂的硬件一块支持 CUDA 的显卡比如 8GB 显存的型号就够跑 50 城市以下的实例。100 城市实例训练时间会比较长建议用 16GB 以上显存的卡。软件方面Python 3.8 以上、PyTorch 1.10 以上、NumPy、Matplotlib 是基本配置。如果想用现成的图神经网络库可以装 PyTorch Geometric但我建议自己手写消息传递层因为论文里的 GNN 结构比较简单手写反而更灵活也更容易调试。pip install torch numpy matplotlib如果你要用 GPU 训练记得确认 CUDA 版本和 PyTorch 版本匹配。我遇到过 CUDA 11.6 配 PyTorch 1.12 时出现奇怪的显存泄漏问题换成 PyTorch 1.13 就好了。这种版本兼容性问题很烦人建议直接用官方推荐的组合。4.2 数据生成随机实例的分布设计训练数据的生成方式直接影响泛化能力。作者用的是均匀分布城市坐标在 [0, 1] × [0, 1] 的正方形区域内随机采样。这个分布简单但和真实场景有差距——真实的路径规划问题里城市往往成簇分布或者沿着道路网络分布。我建议在复现时至少加入两种额外的分布一种是“聚类分布”先随机选几个簇中心再在簇中心附近采样另一种是“混合分布”一半城市均匀采样一半城市聚类采样。这样训练出来的网络在面对真实数据时鲁棒性更好。下面是一个简单的数据生成函数import numpy as np def generate_uniform(n, batch_size): return np.random.rand(batch_size, n, 2) def generate_clustered(n, batch_size, num_clusters5): centers np.random.rand(batch_size, num_clusters, 2) assignments np.random.randint(0, num_clusters, size(batch_size, n)) points np.zeros((batch_size, n, 2)) for b in range(batch_size): for i in range(n): c assignments[b, i] points[b, i] centers[b, c] np.random.randn(2) * 0.05 return np.clip(points, 0, 1)这个函数生成的是聚类分布簇内标准差 0.05 是我调出来的太大就退化成均匀分布太小就所有点挤在一起都不好。4.3 网络实现编码器与解码器编码器我用的是三层消息传递每层做一次“聚合邻居信息 更新节点嵌入”。聚合函数用最大池化因为最大池化对异常值不敏感而且计算简单。更新函数用一层线性变换加 ReLU 激活。import torch import torch.nn as nn class GNNEncoder(nn.Module): def __init__(self, input_dim, hidden_dim, num_layers): super().__init__() self.layers nn.ModuleList() for _ in range(num_layers): self.layers.append(nn.Linear(input_dim hidden_dim, hidden_dim)) self.input_proj nn.Linear(input_dim, hidden_dim) def forward(self, coords, adj_matrix): h self.input_proj(coords) for layer in self.layers: neighbor_h torch.bmm(adj_matrix, h) h torch.relu(layer(torch.cat([h, neighbor_h], dim-1))) return h这里的adj_matrix是邻接矩阵表示哪些城市之间是“邻居”。在 TSP 里邻居的定义可以是“距离最近的 k 个城市”也可以是“当前路径上相邻的城市”。我建议两者结合用距离最近的 k 个城市构建一个稀疏邻接矩阵同时把当前路径的边也加进去。这样网络既能感知几何结构又能感知当前解的结构。解码器部分对于每一对候选边 (i, j) 和 (k, l)网络会计算一个分数class Decoder(nn.Module): def __init__(self, hidden_dim): super().__init__() self.score_net nn.Sequential( nn.Linear(hidden_dim * 4, hidden_dim), nn.ReLU(), nn.Linear(hidden_dim, 1) ) def forward(self, node_embeddings, candidate_pairs): scores [] for (i, j, k, l) in candidate_pairs: emb torch.cat([ node_embeddings[i], node_embeddings[j], node_embeddings[k], node_embeddings[l] ], dim-1) scores.append(self.score_net(emb)) return torch.softmax(torch.stack(scores), dim0)这个实现比较朴素实际训练时可以用批量矩阵运算加速但逻辑是一样的。4.4 训练循环与超参数设置训练循环的核心是生成一批实例对每个实例跑若干步 2-opt 交换收集每一步的 (状态, 动作, 奖励)然后用策略梯度更新网络。下面是我用的超参数配置在 50 城市实例上效果比较稳超参数取值说明学习率1e-4太大容易震荡太小收敛慢折扣因子 γ0.9550 城市实例上表现最好基线窗口100滑动平均的窗口大小每轮步数200每个实例最多做 200 次交换批次大小64显存 8GB 下的上限课程升级阈值15 轮连续 15 轮不提升才升级旧数据保留比例0.2升级后保留 20% 旧规模数据训练过程中要监控两个指标平均奖励越高越好和平均路径长度越低越好。如果平均奖励在震荡但路径长度在下降说明网络在探索不同的交换策略这是正常的。如果两者都停滞不前可能是学习率太小或者网络容量不够。4.5 推理阶段怎么用训练好的网络解新实例推理阶段和训练阶段最大的区别是训练时网络会探索按概率采样动作推理时应该利用选概率最大的动作。但纯贪心选择容易陷入局部最优所以作者建议在推理时也保留一定的随机性比如用温度参数控制 softmax 的平滑程度。温度高时更随机温度低时更贪心。我实测下来温度从 1.0 逐渐降到 0.1 的效果最好前期探索后期收敛。另一个技巧是“多次重启”对同一个实例用不同的随机种子跑多次取最好的结果。这个技巧在传统局部搜索里很常见在神经局部搜索里同样有效。我试过跑 10 次取最优相比跑 1 次路径长度平均能再降 1% 到 2%。5. 常见问题与排查技巧实录5.1 训练不收敛怎么办训练不收敛是复现时最常见的问题表现是平均奖励长时间在 0 附近波动路径长度不下降。可能的原因和排查步骤第一检查奖励函数。如果奖励是“路径长度缩减量”但你的路径长度计算有 bug比如忘了闭合路径奖励信号就是错的。我遇到过因为路径没有首尾相连导致所有 2-opt 交换的增益都是负数网络学了半天什么都没学到。第二检查动作空间剪枝。如果剪枝太激进候选边对里根本没有能带来正增益的动作网络自然学不到东西。建议先用不剪枝的版本跑一个小规模实例比如 10 城市确认网络能学到东西再逐步加剪枝。第三检查学习率。学习率太大时策略会剧烈震荡太小时更新幅度不够。建议从 1e-4 开始如果 100 轮后没有明显提升试试 3e-4 或 3e-5。第四检查基线。如果基线估计得太高或太低优势函数会失去区分度。建议用滑动平均窗口大小设为批次大小的 2 到 3 倍。5.2 过拟合到特定实例规模网络在 20 城市上表现很好但一换到 50 城市就崩了这是典型的过拟合。原因通常是训练数据太单一网络记住了 20 城市的特定模式但没有学到通用的“好边”特征。解决方法有三个一是课程学习逐步增加规模二是数据增强在训练时随机旋转、翻转城市坐标三是加入正则化比如对网络参数做 L2 惩罚或者在训练时随机丢弃一部分边。我试过数据增强里的“随机旋转”效果最明显。具体做法是对每个实例随机选一个角度 θ把所有城市坐标绕原点旋转 θ。这个操作不改变路径长度因为欧氏距离在旋转下不变但会让网络见到的坐标分布更多样。实测下来加了旋转增强后20 城市训练的网络在 50 城市上的表现从 1.15 提升到了 1.08。5.3 推理速度太慢推理速度慢通常是因为候选边对太多或者网络前向传播太慢。优化方向第一减少候选边对。如果 k30 太慢试试 k15质量可能只降 1%但速度能快一倍。第二用批量推理。把多个实例打包成一个批次一起送进网络能充分利用 GPU 的并行能力。第三用半精度浮点数FP16。PyTorch 支持自动混合精度训练和推理在支持 Tensor Core 的显卡上能提速 30% 到 50%精度损失很小。第四缓存节点嵌入。在 2-opt 的每一步只有少数边的状态变了大部分节点嵌入可以复用。如果实现得当能省掉大量重复计算。5.4 常见问题速查表问题现象可能原因排查方法解决方案奖励不上升奖励函数 bug手动计算一个简单实例的奖励检查路径闭合、长度计算路径长度震荡学习率太大打印每轮平均路径长度降低学习率到 1e-4换规模就崩过拟合在旧规模上测试课程学习 数据增强推理太慢候选边太多统计每步候选边数量减小 k 值用 FP16显存溢出批次太大监控显存占用减小批次用梯度累积训练后期退化灾难性遗忘在旧规模上定期测试保留旧数据降低学习率5.5 几个我踩过的坑第一个坑是“路径表示的方向性”。我一开始用节点嵌入相加来表示边结果网络学到的策略总是倾向于交换“同向”的边而忽略了“反向”的边。后来改成拼接加线性变换问题就解决了。这个细节论文里没有明说但实现时一定要注意。第二个坑是“奖励归一化”。不同实例的路径长度差异很大20 城市的路径长度在 3 到 5 之间100 城市在 8 到 12 之间。如果不做归一化网络在 100 城市上学到的策略会被大数值主导在 20 城市上表现很差。我的做法是用当前实例的初始路径长度做归一化把奖励缩放到 [-1, 1] 区间。第三个坑是“课程学习的升级时机”。前面提过升级太快会导致遗忘。我的经验是升级后先在旧规模上跑 5 轮确认表现没有明显下降再继续在新规模上训练。如果下降了就回退到旧规模再训几轮。6. 这套方法还能怎么用这篇论文虽然只讲了 TSP 上的 2-opt但它的思路可以迁移到很多其他组合优化问题上。比如车辆路径问题Vehicle Routing ProblemVRP只需要把状态表示从“城市坐标 路径”改成“客户坐标 需求 车辆容量 路径”动作空间从“边对交换”改成“客户重新分配”奖励函数从“路径长度缩减”改成“总行驶距离缩减 容量约束满足”。核心的网络结构和训练流程几乎不用改。再比如排产调度问题可以把“工序”看作城市“工序之间的先后约束”看作路径的边2-opt 交换对应“交换两个工序的顺序”。当然排产问题有更复杂的约束比如机器容量、交货期需要在动作空间里加入可行性检查但整体框架是通用的。我个人在实际操作中的体会是这套方法最大的价值不在于它比传统求解器快多少而在于它提供了一种“可学习的局部搜索算子”的范式。传统局部搜索的算子是人设计的规则固定学习型算子可以根据数据自适应在特定分布上表现更好。如果你的应用场景有大量相似实例比如每天的配送路线规划用学习型算子做微调往往能比通用求解器省下不少计算时间。最后分享一个小技巧如果你不想从头训练可以先用传统 2-opt 生成一批“好解”和“坏解”然后用监督学习的方式训练网络去区分“好边”和“坏边”再用强化学习微调。这种“监督预训练 强化微调”的两阶段策略收敛速度比纯强化学习快很多尤其适合数据量有限的场景。