神经组合优化强化学习-PyTorch

基于 Neural Combinatorial Optimization with Reinforcement Learning 的 PyTorch 实现。

我实现了论文中带有贪心解码的基本 RL 预训练模型。监督学习基线模型的实现可在 这里 找到。我没有使用评论网络，而是通过指数移动平均评论器在 TSP 问题上获得了以下结果。目前我的代码中评论网络部分已被注释掉。根据与其他几位研究者的交流，大家一致认为使用指数移动平均评论器能够显著提升实验效果。

我的实现中，在训练阶段，指针网络采用随机解码策略，通过 PyTorch 的 torch.multinomial() 函数实现；而在测试模型时，则使用束搜索（尚未完成，目前仅支持 1 束，即贪心解码）进行解码。

当前，该实现支持排序任务和平面对称欧几里得 TSP 问题。

请参阅 main.sh 文件，了解如何运行代码的示例。

使用 --load_path $LOAD_PATH 和 --is_train False 标志可加载已保存的模型。

若要加载已保存的模型并查看指针网络的注意力层，还需添加 --plot_attention True 标志。

如果您遇到任何问题，或希望提交拉取请求以改进此实现，请随时与我联系。

添加其他任务

此实现可以扩展以支持其他组合优化问题。请参考 sorting_task.py 和 tsp_task.py 文件，了解如何添加新任务的示例。关键在于提供一个数据集类和一个奖励函数，该函数接收由指针网络从输入中选择的样本解，并返回一个标量奖励。对于排序任务，智能体获得的奖励与解码输出中最长严格递增子序列的长度成正比（例如：[1, 3, 5, 2, 4] -> 3/5 = 0.6）。

依赖项

• Python=3.6（v >= 3.4 应该也可以）
• PyTorch=0.2 和 0.3
• tqdm
• matplotlib
• tensorboard_logger

PyTorch 0.4 兼容版本位于 pytorch-0.4 分支。

TSP 结果

单个随机种子下，经过 50 个 epoch 的训练（每个 epoch 包含 10,000 个大小为 128 的批次）。每完成一个 epoch，我都用 1,000 个保留图验证了模型性能。我使用了与论文相同的超参数，详见 main.sh 文件。虚线表示 Bello 等人在表 2 中给出的数值，用于对比。训练奖励的对数横轴用于展示旅行商路径长度在早期阶段的快速下降趋势。

排序结果

我在 sort10 数据集上训练了一个模型，共 4 个 epoch，每个 epoch 包含 1,000,000 个随机生成的样本。随后，我在一个包含 10,000 个样本的数据集上进行了测试。接着，我又在同一模型上测试了 sort15 和 sort20 数据集，以评估其泛化能力。

在 10,000 个样本上的测试结果（奖励值为 1.0 表示网络完美地对输入进行了排序）：

任务	平均奖励	方差
sort10	0.9966	0.0005
sort15	0.7484	0.0177
sort20	0.5586	0.0060

sort10 的预测示例：

输入: [4, 7, 5, 0, 3, 2, 6, 8, 9, 1]
输出: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

注意力可视化

可通过添加 --plot_attention True 参数来绘制指针网络的注意力层。

待办事项

• 添加 RL 预训练—采样
• 添加 RL 预训练—主动搜索
• 主动搜索
• 类似 A3C 的异步训练
• 重构 USE_CUDA 变量
• 完成束搜索解码的实现，以支持 > 1 束
• 添加对变长输入的支持

致谢

特别感谢 devsisters/neural-combinatorial-rl-tensorflow 和 MaximumEntropy/Seq2Seq-PyTorch 这两个仓库，它们让我顺利起步；同时也感谢 @ricgama 帮助我解决了 clone() 方法中的那个奇怪 bug。

neural-combinatorial-rl-pytorch 快速上手指南

本指南基于 PyTorch 实现了论文《Neural Combinatorial Optimization with Reinforcement Learning》中的核心算法，主要用于解决组合优化问题（如旅行商问题 TSP 和排序任务）。

环境准备

系统要求

• 操作系统：Linux / macOS (Windows 需自行配置兼容环境)
• Python 版本：推荐 Python 3.6 (兼容 v >= 3.4)
• PyTorch 版本：原生支持 0.2 和 0.3。
  • 注：若需使用 PyTorch 0.4+，请切换至 pytorch-0.4 分支。

前置依赖

安装必要的 Python 库。国内用户推荐使用清华或阿里镜像源加速安装：

pip install -i https://pypi.tuna.tsinghua.edu.cn/simple torch==0.3.0 tqdm matplotlib tensorboard_logger

注意：由于该项目基于较旧版本的 PyTorch (0.2/0.3)，直接安装最新版可能导致兼容性问题。建议创建虚拟环境并指定版本安装，或参考项目 pytorch-0.4 分支进行适配。

安装步骤

1. 克隆仓库

   git clone https://github.com/pemami4911/neural-combinatorial-rl-pytorch.git
   cd neural-combinatorial-rl-pytorch
   

2. 验证依赖 确保已安装 tqdm, matplotlib 和 tensorboard_logger。如有缺失，请参照上方“环境准备”中的命令安装。

基本使用

项目通过 main.sh 脚本提供运行示例，支持训练、测试及可视化。

1. 运行训练或测试示例

查看并执行默认的示例脚本（包含超参数设置）：

chmod +x main.sh
./main.sh

默认配置通常包含 TSP 任务的训练流程。

2. 加载预训练模型进行测试

若已有保存的模型权重，可使用以下命令加载并进行推理（关闭训练模式）：

python main.py --load_path $LOAD_PATH --is_train False

请将 $LOAD_PATH 替换为实际的模型文件路径。

3. 可视化注意力机制

在加载模型测试时，添加 --plot_attention True 参数即可绘制指针网络（Pointer Network）的注意力层热力图，用于分析模型决策过程：

python main.py --load_path $LOAD_PATH --is_train False --plot_attention True

4. 扩展新任务

如需支持其他组合优化问题，可参考 sorting_task.py 和 tsp_task.py 的实现逻辑：

• 定义新的数据集类。
• 编写奖励函数（Reward Function），该函数接收指针网络生成的解序列，返回标量奖励值。