内容概述

组合优化（CO）广泛应用于物流调度、资源分配、硬件设计等场景，多为 NP 难问题，传统数学规划与人工启发式方法难以适配大规模、多约束任务。神经组合优化（NCO）结合深度学习实现自动求解，其中强化学习（RL）因无需标注数据、可自主探索最优解，成为主流研究方向。

组合优化（CO）多为 NP-hard，传统方法（精确求解器/人工启发式）难以适配大规模、高约束场景。

方法类别	优点	缺点
精确求解器（如 Gurobi）	最优解保证	指数级时间，不可扩展
人工启发式（如 LKH）	工程效果好	设计成本高，泛化差
监督学习（SL）	直接模仿最优解	需要大量标注数据，标注本身是 NP-hard
强化学习（RL）	无需标注，自主探索	奖励稀疏，训练不稳定

RL 的关键优势：以解的代价本身作为奖励信号，无需任何人工标注。

当前该领域缺少统一基准测试框架，存在评估标准不一、结果可复现性差、工程成本高、入门门槛高等问题。为此本文提出RL4CO开源基准框架，集成 27 类优化环境、23 个前沿基线模型，采用模块化、高效化实现，可灵活适配各类算法与策略。

该框架主要贡献为：简化开发、提升实验效率、标准化评估、赋能社区发展，为神经组合优化提供统一研究平台，助力领域创新与成果迭代。

表 1.1 对比了多款强化学习领域的组合优化软件库，可见本文提出的 RL4CO 基准框架功能最为全面。

核心建模：CO → MDP

将"逐步构造解"过程建模为马尔可夫决策过程（MDP），是 NCO 的核心范式。

$$(\mathcal{S},\mathcal{A},\mathcal{T},\mathcal{R},\gamma )$$

元素	含义	CO中的含义
$\mathcal{S}$	状态空间	问题实例 $x$ + 当前部分解
$\mathcal{A}$	动作空间	每步可选的节点/分配方式
$\mathcal{T}(s_t,a_t)$	状态转移（确定性）	将动作追加到部分解
$\mathcal{R}(s_t,a_t)$	即时奖励	通常仅在终止步给出（稀疏）
$\gamma$	折扣因子	CO中常取 $\gamma =1$（无折扣）

关键推论：由于转移确定性，解 $\mathbf{a}=(a_0,\dots ,a_{T-1})$ 唯一对应一条轨迹，于是：

$$\text{累计奖励}=\sum _{t=0}^{T-1}\mathcal{R}(s_t,a_t)=-\text{cost}(\mathbf{a},x)$$

即最大化累计奖励 ≡ 最小化解的代价。这一等价性使得 RL 目标与 CO 目标完全对齐，无需额外设计。

为什么稀疏奖励是大问题：TSP 等问题只有走完全程后才能计算总距离，中间每步的奖励为 0。这使得基于值函数的方法（A2C、DQN）很难学到有意义的状态价值估计。

策略设计

构造式 vs 改进式

构造式策略：∅ → 完整解（从零开始逐步决策）
改进式策略：解₀ → 解₁ → … → 解ₖ（迭代优化现有解）

选择原则：

• 计算资源受限 → 构造式（一次前向传播即得解）
• 追求高质量解 → 改进式（可无限迭代）
• 最优实践 → 构造式初始化 + 改进式精调

---

自回归（AR）构造式策略

$$\pi (\mathbf{a}|x)=\prod _{t=0}^{T-1}g(a_t\mid a_{t-1},\dots ,a_0,s_t,\mathbf{h})$$

其中 $\mathbf{h}=f(x)$ 是编码器输出的实例嵌入。

架构核心：注意力编码器-解码器（Attention Model, AM）

编码器（Transformer 变体）：

• 输入：节点特征（如坐标） → 线性投影得初始嵌入
• 通过 $L$ 层多头注意力（Multi-Head Attention, MHA）更新节点嵌入
• 输出：每个节点的上下文感知嵌入 ${\mathbf{h}}_i\in {\mathbb{R}}^d$，以及图全局嵌入 $\bar{\mathbf{h}}=\text{mean}({\mathbf{h}}_i)$

解码器（指针网络机制）：

• 构造查询向量 $q_t$（上下文嵌入 ${\varphi }_c$）：融合当前部分解状态
  • TSP：$q_t=[h_{\text{last}},h_{\text{first}},\bar{h}]$ 的线性变换
  • CVRP：额外加入剩余容量特征
• 注意力得分（tanh 裁剪防止极端值）：

$$u_{i,t}=C\cdot \tanh \left(\frac{q_t^{\top }{k}_i}{\sqrt{d}}\right),C=10$$

• 对不可行动作（已访问节点、超容量节点）掩码为 $-\infty$，再经 Softmax 得概率：

$$P(a_t=i\mid s_t)=\text{softmax}(u_{\cdot ,t}{)}_i$$

三类嵌入的分工：

嵌入类型	映射	作用
节点嵌入 ${\varphi }_n$	${\mathbb{R}}^{N\times m_n}\to {\mathbb{R}}^{N\times h}$	编码各节点静态特征
边嵌入 ${\varphi }_e$	${\mathbb{R}}^{E\times m_e}\to {\mathbb{R}}^{E\times h}$	编码边权/距离矩阵（如 MatNet）
上下文嵌入 ${\varphi }_c$	${\mathbb{R}}^{m_c}\to {\mathbb{R}}^h$	编码当前解码步骤的动态状态

---

非自回归（NAR）策略

NAR 一次性输出全局启发式热图：

$$\mathcal{H}=f(x)\in {\mathbb{R}}_{+}^N\text{（各边/分配方式的未归一化概率）}$$

典型代表：扩散模型（DIFUSCO）、基于热图的 DPDP 等。特点是可以并行解码，但需要额外的后处理（动态掩码/束搜索）来保证解的可行性。

---

RL 训练算法

优化目标

$${\theta }^{\ast }=\underset{\theta }{\mathrm{argmax}}{\mathbb{E}}_{x\sim P(x)}\left[{\mathbb{E}}_{\mathbf{a}\mid x}\left[\sum _{t=0}^{T-1}\mathcal{R}(s_t,a_t)\right]\right]$$

---

REINFORCE 及其基线

策略梯度（REINFORCE）的核心问题是梯度方差极大：

$${\nabla }_{\theta }\mathcal{L}=\mathbb{E}\left[(R(\mathbf{a},x)-b(x)){\nabla }_{\theta }\log \pi (\mathbf{a}\mid x)\right]$$

基线 $b(x)$ 的理想值是 $\mathbb{E}[R(\mathbf{a},x)]‘$：

• $b$ 过低 → 所有动作都获得正强化，学习效率低
• $b$ 过高 → 所有动作都被抑制，策略退化
• $b=\mathbb{E}[R]$ → 梯度无偏，方差最小

各类基线的本质对比：

基线方法	估计方式	适用场景	缺陷
A2C 价值网络	神经网络估计 $V(s)$	稠密奖励 MDP	CO稀疏奖励下难以训练，本质上需要网络"解决"整个问题
贪心滚动基线（AM）	当前最优贪心策略的奖励	通用	计算成本高（需额外前向推理）
POMO 平均基线	$N$ 个起点的平均奖励	路由对称问题（TSP）	非对称/有约束问题中基线虚高（见下分析）
Sym-NCO 增强基线	对称变换（旋转+翻转）的平均	欧几里得问题	非欧几里得（调度、非对称路由）不适用
指数移动平均	历史奖励的 EMA	通用	响应慢，对策略更新滞后

A2C 失效的深层原因：
CO 问题中价值函数 $V(s_t)$ 需要估计"从当前部分解出发，最终能得到多少奖励"。但这本质上等价于求解剩余子问题——一个同样是 NP-hard 的任务。神经网络很难从稀疏的终止奖励信号中反向传播出有意义的中间价值估计。

POMO 基线失效于定向问题（OP）的分析：

• TSP 中任意城市都可作为合理起点，$N$ 条轨迹质量相近 → 平均基线接近真实期望 → 有效
• OP 有时间预算约束，只有部分节点是好的起点（高价值密集区），其余节点根本不该选 → 平均奖励虚低 → 基线偏差大 → 梯度噪声大

---

归纳式 vs 转导式 RL

类型	训练时机	泛化方式	代表方法
归纳式	离线在训练集上训练	直接泛化到新实例（一次前向推理）	AM, POMO, MatNet
转导式（测试时自适应）	在测试实例上在线优化	针对单个实例微调参数	EAS, DPDP

实践中的最优策略：先用归纳式训练获得好的初始策略，再用转导式在测试实例上自适应微调——本质是将预训练作为 warm start，大幅减少转导式所需的迭代次数。

---

解码策略

解码策略定义了"如何从概率分布 $P(\mathcal{A})$ 中选取动作"，是推理阶段性能的核心变量：

策略	方式	适用
贪心（Greedy）	$a_t=\arg \max P$	快速，解质量一般
采样（Sampling）	$a_t\sim P$	多次采样取最优，质量提升显著
POMO 多起点	强制 $N$ 个不同起始节点	路由问题，低额外成本的多样性
数据增强（Augmentation）	对实例施加旋转/翻转变换	欧几里得问题

采样参数的精细控制：

• 温度缩放 $\tau$：$P_{\tau }(a)\propto \exp (u_a/\tau )$，$\tau \to 0$ 趋于贪心，$\tau \to \infty$ 趋于均匀
• Top-$k$ 采样：只从概率最高的 $k$ 个动作中采样（减少无意义探索）
• 核采样（Top-$p$）：从累计概率达 $p$ 的最小集合中采样（动态截断）

实验发现（CVRP50）：采样策略在样本量相同时通常优于增强策略；Top-$p$ 采样在适中样本预算下性价比最高（见图 5.1 帕累托前沿）。

---

关键实验洞察

模块替换即可显著提升性能

以 FJSSP（柔性作业调度）为例：

基线（HGNN 编码器 + MLP 解码器）
  ↓ 替换编码器
MatNet 编码器（更强的边特征表达） → makespan 下降 ~7%
  ↓ 替换解码器
AM 指针机制 → 最优性间隙降至原方法的 1/3（贪心解码下）
  ↓ 换解码策略
128 次采样 → 进一步提升

核心结论：NCO 的性能瓶颈往往在于编码器对问题结构（尤其是边/交互关系）的表达能力，而非解码器。

构造式 + 改进式混合

实验在 TSP-50 上对比三种范式：

方法	原积分（PI）↓越好
DACT（改进式，随机初始化）	2.99
NeuOpt（改进式，随机初始化）	2.26
POMO（构造式，128次采样）	0.08
POMO → DACT（构造式初始化改进式）	0.08
POMO → NeuOpt	0.04

原积分（PI，Performance Integral）：衡量解质量随时间变化的曲线下面积（越小越好），能同时评估最终质量与收敛速度。

关键洞察：构造式方法生成的初始解显著加速改进式收敛，因为改进式算法本质上是局部搜索，好的起点减少了"爬出差解区域"的迭代。

多分布/多任务训练提升泛化

在 CVRPLib 基准测试中，跨分布训练（MDPOMO） 比单分布训练（POMO）泛化性能更优，在分布外数据集上差距尤为明显——支持了构建 CO 基础模型（Foundation Model）的可行性。

---

框架设计要点（工程视角）

无状态张量字典设计：环境状态 $s_t$ 以张量字典存储，避免 Python 对象开销，支持 GPU 并行批处理（相比逐实例仿真，步进延迟降低 50%，内存占用减半）。

分层配置（Hydra）：实验参数通过 YAML 文件管理，便于超参数扫描与结果复现，避免硬编码。

核心依赖：PyTorch + TorchRL（环境/策略接口）+ PyTorch Lightning（训练循环/分布式）+ Hydra（配置管理）。

---

开放问题与前沿方向

1. CO 基础模型：能否像 LLM 一样，在大量 CO 问题上预训练单一模型，然后 few-shot 迁移到新问题类型？当前 MTPOMO/Uni-CO 是初步探索。

2. 大规模算例：千级节点 CVRP 仍依赖分治（GLOP 等）而非端到端——单次注意力计算复杂度 $O(N^2)$ 是根本瓶颈，需要线性注意力或分层方案。

3. 改进式方法的 RL 设计：改进式策略中每次扰动（2-opt, Or-opt）的奖励如何定义？稠密奖励（每步改进量）还是稀疏奖励（最终质量）——这个选择对训练稳定性影响显著。

4. 非欧几里得/异构问题：调度、芯片布局等问题不具备 Sym-NCO 的对称增强，且节点/边的异构性更强，需要更通用的嵌入设计。