研究 01 · 强化学习 · 图神经网络
使用强化学习创建TSP路径的图模型
2018.09–2021.06 · 本科生研究助理我实现了基于图模型的 TSP 搜索程序，通过强化学习选择下一个插入路径的城市。
- 1以图的形式表示
城市、距离、访问状态
- 2Structure2Vec + Q-learning
计算每个城市的 Q 值
- 3城市选择和路径插入
插入模型使用启发式算法选择的城市
强化学习设计
- 状态
- 城市连接（邻接矩阵）与距离，以及已加入路线的城市
- 动作
- 选择下一个加入路线的城市
- 奖励
- 加入城市后增加的路线长度直接作为扣分
参考NeurIPS 2017图组合优化研究实现
直接分配的角色和结果
- 研究目标
- TSP 的可能路线数量会随城市增加而急剧增长，目标是比现有算法更快地找到更短的路线。我与指导教授一起尝试用强化学习来解决。
- 已分配角色
- 基于参考论文中的图表示和Q学习思想，我实现了连接TSP环境、模型、学习循环和插入规则的实验代码。
- 成果
- 我编写了一个搜索程序：把城市的位置、距离和访问状态作为图输入，并用插入启发式把模型选出的城市加入路线。用公开代码与基线进行对比实验时，我也找出了学习未能正常起作用的原因。
我内部实施和分析的内容
- 包含节点、边、访问状态和路径成本记录的图环境
- Structure2Vec嵌入和Q值评估
- 连接多步奖励累积和经验采样的探索循环
- 模型选择城市，插入启发式算法确定插入位置的结构。
基于研究 · 公开模型
- NeurIPS 2017 用于图组合优化研究的 Structure2Vec/强化学习方法
实验结果与试错
短路学习中未观察到与随机插入相比的改进
使用原始设置进行训练后，该策略对所有城市和按数值顺序选定的城市都产生了相同的 Q 值。
- TensorFlow 2.15
- 3个随机种子
- 训练轮数：10,000 → 100
- +12%以上 50 度示例 · OR-Tools 比太阳还长路径
- 改进未确认与随机顺序插入相比，学习时间更短
- 2 件事代码中发现原因
- 预期
选择学习到的 Q 值使路径更短的城市
- 当时的判断
随着训练路线成本有所下降，但没有达到最优解；当时认为是城市太多、探索不够充分
- 实际
由于所有城市的 Q 值相同，因此按数值顺序选择
- 原因
未归一化的邻域总和导致数值飙升，而 TD 目标仅考虑起始城市。
问题及解决方案
问题矩阵大小随城市数量而变化，无法直接输入固定尺寸的神经网络。
已解决。用 Structure2Vec 为每个城市生成嵌入，再由评估网络为每个未访问的城市给出 Q 值。
问题仅选择下一个城市并不能确定它在路径上的位置。
已解决。学习模型负责城市选择，而插入位置则结合了一种启发式算法，该算法旨在找到使路径长度增加最小的位置。
问题即使出现短路径，也很难区分是学习效应还是插入规则效应造成的。
分析·验证我们对随机城市顺序应用了相同的插入规则进行比较，并跟踪了 Q 值和 TD 目标计算结果。我们没有发现短路学习策略有所改进。
实验对比及详细结果
| 城市数量（问题数量） | 训练策略 | 随机顺序 + 插入 | 插入新对象 | 最近邻居 | 训练策略与随机训练（Wilcoxon p 检验） |
|---|---|---|---|---|---|
| 20 (100) · 学习范围之外 | 1.11 | 1.11 | 1.03 | 1.18 | 0.96 |
| 50 (50) | 1.13 | 1.14 | 1.05 | 1.21 | 0.24 |
| 100 (30) | 1.12 | 1.13 | 1.06 | 1.22 | 0.38 |
已观察到的原因和剩余任务
- Q值爆炸
未进行归一化处理时，对整个图求和导致 Q 值增长至数百万，更新损失飙升至 10¹⁵ 个单位。
- TD目标误差
目标值始终基于起始城市的 Q 值而非剩余城市的 Q 值计算，并且 n 步后的下一状态也存在一步偏差。
- 缩减至第100集
由于大型图表每集大约需要 45 秒，因此 10,000 次迭代将耗时超过 5 天。我减少了迭代次数，其余设置保持不变。
读取结果的条件
- 并非直接复现原始论文（无目标网络，n步方法不同）
- 仅学习已配置的 1%章节
- 训练到末端时的性能未知
下次实验需要改进的地方
- 先将答案与小问题匹配
- 邻居总和归一化和目标值校正
- 从一开始就设置随机顺序基线