【论文笔记】NEURAL COMBINATORIAL OPTIMIZATION WITH REINFORCEMENT LEARNING

本文提出了一种结合强化学习（RL）和指针网络的新型指针网络模型用于解决组合优化问题（TSP）。通过引入Critic网络来估计策略的好坏，并采用抽样搜索和主动搜索相结合的方法进行策略优化。实验结果表明，在解决旅行商问题（TSP）时，该方法显著优于传统启发式算法；同时将其应用于背包问题时，在保证解的质量的同时显著提升了求解效率。该研究展示了基于RL的指针网络模型在复杂组合优化任务中的广泛适用性和有效性。

目录

• 论文

• • 一、概论

  • 二、模型

  • • 参数
    • 公式
    • 网络
    • • Critic网络

  • actor-critic算法

    • 搜索策略

  • 三、实验及结果

  • • 几种不同的实验组合
    • 实验结论

  • 四、迁移到背包问题

  • • 定义
• 实验结论

论文

强化学习+指针网络+组合优化

一、概论

主要应用基于强化学习的策略梯度方法用于构建指向网络模型以解决旅行商问题（TSP）。此外发现加入主动学习机制能够显著提升模型表现。

二、模型

参数

s：是输入的序列坐标集
\theta：网络的参数
\pi：一种策略（参数）的输出结果

公式

定义结果好坏

\pi结果出现的可能性【链式展开】

定义在s的空间中，参数为\theta的L的期望值

s是S空间中的一个分布（子集），所以定义总的L为——期望

详细计算3式中的梯度——采用强化学习相关的方法
其中b(s)式不受策略\pi的影响作为基准值使用，并用于降低梯度

梯度近似表示采用了蒙特卡洛采样的方法以估计梯度信息

找出确定b(s)的方法。
一种常用方法是利用一定时间内的数据计算网络累积获得的奖励的指数移动平均值，并用于衡量策略随训练逐步改进的情况。共享参数b可能无法涵盖所有状态s的最佳策略结果。

构建critic网络模型；旨在训练一个具有特定参数（其中参数为\theta_v）的网络；基于给定的一个初始图s进行运算以输出该策略的基准值b

网络

Critic网络

• 基于长短期记忆机制的编码器——类似于Ptr的设计（多个潜在的记忆单元及一个隐藏状态h）
• LSTM模块——经过p次迭代计算
• 两层ReLU激活函数，将输出转换为单一数值表示（表示b）

基于actor-critic的算法

搜索策略

在本TSP问题中，判断一个解好坏的成本较低，在每个输入图中探索所有候选方案后确定最优解决方案。主要采用采样式遍历与主动式探索的方法进行求解。

该系统采用抽样方法对目标空间进行遍历，在决策过程中通过计算各点的softmax值来确定访问概率。基于此设计的贪婪算法，在每一步迭代中都会优先选择具有最高访问概率的点进行探索。值得注意的是，在此方案中我们采用了温度超参数模型进行归一化处理（Softmax(u/T)），通过引入温度参数T进行归一化处理（Softmax(u/T)），这种方法不仅能够平衡各选项的概率分配还能显著提升算法的探索效率。

主动式搜索
若采用固定采样模型，则会忽视奖励值这一信息。在单个测试输入中对参数θ进行细致调整，并据此优化策略参数。

三、实验及结果

几种不同的实验组合

实验结论

结果表明：

通过RL进行训练明显提升了监督学习（Vinyals等，2015b）。
我们所有的方法轻易超过了 Christofides’ heuristic method，并且其中包括了一种无需搜索的RL预训练贪婪策略。

在推理阶段执行搜索操作对于接近最优解具有重要意义,然而这可能会导致运算时间显著延长. 幸运的是,基于最终目标函数值的小幅性能损失,RL预训练采样方法和RL预训练活动搜索技术能够实现早期终止.

四、迁移到背包问题

背包问题定义

定义

我们采用了指针网络，并将每个背包实例表示为二维向量序列(wi, vi)。在解码过程中，指针网络指示出要放入背包中的物品。一旦所收集物品的总重量超过规定重量容量，则解码过程不再继续。

实验结论

• 第一个基准采用贪婪权重与价值比的启发式方法
• 第二个基准采用随机搜索策略
• 我们对主动搜索进行了充分的评估
• 这些greedy方法生成的结果平均偏离最优解仅约1%
• 而Active Search则成功地将所有测试案例优化至全局最优状态。