简介这份压缩包提供了一套基于指针网络的旅行商问题强化学习 Python 实现适合对深度强化学习与组合优化交叉方向感兴趣的开发者、研究生或竞赛选手。项目没有单独实现评论家网络而是直接用最优路径长度作为评论家值训练样本在单位正方形网格内均匀采样二维点最优解由 Concorde 求解器生成是学习指针网络与强化学习结合范式的良好示例。资源共 14 个文件压缩包约 4.01MB包括 8 个 Python 脚本分别承担模型构建、训练器、数据加载、配置与主流程2 张 PNG 图展示了 TSP10 和 TSP50 的测试结果2 个 npz 文件存放预置测试集另有说明文档介绍用法与目录结构。目前已有 867 人学习。下载后可以拿到完整可运行的代码骨架、测试数据集与结果图能够通过调整参数重现不同规模旅行商问题的求解效果并对比强化学习解与最优解之间的差距帮助理解注意力机制、策略梯度训练以及奖励设置对组合优化问题性能的影响。1. 指针网络给TSP做强化学习为什么这是一份值得照着跑的 Python 代码城市数一超过 20穷举就开始吃力这是 TSP旅行商问题给所有做求解器的人上的第一课。以前我们靠 2-opt 这类局部搜索去修路径现在换个思路让深度强化学习算法直接学“下一个该飞哪个城市”。指针网络处理这类问题很顺它的输出天然是指向输入序列某一位的“指针”正好把 TSP 路线生成变成一步一个指向。这篇文章把指针网络、TSP、强化学习、Python 代码这套组合拆开讲清楚从原理到可复现的训练脚本再列出我复现时反复踩的坑。适合已经写过一点 PyTorch、想用组合优化问题练手深度强化学习的读者。2. 先把原理钉在纸上为什么排序问题不能靠普通 seq2seq 硬解2.1 从定长编码器到指针网络输出必须从输入里“挑”TSP 的输出不是一串“词”而是输入城市集合的一个排列。你要是拿早年 seq2seq 那套做法来套编码器把整张图压成一个定长向量解码器在固定词表上做分类问题立刻出现城市数量一变词表就得重建城市顺序打乱同一个几何问题被编码成完全不同的向量模型从头再学一遍。传统 seq2seq 的输出空间是预先定义好的比如翻译任务里目标语言词表是固定的TSP 却要求模型输出动态长度的排列而且这个排列的元素全部来自输入序列。指针网络Pointer Network的核心改动就在这里它不维护一个独立的目标词表而是把每一步的 softmax 直接施加在输入序列的每一个元素上输出一个“指向”输入里某个位置的指针。对 TSP 来说这个指针的意思就是“下一个要访问的城市”。掩码是这套机制里最容易写错又最关键的部分。已经访问过的城市必须在打分阶段被排除否则解码器会反复指回同一个城市。常见的做法是先把所有已访问位置的 logit 置为负无穷再进入 softmax。这一步放错位置整个训练过程都会在垃圾路线上打转后面第 5 章我会单独讲这个坑。2.2 注意力打分就是指针一个 softmax 完成“指认”指针网络的计算过程可以拆成两段。编码器把每个城市的坐标变成一组高维向量解码器在每一步用一个“当前上下文向量”去跟编码器输出的所有城市向量做点积得到一组分数除以sqrt(d_k)做缩放再经过掩码和 softmax就得到指向每个城市的选择概率。训练时按这个概率采样验证时直接取 argmax。# 指针打分context 是解码器当前状态enc 是编码器输出 logits torch.matmul(context, enc.transpose(1, 2)) / math.sqrt(embed_dim) logits logits.masked_fill(visit_mask, float(-inf)) prob torch.softmax(logits, dim-1)这段代码的表达力在于enc保存了所有城市的信息context只负责说“我现在在这接下来往哪飞”打分结果不需要依赖固定词表完全由输入序列本身决定。visit_mask是一个布尔张量值为 True 的位置表示已经访问过直接填负无穷。这里有一个细节如果掩码不是加在 logits 上而是加在 softmax 之后概率已经完成归一化掩码就不起作用了因为被掩掉的位置的概率已经被重新分配给了其他城市。上下文向量怎么更新最简单也最稳定的做法是把上一步选中城市的编码器输出作为下一步的context。城市坐标本身在编码器里已经包含了全局信息用它做指针依据足够。至于要不要在解码器里再套一层 RNN 或者 GRU我试过的经验是小规模 TSP 上收益有限参数却多了一圈反而不如直接用上一步指向的 embedding 干净。2.3 把 TSP 构造成强化学习状态、动作、奖励这样定义用强化学习解 TSP第一步是把问题描述成一个马尔可夫决策过程。状态是“当前所在城市 尚未访问的城市集合”动作是“从剩余城市里选一个作为下一站”状态转移是确定的选了哪个城市就移动到哪里奖励的设计最有讲究——如果每走一步都给出负的欧氏距离模型容易变得短视只顾眼前的小步忽略全局路径。常见做法是把奖励定义成整条路线结束时的负路径总长度中间步骤不给奖励。这样策略网络只能通过“整条路线的长度”来判断之前一串动作的好坏迫使它学习长距离的依赖关系。目标是最小化期望路径长度等价于最大化期望累积奖励。方法是否需要最优标签可扩展性主要问题精确求解器不需要差规模稍大就爆炸求解时间长监督学习需要最优路径做标签受标签质量限制TSP30 以上标签极难获取强化学习不需要好只用奖励信号方差大训练不稳定REINFORCE 是深度强化学习算法家族里最简单的一档也是跑通这套方案最合适的起点。它不需要引入价值网络或经验回放只要一条轨迹的路程长度就能更新策略。损失函数的形式是把整条路径上每一步的 log 概率加起来乘上一个优势值。优势值的计算方式直接影响训练稳定性第 3 章会给出具体代码。关于“强化学习算法”这个关键词需要记住的是这里不是像围棋那样有一个对手或者环境反馈环境的全部反馈就是最终那段路程朴素但够用。3. 一份最小可跑的 Python 实现模型定义、采样与 REINFORCE 训练循环3.1 代码库长什么样train.py、model.py、data.py 的职责划分下载一份 TSP 强化学习代码包后第一件事不是急着跑train.py而是看懂文件划分。不管代码是从哪个仓库拿来的我一般会找出三个核心模块并确认它们各自的边界model.py负责指针网络结构train.py负责训练循环和 checkpoint 保存data.py负责生成随机城市坐标、组织 batch 和掩码。三个文件各干各的事是后面排查问题的前提。环境配置其实和普通 PyTorch 项目没有区别我通常直接在 vscode 里建一个虚拟环境装好 torch 和 numpy 就能开跑。这个小规模项目没必要引入任何重量级框架gymnasium 也不是必须的因为 TSP 的环境就只是一个坐标生成器和一个路线长度计算函数自己写比套环境接口更直接。文件职责关键函数model.py指针网络定义encode / decode_stepdata.py坐标生成、批量采样generate_instances / compute_distancetrain.py训练循环、验证、存档train_epoch / validate3.2 编码器和解码器注意力掩码在哪一步加顺序别弄反编码器我用 Transformer encoder 而不是 LSTM原因有两个城市之间的依赖关系是双向的LSTM 的顺序扫描反而引入不存在的顺序偏置Transformer 的并行计算让 batch 内多条轨迹一次跑完训练速度快很多。城市坐标是二维的所以第一层是一个线性层把 2 维映射到 128 维再做位置编码是多余的一步——TSP 输入是集合不是序列城市编号没有语义。import math import torch import torch.nn as nn class PointerNet(nn.Module): def __init__(self, embed_dim128, n_heads8, num_encoder_layers3): super().__init__() self.embed nn.Linear(2, embed_dim) encoder_layer nn.TransformerEncoderLayer( d_modelembed_dim, nheadn_heads, batch_firstTrue ) self.encoder nn.TransformerEncoder(encoder_layer, num_layersnum_encoder_layers) self.d_k embed_dim ** 0.5 def encode(self, xy): return self.encoder(self.embed(xy)) def decode_step(self, context, enc, visit_mask): # context: (B, embed_dim) # enc: (B, seq_len, embed_dim) logits torch.matmul(context.unsqueeze(1), enc.transpose(1, 2)) / self.d_k logits logits.squeeze(1).masked_fill(visit_mask, float(-inf)) return torch.log_softmax(logits, dim-1)decode_step返回的是 log 概率而不是原始概率这一点对训练很重要后续计算策略梯度时要用log_prob而验证贪心解码直接用 argmax两者共用同一个函数不会出分歧。batch_firstTrue意味着输入张量的形状是(batch, seq_len, embed_dim)掩码张量形状是(batch, seq_len)。masked_fill把已访问位置变成负无穷log_softmax之后这些位置的值变成 NaN 是正常现象只要采样时不取到它们就没问题。3.3 REINFORCE 训练循环baseline 和 advantage 的符号决定模型生死训练循环里最容易把人绕晕的是奖励的符号。路径长度是正的我们要最小化它所以每一步的奖励设置为负的总长度目标函数是最大化期望奖励。REINFORCE 的更新方向要求“比 baseline 好的动作概率提升比 baseline 差的动作概率下降”。def train_one_batch(model, optimizer, xy): B, C, _ xy.shape enc model.encode(xy) visit_mask torch.zeros(B, C, dtypetorch.bool, devicexy.device) prev_idx torch.zeros(B, dtypetorch.long, devicexy.device) prev_xy xy[:, 0, :] context enc[:, 0, :] visit_mask[:, 0] True log_probs [] total_dist torch.zeros(B, devicexy.device) for step in range(C - 1): log_p model.decode_step(context, enc, visit_mask) dist torch.distributions.Categorical(logitslog_p) idx dist.sample() log_probs.append(dist.log_prob(idx)) cur_xy torch.gather(xy, 1, idx.view(-1, 1).expand(-1, 2)).squeeze(1) total_dist torch.norm(cur_xy - prev_xy, dim-1) visit_mask visit_mask.scatter(1, idx.unsqueeze(1), True) context torch.gather(enc, 1, idx.view(-1, 1, 1).expand(-1, 1, model.d_k)).squeeze(1) prev_xy cur_xy # 最后回到起点路径闭合 total_dist torch.norm(xy[:, 0, :] - prev_xy, dim-1) log_probs torch.stack(log_probs, dim1) baseline total_dist.detach().mean() advantage baseline - total_dist.detach() loss (log_probs.sum(dim1) * advantage).mean() optimizer.zero_grad() loss.backward() torch.nn.utils.clip_grad_norm_(model.parameters(), 1.0) optimizer.step() return total_dist.detach().mean().item()advantage写成baseline - total_dist意思是这条路径比平均水平短优势为正模型会提高这条路径上动作的概率比平均水平长优势为负概率就会被压低。如果这里符号写反模型会反向优化专门去学更长的路线。total_dist.detach()是关键奖励不能把梯度传回采样动作策略梯度的梯度只应该流经log_probs。clip_grad_norm_的 1.0 是对付训练后期梯度爆炸的安全网丢了它训练到某个 batch 突然变成 NaN 的概率会大很多。4. 训练配置与参数清单照着抄能复现的默认值4.1 数据生成U(0,1)² 坐标、固定 seed 与训练/验证划分TSP 的强化学习不需要真实数据集坐标直接随机生成就行。最通用的做法是在单位正方形里采样均匀分布的坐标点所有坐标落在 0 到 1 之间这样欧氏距离天然在一个稳定尺度内模型对不同规模的 TSP 有一定迁移能力。如果你的坐标是从实际业务里来的比如仓库经纬度第一件事是归一化把最大最小值缩放到 0 到 1否则模型会把尺度当成隐含特征换个城市规模就失灵。def generate_instances(batch_size, seq_len, seed0): torch.manual_seed(seed) return torch.rand(batch_size, seq_len, 2)固定 seed 是写进训练脚本里最便宜的投资。同样一份代码换个 seed 可能跑出不一样的曲线不固定 seed你连“参数调整到底有没有效果”都判断不了。我一般会在train.py里同时固定 PyTorch 和 Python 的随机种子数据生成和模型初始化都走同一套 seed。训练集每次重新随机生成验证集单独存一份固定实例保证每次验证都在同样的问题上比较。验证集规模我习惯取 100 个实例统计贪心解码的平均路径长度这个数字波动不大足够做模型效果对比。4.2 超参清单从嵌入维度到梯度裁剪参数默认值说明embed_dim128坐标嵌入维度容量不够时首选增至 256n_heads8注意力头数TSP20 上用 4 也能跑num_encoder_layers3encoder 层数继续加深收益不明显batch_size256并行采样的轨迹数越小噪声越大learning_rate1e-4Adam 默认学习率调大容易崩grad_clip1.0梯度裁剪上限防 NaN 的第一道保险max_epochs100每个 epoch 内 200 个训练步ema_baseline0.9baseline 平滑系数稳定训练后半程seed0数据与权重初始化这些参数的组合在我的复现里是最稳的一组TSP20 在城市数不变的前提下训练几十个 epoch 后贪心解码的平均路径就能逼近 2-opt 启发式的结果。batch_size和learning_rate是关联的batch 越小REINFORCE 的梯度噪声越大学习率要相应调低。TSP20 这个规模上用普通独立显卡或者纯 CPU 都能跑区别只是速度CPU 上大概要等一个午休的时间也能看到稳定下降的趋势。4.3 训练日志看什么loss 下降不等于路径变短REINFORCE 有一个反直觉的现象loss 曲线下降得漂亮不代表策略在变好。因为优势值本身在变化loss 减小只能说明“当前这批轨迹的 log 概率与优势的乘积在收敛”路径质量要看验证集上的贪心解码平均长度。我每个 epoch 结束都会跑一次验证把当前模型在固定验证集上的平均路径长度打印出来这个数字才是模型有没有学到东西的唯一证据。def validate(model, val_instances): model.eval() total 0 with torch.no_grad(): for xy in val_instances: enc model.encode(xy) B, C, _ xy.shape visit_mask torch.zeros(B, C, dtypetorch.bool, devicexy.device) context enc[:, 0, :] prev_xy xy[:, 0, :] visit_mask[:, 0] True dist 0 for _ in range(C - 1): log_p model.decode_step(context, enc, visit_mask) idx log_p.argmax(dim-1) cur_xy torch.gather(xy, 1, idx.view(-1, 1).expand(-1, 2)).squeeze(1) dist torch.norm(cur_xy - prev_xy, dim-1) visit_mask visit_mask.scatter(1, idx.unsqueeze(1), True) context torch.gather(enc, 1, idx.view(-1, 1, 1).expand(-1, 1, 128)).squeeze(1) prev_xy cur_xy dist torch.norm(xy[:, 0, :] - prev_xy, dim-1) total dist.mean().item() return total / len(val_instances)训练日志里同时打印三列训练 loss、当前 epoch 的平均路径长度、验证集贪心平均长度。前两个很短时间就会稳定第三个才是决定要不要继续跑下去的关键。对照一个 2-opt 的结果作为参考线会比盯着 loss 曲线有用得多。5. 避坑与排查训练强化学习 TSP 最容易翻车的四个问题5.1 现象loss 一直在降贪心解反而越来越差原因几乎总是出在 advantage 的符号上。把优势写成total_dist - baseline而不是baseline - total_dist之后模型会认为“比平均路径更长”是好的于是每一轮都在强化那些绕远路的动作。训练曲线的 loss 看起来漂亮验证结果却一天比一天离谱。解决方式是先做一次符号自查训练一个 batch打印出advantage的均值和loss的符号如果最短路径对应的 advantage 是负数就说明写反了。把验证集的贪心路径长度加入训练日志是防止这类问题悄悄发生的最后防线。这个坑我在第一次复现这个方案时踩过整夜训练白跑第二天一早看到验证结果时心情相当复杂。5.2 现象解码时重复访问城市绕着绕着就卡死问题出在掩码没有施加在 logits 上而是施加在 softmax 之后的概率上。概率已经归一化掩码填零之后被掩位置的概率会被其他城市重新分配模型依然会以一个较高的概率指回已经访问过的城市。另外一个容易忽视的原因是起始城市的掩码没有初始化为 True整个循环里模型始终认为起点还没访问过。我一般会在训练循环和验证循环里各加一条断言比如assert visit_mask.sum() step 1一旦掩码数量对不上就立刻崩溃而不是带着错误继续训练。检查的时候把每一步采样出的城市索引打印出来肉眼看一下是否出现重复比盲改代码快得多。这算是代码诊断插件帮不上的问题它只能告诉你代码哪里语法错了这种逻辑错误还是得靠断言和日志。5.3 现象TSP20 学得很好换到 TSP50 直接翻车坐标没有归一化是这个现象最常见的原因。如果原始坐标的尺度在训练集和测试集之间不同模型学到的注意力打分尺度就完全错位。另一个原因城市规模变大后需要探索的路径空间呈指数增长TSP20 上训练出的策略根本没有见过那么长的序列注意力的累计偏差会让路径后半段质量迅速崩掉。解决方式分两步。第一步训练和测试的坐标统一归一化到 0 到 1这一步能解决大部分规模差异问题。第二步如果还想进一步提升在新规模上用旧模型初始化权重再做几十个 epoch 的微调比从零训练快得多收敛后的解质量也更稳定。这不算玄学相当于让模型先学会“怎么规划”再学“怎么规划更长”。5.4 现象训练中突然出现 NaN代码没有报错但 loss 变 NoneNaN 的来源通常有两个。第一个是log_softmax收到了全为负无穷的 logits比如掩码把一整行都掩掉了log(0)直接出现 NaN。第二个是梯度爆炸训练步数多了之后策略进入某个极端区域梯度数值过大更新后的参数直接溢出。第一个原因的做法是检查掩码逻辑确保每一步至少保留一个可选城市。第二个原因用梯度裁剪解决clip_grad_norm_设为 1.0在训练循环里是必写项。如果 NaN 已经出现模型参数基本废了没有后悔药只能从最近一次 checkpoint 恢复继续训练。所以训练脚本里一定要有定期存档我习惯每个 epoch 存一次这比训练中断后重头跑要省钱得多。6. 从跑通到能用三个不改变网络结构的验证与提升技巧模型训练到头验证结果的路径长度只领先随机策略一点还远远不够。接下来值得做的第一件事是采样式解码替代贪心解码。对每个验证实例用当前模型采样 16 条或 32 条路径取总长度最短的那条作为最终输出。采样引入了随机性等于在策略的指引下做了多轮探索TSP20 规模下通常比单次贪心再短几个百分点。代码改动很小在验证循环里把argmax换成Categorical分布采样重复多次后取最小距离。第二件事是引入一个像样的对比基线。2-opt 局部搜索几十行就能实现它不算强基线但对 TSP20 这类小规模问题已经能给出相当接近最优的解。把指针网络的结果和 2-opt 的结果做比值比如 1.05 以内的差距就说明模型学到的东西有实际价值如果差距超过 1.2优先去查数据归一化和 baseline 的稳定性而不是急着加大模型。这个比值也是向别人说明方案效果的硬指标比我跑出了几条好看路径的说服力强得多。第三件事也是我最后想强调的换规模时不要直接推理。TSP20 训练出的模型直接解 TSP50路径质量大概率不可接受这反而是正常现象不代表方案本身有问题。正确做法是在新规模上重新生成训练数据用旧模型初始化新模型微调几十个 epoch 后再验证。我最早做这个方案时把 baseline 写成了 batch 内的瞬时平均训练到后期整个策略退化到只输出同一条单调路线。后来改成指数移动平均 baseline路径质量才稳定下来。回头看固定 seed、定期存档、验证集固定实例这三件事是让训练过程少受折磨的前提。希望这次的实操记录能帮你在指针网络和 TSP 上少走一段弯路。本文还有配套的精品资源点击获取