★ FEATURED ARTICLE 简介面向强化学习与组合优化方向的开发者这份资源提供了一套基于指针网络求解旅行商问题TSP的Python工程实现。代码采用强化学习训练框架覆盖模型定义、数据加载、训练器和主流程等完整环节适合用于入门RL在离散组合问题中的应用或作为复现和改造的起点。压缩包共14个文件大小约4.01MB包括8个Python脚本、2张结果图、2个npz测试数据集、1份README说明及gitignore配置结构与功能划分清晰。目前已有867人学习下载。实现为简化起见未单独设计critic网络而是用最佳路径长度作为critic值训练样本在[0,1]x[0,1]网格上均匀采样由Concorde求最优解依赖环境配置可在README中查阅。读者通过main.py、model.py、trainer.py等文件即可复现训练与评测查看TSP10、TSP50的测试结果图并能在此基础上扩展注意力机制或策略梯度改进。1. 先想清楚指针网络到底在解 TSP 的哪一环训练好的指针网络在 100 个城市的 TSP 实例上哪怕只用贪心解码解的质量也能逼近最优解的 95%~98%而这个模型从零训练到收敛通常只需要一两个小时的 CPU 时间。这就是这个标题背后真正值得做的事把组合优化问题包装成一个序列生成问题交给深度强化学习去解。指针网络不是传统意义上的“优化求解器”它不靠分支定界也不靠局部搜索而是让网络自己学会“下一个该访问哪个城市”的决策习惯。这篇文章面向的读者很明确你手里有一份想跑的 Python 代码想搞清楚它每一步在干什么、参数为什么这么设、跑出来的结果怎么评估。我会把指针网络的结构、REINFORCE 的训练流程、数据怎么生成、模型怎么定义、训练怎么收敛、结果怎么验证从头到尾拆开讲。适合谁适合刚接触深度强化学习、想拿一个经典问题练手的研究生或工程师也适合需要快速复现一个 baseline 的算法工程师。读完你能跑通也能改。2. 指针网络为什么能解 TSP从 seq2seq 到“指向输入序列”2.1 传统 seq2seq 的一个尴尬输出字典是固定的早期用神经网络做 TSP 的尝试大多把 TSP 当翻译任务输入一串城市坐标输出一串城市编号。但 seq2seq 的 decoder 每一步是从一个固定词表里挑一个 token比如“城市 0”“城市 1”……到“城市 99”这要求训练前就把城市数量定死。换一个城市规模就要重新训练并且输出层的大小也跟着变非常不灵活。而且 TSP 的输出本质上不是一个“词”而是输入序列里元素的一个排列。你给模型看 50 个城市它输出的第 5 步“该去哪个城市”必须在它之前见过的 50 个城市里选不能凭空冒出一个新城市。这天然是“指向”语义不是“生成”语义。这里就有个常见误区很多人以为指针网络和 attention seq2seq 差不多其实差在最后那层。seq2seq 的 attention 是给 decoder 当前状态计算一个上下文向量然后把这个向量喂给 softmax 分类器去生成词而指针网络把 attention 的权重直接当成了输出概率分布权重最大的那个位置就是模型“指向”的输入元素。也就是说attention 的用途从“提取信息”变成了“输出决策”这是本质区别。2.2 注意力打分函数怎么设计加性注意力与点积注意力的选择指针网络的经典实现里decoder 在每一步 t 先算出一个查询向量 q_t然后和 encoder 每个位置的隐状态 h_i 做注意力打分。早期论文用的是加性注意力additive attention打分函数是score(q_t, h_i) v^T tanh(W_1 h_i W_2 q_t)代码里写出来也直观def attention_score(query, ref, W1, W2, v): # query: [batch, hidden], ref: [batch, seq_len, hidden] # 加性注意力把 query 广播到每个位置再过一个 tanh 全连接 expanded_query query.unsqueeze(1).expand_as(ref) energy torch.tanh(W1(ref) W2(expanded_query)) score v(energy).squeeze(-1) # [batch, seq_len] return score这段代码的思想是把 decoder 当前的“意图”和 encoder 每个城市位置的“记忆”融合一下让打分向量 v 判定哪个城市和当前意图最匹配。注意expand_as这里要用不然 batch 维对不上。如果你改用点积注意力 score q_t^T h_i / sqrt(d)效果其实也接近但对维度敏感加性注意力对 hidden size 更鲁棒这也是原论文选它的原因。最终对 score 做 softmax 得到概率分布然后按概率采样或者取 argmax 得到当前要访问的城市。在训练的时候这个分布还会被用来算 log 概率喂给 REINFORCE 的损失函数。2.3 训练范式为什么必须选强化学习监督学习的两个死穴先看监督学习路线能不能走。理论上你可以拿精确求解器比如 Concorde跑出一批最优解把城市序列当标签去训练模型。这看起来很美好实际操作有两个死穴。第一TSP 的最优解不唯一对称解特别多。一个 5 个城市的实例最优环可能从任意城市开始、正着走反着走都行。你给模型一个标签序列 0→3→1→4→2它绕一圈变成 2→1→3→0→4 也是最优解但你没法在 loss 里表达这种等价性。模型会学着背着大量互相矛盾的标签收敛非常慢。第二你想让模型泛化到更大规模的实例比如训练 20 个城市、测试 100 个监督学习很难处理这种分布外泛化。而强化学习的思路完全绕开了这两个问题不需要标签只定义奖励路径总长度的负数让模型自己探索怎么排列城市能得到更短的路径。网络在探索中自己发现“相邻城市优先”“不交叉”这类启发式规则不需要你告诉它。所以在标题这套方案里训练范式选的是 policy gradient具体来说是 REINFORCE。这个算法在组合优化场景里是最省事的你只需要一个可采样的策略网络和一个能算奖励的仿真环境不需要 Q 值函数不需要经验回放也不容易发散。3. 搭出可训练的最小系统数据生成、Encoder 和 Decoder 的 PyTorch 实现3.1 训练数据是现成的随机 TSP 实例生成器TSP 强化学习训练最大的好处是数据不用买不用标随时生成而且理论上无限。常见做法是在单位正方形里均匀随机采样城市坐标。这个分布和很多公开 benchmark 一致方便你后面和别人的结果对比。import torch def generate_tsp_data(batch_size, num_cities): # 返回形状 [batch_size, num_cities, 2]值域 [0, 1] # 在单位正方形内均匀采样不需要额外归一化 data torch.rand(batch_size, num_cities, 2) return data # 用固定种子生成一批 50 城市的实例方便排查问题 torch.manual_seed(42) train_data generate_tsp_data(128, 50) print(train_data.shape) # torch.Size([128, 50, 2])这段生成器本身没有技术难点但有个容易被忽略的细节坐标要不要归一化我建议在数据生成时就直接落在 [0, 1] 区间不要再额外做标准化。原因有两点一是 TSP 的奖励是路径总长度坐标尺度直接影响奖励量级进而影响 REINFORCE 的梯度方差二是后续做可视化和评估时直接画在单位正方形里最直观。如果你处理的是真实地理坐标数据那就必须先缩放到 [0, 1]不然奖励量级会变得非常大训练很难稳。3.2 Encoder 读取城市集合LSTM 还是线性映射指针网络原文里 encoder 用的是双向 LSTM把每个城市的坐标依次读入输出一组隐状态。但在实际复现中很多人发现一个问题城市坐标没有天然的顺序LSTM 从左到右读它们本质上是在给城市强加一个输入顺序这个顺序是模型自己“脑补”的并不会带来任何几何信息。于是后来的实现里很多做法是把 encoder 简化为一个线性映射加一层 MLP。对每个城市坐标 [x, y] 做一次线性变换得到 embedding然后用一个可学习的位置编码或者根本不用位置编码直接拿这组 embedding 去做 attention。class TSPEncoder(nn.Module): def __init__(self, input_dim2, embedding_dim128): super().__init__() # 用全连接把 2 维坐标映射到 embedding 空间 self.init_w nn.Linear(input_dim, embedding_dim) self.embedding_dim embedding_dim def forward(self, city_coords): # city_coords: [batch, seq_len, 2] # 线性映射 ReLU得到每个城市的嵌入表示 embedded torch.relu(self.init_w(city_coords)) return embedded # [batch, seq_len, embedding_dim]不要小看这个简化它把 encoder 的参数量降了一个数量级训练速度变快而且效果并不比 LSTM 差。背后的道理很简单——你不需要一个顺序模型去理解无序集合你需要的是一个“地点特征提取器”。如果你的任务场景里城市之间有明确的进入顺序比如带时间窗的路径问题那 LSTM 仍然有价值但标准 TSP 里线性映射就够用。这个代码里的input_dim2是对标准坐标输入写的如果你给每个城市额外加了特征比如城市的“热度”改成相应维度就行。3.3 Decoder 的指向机制从上下文向量到选择概率decoder 是整个指针网络的灵魂。它每一步维护一个状态计算注意力得分然后用 softmax 把它变成“选择哪个城市”的概率分布。在实现时最大的坑是掩码mask已经访问过的城市必须被屏蔽掉不然模型会原地打转或者重复访问。class PointerDecoder(nn.Module): def __init__(self, embedding_dim128): super().__init__() self.W1 nn.Linear(embedding_dim, embedding_dim, biasFalse) self.W2 nn.Linear(embedding_dim, embedding_dim, biasFalse) self.v nn.Linear(embedding_dim, 1, biasFalse) self.embedding_dim embedding_dim def forward(self, hidden, encoder_outputs, mask): # hidden: [batch, embedding_dim] decoder 当前状态 # encoder_outputs: [batch, seq_len, embedding_dim] 每个城市的嵌入 # mask: [batch, seq_len] 已访问位置为 True expanded_hidden hidden.unsqueeze(1).expand_as(encoder_outputs) energy torch.tanh(self.W1(encoder_outputs) self.W2(expanded_hidden)) score self.v(energy).squeeze(-1) # [batch, seq_len] score score.masked_fill(mask, float(-inf)) # 屏蔽已访问城市 prob torch.softmax(score, dim-1) return prob这段代码有三个点需要说明。第一masked_fill用float(-inf)而不是 0因为 softmax 之后 -inf 会变成 0 概率而直接填 0 会导致 softmax 分母仍包含这个位置概率分配会出错。第二expand_as不会复制数据它只是让hidden在内存里广播成 batch 个副本节省内存开销。第三softmax 之后的prob既用来采样也用来算 log 概率注意 PyTorch 里torch.log(prob)在概率为 0 的位置会产生 -inf如果后面要算损失要额外做 clamp 或者用log_softmax重算一次。我一般会在实际工程里把 softmax 和 log_softmax 分开算torch.distributions.Categorical可以直接从 logits 构建采样分布底层同时维护概率和 log 概率能省掉不少数值稳定性上的处理。4. 训练循环的正确打开方式REINFORCE 与 critic baseline 的实现细节4.1 奖励函数和损失函数怎么定义为什么不能直接算“准确率”先想清楚奖励怎么定。TSP 的目标是路径总长度最短那每一轮完整的路径生成结束后路径总长度的相反数就是奖励即 reward -tour_length。用强化学习的术语说这是一个 episodic 任务一个 episode 就是完整地访问所有城市并回到起点。REINFORCE 的损失函数写成loss -mean( (reward - baseline) * log_prob )注意这里reward - baseline是整个 episode 的奖励减去一个 baseline。为什么要减 baseline因为 REINFORCE 的原始形式里所有 action 的梯度都会被 reward 放大如果 reward 恒为正模型会盲目提高所有动作的概率方差极大。减去 baseline 之后只有比平均表现更好的轨迹才会被强化这就是“advantage”的概念。4.2 baseline 的选择critic 网络 vs 指数滑动平均baseline 有两种常见做法。第一种是用一个独立的 critic 网络输入城市坐标输出一个标量预测当前实例的期望路径长度。第二种是维护一个指数滑动平均EMA的 baseline每轮用当前奖励更新。class CriticNetwork(nn.Module): # 预测一个实例的期望路径长度作为 REINFORCE 的 baseline def __init__(self, input_dim2, embedding_dim128, hidden_dim256): super().__init__() self.encoder TSPEncoder(input_dim, embedding_dim) self.fc1 nn.Linear(embedding_dim, hidden_dim) self.fc2 nn.Linear(hidden_dim, 1) def forward(self, city_coords): # 先对每个城市做 embedding再对所有城市取平均得到一个实例级向量 embedded self.encoder(city_coords) # [batch, seq_len, emb] instance_embed embedded.mean(dim1) # [batch, emb] value torch.relu(self.fc1(instance_embed)) value self.fc2(value).squeeze(-1) # [batch] return value这个 critic 网络的训练目标是最小化 MSE预测值和实际奖励之间的差距。在训练循环里critic 和 policy 是交替更新的policy 用 advantage 更新critic 用真实奖励回归更新。理论上 critic 能提供更稳定的 baseline但实践中有个尴尬critic 网络的训练本身也会震荡而且它的容量和 policy 相当训练开销翻倍。我在自己跑实验时更推荐指数滑动平均 baseline——代码少、稳定、效果也够用baseline 0.9 * baseline 0.1 * torch.mean(rewards).item()这个式子里 0.9 是平滑系数含义是 baseline 缓慢地追着近期平均奖励走。系数太小会导致 baseline 追太快、advantage 失去意义系数太大则 baseline 不变相当于没有 baseline。0.85~0.95 之间是安全区间。4.3 完整训练循环采样、推断、损失、反向传播的顺序写完整训练循环时新手最容易翻车的点是采样和推断混在一起。记住一个原则训练时每一步都要采样用概率分布去随机选城市评估时每一步都要取 argmax选概率最大的城市。训练时如果取 argmax模型永远探索不了新路径评估时如果采样结果会有随机性指标不稳定。def train_one_epoch(model, critic, optimizer, scheduler, batch_size128, num_cities50, max_grad_norm1.0): # 1. 随机生成一批 TSP 实例 city_coords torch.rand(batch_size, num_cities, 2) # 2. 用当前 policy 在环境中采样完整路径 tours, log_probs model.sample_tour(city_coords) # tours: [batch, num_cities] 每一步访问的城市索引 # log_probs: [batch, num_cities] 每一步的选择对数概率 # 3. 计算路径总长度作为奖励 rewards compute_tour_length(city_coords, tours) # [batch] # 4. critic 预测 baseline并计算 advantage baseline_value critic(city_coords).detach() # 停止梯度防止 critic 的 loss 回传到 policy advantage rewards - baseline_value # [batch] # 5. REINFORCE 损失优势越大对应路径的 log 概率越大 loss -(advantage * log_probs.sum(dim1)).mean() # 6. 同时更新 critic让它更接近真实奖励 critic_loss torch.nn.MSELoss()(critic(city_coords), rewards) optimizer.zero_grad() loss.backward() critic_loss.backward() torch.nn.utils.clip_grad_norm_(model.parameters(), max_grad_norm) optimizer.step() scheduler.step() return loss.item(), rewards.mean().item()这里有个细节很关键baseline_value要.detach()。如果不 detachcritic 的梯度会穿过 advantage 反传到 policy 网络两个网络互相拉扯训练直接乱掉。还有一个注意点是scheduler.step()的位置。如果你用的是 StepLR 或 CosineAnnealingLR应该在每一轮或者每 N 轮更新一次而不是在每次反向传播后更新。更新太频繁会导致学习率骤降模型后期根本没法学。梯度裁剪clip_grad_norm_在这个任务里几乎是必须的。为什么因为 REINFORCE 的梯度 奖励 × log 概率的梯度如果某个 batch 里一条路径特别短奖励特别大梯度范数会爆炸训练一步就毁掉整个模型。梯度范数上限 1.0 是个常用默认值不稳定时可以降到 0.5。训练到什么时候算收敛一个实用判据是在固定 1000 个测试实例上贪心解码的路径长度不再下降且波动小于 0.1%。20 个城市的实例通常几百轮就能收敛到接近最优50 个城市需要几千轮。5. 复现避坑指南5 个让模型训不出来的常见原因5.1 损失一直在涨但奖励也在涨——这是正常的吗现象训练日志里 REINFORCE 的 loss 数值一直上升完全不像分类任务里的 loss 一样单调下降。原因REINFORCE 的 loss 本身没有下界它等于 advantage 和 log_prob 的乘积之和。当模型越学越好log_prob 会越来越大负数变小但 advantage 也在变化两者相乘的 loss 会上下波动甚至整体上升。这完全正常不要用 loss 的绝对值判断收敛要看奖励的均值曲线。解决把训练日志的监控指标从 loss 改为 reward。如果 reward 在稳步上升且最终平稳loss 怎么动都无所谓。5.2 同一份代码换了 batch size 效果差很多现象batch size 从 64 换到 256其他参数不变最终解的质量掉了 5%。原因batch size 直接影响 REINFORCE 的方差。REINFORCE 用同一个 batch 内的多个实例来平均梯度相当于蒙特卡洛采样。batch 越大梯度越稳定但也会带来一种副作用baseline 的预测会越来越准exploration 的推力变小模型更容易陷在局部最优。解决我一般用 128 作为起点如果你的显存或内存够大建议配合增大学习率一起调整并且观察评估曲线而不仅仅是训练曲线。5.3 模型训练完成后在训练集上表现好但在新实例上泛化崩了现象固定 50 城市的实例训练训练集的 TSP 求解质量很高但换到 100 城市的实例上模型输出的路径几乎是随机的甚至不如最近邻启发式。原因指针网络是基于 attention 的模型它对输入序列长度有一定外推能力但输出长度是 num_cities 决定性的。如果训练时从未见过 100 城市的实例decoder 的 attention 分布在长序列上很难自动适应。解决最直接的办法是“多尺度训练”每轮随机让 num_cities 在 20 到 50 之间变化这样模型见过不同长度的序列。还有一个 trick 是在 decoder 的 mask 处理里对于超出当前实例长度的位置保持 mask 为 True这样模型学会“不选择不存在的城市”。5.4 训练时 loss 出现 NaN现象训练跑了几百轮突然 loss 变成 NaN然后整个模型权重都废了重启训练也一样。原因REINFORCE 的 log 概率在概率接近 0 的位置是 -inf如果某个动作的概率被 mask 或数值下溢搞成 0log_prob 直接爆炸。另外学习率太大也可能导致权重更新过度激活值变成 NaN。解决第一个也是最容易忽略的——在计算 log_prob 时一定要从 logits 重新算 log_softmax而不是从 softmax 之后的概率取 log。第二个是加梯度裁剪前面已经提过。第三个是如果 NaN 出现在 critic 的 loss 上检查 critic 的预测值有没有超出合理范围可以在 critic 的输出后加一个 sigmoid 或 clamp 限制在 [0, 最大路径长度] 区间内。5.5 用了 Mask 但模型还是重复访问城市现象评估时模型的输出序列里有重复的城市比如 50 个城市的实例输出只有 48 个不同城市然后重复了其中一个。原因大概率是 mask 的实现有 bug常见的有三种一是 mask 没有在每一步更新二是 mask 更新时用mask[:, tour[:, t]] True但tour[:, t]的形状和张量索引的语义不符合预期导致没有真正标记三是 softmax 之前score.masked_fill(mask, float(-inf))写成了 fill 0。解决调试时最直接的方法是把一个 batch 的 mask 张量打印出来看每一步之后已访问位置是否都变成了 True。另外在评估脚本里加一个断言assert tours.max() num_cities and tours.min() 0 assert len(set(tours[0].tolist())) num_cities, tour has duplicate cities如果在训练中触发断言立刻调小 batch size 或学习率通常是模型还没学会“不重复”的规则而不是代码问题。6. 验证和进阶玩法贪心解码、Beam Search 和可视化对比先用一个小技巧说明贪心解码的重要性训练时模型输出的是每一步的概率分布而评估时你要用torch.argmax(prob, dim-1)来选城市这样才能得到一个确定性的解。这个解对应于“模型认为的最优路径”。但贪心解码有个天生缺陷——每步取局部最优可能错过全局最优。比如前两步选了次优的相邻城市后面才可能连出一条更短的环。一个改进是 beam search。你可以在每一步保留 top-k 个部分路径而不是只保留 1 个。k10 的 beam search 通常能把解的质量提升 1%~2%但推理时间也涨了 10 倍。我的习惯是先用贪心解码快速验证模型效果确认没问题之后再用 beam search 跑最终指标。验证的第二步是可视化。把模型输出的路径画出来用肉眼判断是否出现交叉边。TSP 的最优解在欧氏距离下一定是无交叉的简单多边形如果你看到交叉说明模型还没收敛或者陷入了局部最优。import matplotlib.pyplot as plt def plot_tour(coords, tour, title): # coords: [num_cities, 2]tour: 城市访问顺序的索引列表 city coords[tour] # 闭合环把第一个城市补到末尾画出一个完整多边形 city city city[:1] plt.figure(figsize(6, 6)) plt.plot(city[:, 0], city[:, 1], o-, linewidth1, markersize4) plt.title(title) plt.show()这段代码里city city[:1]是闭合环的关键没有它你画出来的是一条折线而不是一个环一眼看不出来路径好坏。可视化不能替代定量评估但它能帮你快速定位两种典型问题如果路径有大量交叉说明模型还没收敛如果路径虽然无交叉但明显绕路说明模型陷入了局部最优可能需要增大探索率或者换 baseline 策略。我自己的一个血泪经验是评估时不要在训练日志里直接打印“当前 batch 的奖励均值”而是维护一个固定的验证集每 50 轮跑一次贪心解码记录平均路径长度。原因很简单训练 batch 是随机生成的单 batch 的奖励均值波动非常大看不出趋势。固定验证集的结果才是稳定的曲线。最后还想说一句如果你想把这个方案用到更大规模的问题上150 个城市以上的实例纯指针网络的效果会明显下降这时可以叠加一个 2-opt 局部搜索作为后处理——先用指针网络生成一个初始路径再用 2-opt 优化这在工程上是很常见也很有用的组合。这个方向最大的价值是让你真正理解“把组合优化问题转成生成问题”的思维范式这个范式换到路径规划、调度问题上同样成立。希望帮到你。本文还有配套的精品资源点击获取
阅读完成 · 觉得有帮助？
