HyCO: A Hybrid Neural Solver for Combinatorial Optimization¶

会议: NeurIPS 2026
arXiv: 2609.07990
代码: https://github.com/ai4co/rl4co
领域: 优化/理论
关键词: 神经组合优化, 强化学习, 扩散模型, 遗憾界分析, 混合求解器

一句话总结¶

针对神经组合优化中序列强化学习长程累积误差与全局扩散模型全空间高遗憾的互补缺陷，HyCO提出在统一边际遗憾框架下寻找唯一最优交接点，并通过策略熵与模型分歧轻量自适应触发单次交接与双轨补全，在TSP、MIS和OP上一致大幅超越单一求解器。

研究背景与动机¶

神经组合优化（Neural Combinatorial Optimization, NCO）近年来逐渐成为运筹学与机器学习交叉领域的核心前沿，旨在利用深度学习直接从问题数据中学习高效启发式算法，以应对如旅行商问题（TSP）、最大独立集（MIS）等NP-hard难题。然而，现有主流神经求解器在设计范式上存在天然割裂，主要分化为基于序列强化学习（RL）的自回归构造方法与基于扩散模型（DM）的非自回归全局生成方法。自回归RL求解器如AM、POMO推理极其高效，但在长决策视野下极易受到视距累积误差（horizon-wise compounding errors）困扰，微小的局部决策偏差会随时间步推移导致状态轨迹严重偏离训练分布，带来超线性的累积遗憾膨胀。

与此相对，基于离散图扩散模型的全局求解器如DIFUSCO从全局视角出发直接生成解热图，彻底规避了视距级误差累积，但其固有的边际遗憾受制于未求解子空间的有效维度。在全空间维度从零生成完整解时，庞大的搜索空间会引发极高的统计估计与离散化漂移遗憾，使得纯扩散求解器在缺乏前置约束时往往需要海量并行采样才能换取高精度解。有趣的是，一旦引入部分固定前缀（prefix），条件扩散模型面临的有效未解维度显著收缩，其边际遗憾保持恒定甚至递减，这与RL求解器随步数递增的边际遗憾形成了强烈的空间-时间互补性。

这种互补的误差扩展动力学揭示出一个根本性的结构交汇点：在求解初期，RL凭借高局部置信度以极低遗憾快速圈定骨架；在求解后期，维度缩减后的条件扩散模型凭借全局协同约束消除累积误差。核心 idea：将神经组合优化解构为序列RL前缀构造与条件DM全局生成的单次自适应交接流水线，在理论上证明最优交接点的存在唯一性与严格优势，并在推理时通过策略熵与跨模型分歧双信号自适应捕捉转移临界点。

方法详解¶

整体框架¶

HyCO在整体设计上采用即插即用的单次交接（Single-Trigger）流水线架构。算法从待求解的组合优化实例出发，首先启动贪婪自回归的快速序列RL求解器逐步构建部分解前缀；在每一步决策中，轻量自适应触发器实时监控轨迹级的内部不确定性与跨模型全局一致性。一旦满足触发条件，RL求解器将控制权移交给条件扩散模型并执行双轨解生成（Dual-Track Generation）：一条轨道利用扩散模型的全局提议修正RL在触发步的决策并继续由快速RL完成后续贪婪构造，另一条轨道直接由条件扩散模型全量采样补全若干完整候选；最终在双轨提议集合中取目标成本最优者作为最终输出。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}, 'subGraphTitleMargin': {'top': 8, 'bottom': 16}}}%%
flowchart TD
    A["输入组合优化实例<br/>图/节点坐标/约束"] --> B["自回归RL前缀构造<br/>逐布贪婪展开与前缀扩展"]
    B --> C["双信号自适应触发器<br/>监测策略熵与RL-DM分歧"]
    C -->|未达阈值| B
    C -->|触发单次交接| D["双轨候选生成与修正"]
    subgraph D["双轨候选生成与修正"]
        direction TB
        E1["混合路径修正轨<br/>DM修正即时动作 + RL快速收尾"]
        E2["全量扩散提议轨<br/>Top-P前缀分支 + 条件DM采样补全"]
    end
    D --> F["全局最优解选择<br/>综合双轨候选取最小目标值"]

关键设计¶

1. 边际遗憾均衡理论：证明混合架构的严格优势与最优触发点唯一性

针对传统组合优化缺乏对序列构造与全局生成统一建模的理论空白，HyCO在目标函数的连续松弛 Lipschitz 连续性假设下，建立了连接传输几何距离（Wasserstein-1）与统计信息散度（KL散度）的统一遗憾界分析框架。理论证明条件扩散模型的优化遗憾受未求解子空间有效维度 $d_{\text{eff}} = d - h$ 控制，满足次线性扩展界 $\mathcal{R}_{\text{DM}}(d_{\text{eff}}) \le \mathcal{O}(\ell \cdot \sqrt{d_{\text{eff}}} \cdot \epsilon_{\text{score}})$，其边际遗憾 $r_{\text{DM}}(h)$ 随前缀长度非增；而自回归RL在单幕长程视距下累积遗憾呈现超线性扩展 $\mathcal{R}_{\text{RL}}(h) \sim \mathcal{O}(h^\alpha) (\alpha > 1)$，其边际遗憾 $r_{\text{RL}}(h)$ 严格单调递增。若满足边界条件 $r_{\text{RL}}(0) < r_{\text{DM}}(0)$ 且 $r_{\text{RL}}(d) > r_{\text{DM}}(d)$，总混合遗憾： $$\mathcal{L}(\tau) = \int_{0}^{\tau} r_{\text{RL}}(h)\,dh + \int_{\tau}^{d} r_{\text{DM}}(h)\,dh$$ 的导数 $\mathcal{L}'(\tau) = r_{\text{RL}}(\tau) - r_{\text{DM}}(\tau)$ 严格单调递增且必然在区间 $(0, d)$ 内存在唯一的零点 $\tau^*$，满足 $r_{\text{RL}}(\tau^*) = r_{\text{DM}}(\tau^*)$。这从数学上确证了单次交接混合策略的期望遗憾严格低于纯RL或纯DM基线。

2. 双信号轻量自适应触发器：轨迹级代理捕捉机制漂移

由于理论最优交接步数 $\tau^*$ 是在期望遗憾层面定义的、无法在单条解题轨迹上由预言机直接计算，HyCO设计了兼具内部不确定性与外部先验对齐的轻量双信号触发机制。内部信号采用RL策略分布的信息熵： $$H(\pi_\theta(\cdot \mid s_k)) = -\sum_{a \in \mathcal{A}_k} \pi_\theta(a \mid s_k) \log \pi_\theta(a \mid s_k)$$ 当熵值骤升时，表明RL候选动作概率扁平、缺乏显著优势动作，贪婪延拓极易失稳。外部信号通过单步去噪能量探测评估RL局部偏好与扩散全局先验的一致性：对RL概率最高的 Top-$M$ 个候选动作分别拼接形成一步扩展前缀 $c_k^{(i)} = c_k \oplus a_k^{(i)}$，通过扩散模型预估连接边的负对数似然能量 $E_\phi(c_k^{(i)})$，经玻尔兹曼分布转化为离散先验 $q_{\text{DM}}$，进而计算受限支集上的KL散度 $D_{\text{KL}}(\pi_\theta \parallel q_{\text{DM}})$。当满足条件： $$H(\pi_\theta(\cdot \mid s_k)) > H_{\text{th}} \quad \lor \quad D_{\text{KL}}(\pi_\theta \parallel q_{\text{DM}}) > D_{\text{th}}$$ 时立即触发交接。该“逻辑或”规则既能捕获RL自身举棋不定的时刻，又能纠正RL过于自信却与全局拓扑相抵触的决策暗礁。

3. 双轨生成与容错修正机制：兼顾多样性与底线可靠性

在触发交接步 $k^*$，为防止单一生成路径因触发时机微弱偏差或扩散采样随机性导致求解质量受损，HyCO部署了互补的双轨生成机制。第一条轨道是全量扩散提议池 $\mathcal{P}_{\text{DM}}$：基于RL在触发步给出的累积概率阈值 $P_{\text{th}}$ 筛选高质量前缀分支，利用前缀条件扩散模型（Prefix-Difusco）执行并行DDIM反向去噪采样，获得一组具备强全局连贯性的完整候选。第二条轨道是混合修正路径 $l_H$：直接从扩散提议池中最优样本提取在步数 $k^*$ 的决策动作 $a_{k^*}^{\text{DM}}$ 替换原本RL的局部贪婪动作，随后重新切回轻量级RL自回归策略完成后续步骤的快速收尾。最终解在双轨所有候选集合 $\{l_H\} \cup \mathcal{P}_{\text{DM}}$ 中通过目标成本比较产生： $$l_{\text{out}} = \arg\min_{l \in \{l_H\} \cup \mathcal{P}_{\text{DM}}} \mathrm{Cost}(l)$$ 这一机制使混合系统即便在扩散去噪出现不可行边或质量波动时，依然拥有RL快速构造作为安全锚点。

一个完整示例¶

以求解规模 $N=100$ 的 2D TSP 为例： 1. RL起手：POMO策略从起始节点贪婪展开，前 5 步路径清晰紧凑，策略熵 $H_k \approx 0.12$，单步扩散能量探测显示 $D_{\text{KL}} \approx 0.08$； 2. 信号异动与触发：在步数 $k=6$ 时，路径面临两组分离簇的选择，RL输出出现明显双峰导致策略熵跳升至 $H_6 = 1.85 > H_{\text{th}}$，同时扩散探测预估若强行依贪婪边缘连接将严重破坏对向未访问点闭合，产生 $D_{\text{KL}} = 1.92 > D_{\text{th}}$； 3. 双轨补全：自适应触发器激活单次交接，以当前 6 节点前缀为条件，筛选累积概率前 $80\%$ 的 3 个分支送入 Prefix-Difusco 运行 10 步 DDIM 去噪生成 3 个完整巡回回路；同时提取最优生成回路在当前步的转移点修正 RL 的贪婪动作，由 RL 自回归生成第 4 条混合路径； 4. 决策优选：从 4 条候选解中评估实际回路长度，选出全局总距离最短者（长度 7.76，与 Concorde 最优解对齐，Gap 仅 0.02%），全程仅耗时约 1.7 秒。

损失函数 / 训练策略¶

条件扩散模型 Prefix-Difusco 采用离散去噪网络，核心骨干为 12 层图神经网络（GNN）。为高效适应任意前缀长度条件，模型训练设计了关键策略： - 前缀掩码损失：在对真实巡回邻接矩阵 $x_0$ 施加 $T=1000$ 步余弦加噪后，仅对“非前缀边”（即至少有一个端点不在前缀内部的边）计算二元交叉熵（BCE）损失，强迫模型专注于未决子图的拓扑补全，避免对已知前缀重复优化； - 课程学习规划：TSP 训练划分为由易到难的多阶段课程。以 TSP-100 为例，第一阶段训练长前缀（$k \in [61, 99]$），使模型快速掌握短距离贪婪连接；随后逐步过渡到中长前缀（$k \in [30, 60]$）、全范围（$k \in [1, 99]$），最后专门强化短前缀（$k \in [1, 20]$ 及 $k \in [1, 10]$），确保在早期触发时依然具备强大的补全泛化能力；大规模 TSP-500/1000 则直接继承 TSP-100 权重进行迁移微调。

实验关键数据¶

主实验¶

论文在标准 2D 欧几里得 TSP（规模从 50 到 1000）、最大独立集（MIS）以及定向越野问题（OP）上开展了全面评测。在 TSP 上对比了精确求解器 Concorde、Gurobi，传统启发式 LKH-3，强 RL 基线（AM、POMO、LEHD）以及前沿扩散求解器（DIFUSCO、T2T、Prefix_Difusco）。

数据集	算法配置	求解类型	目标长度 (Len) ↓	最优差距 (Gap) ↓	推理耗时 (Time) ↓
TSP-50	Concorde	Exact	5.69	0.00%	-
	AM*	RL+G	5.80	1.76%	-
	POMO*	RL+G	5.73	0.64%	-
	DIFUSCO ($T_s=50$)	DM	5.71	0.45%	-
	Prefix_Difusco	DM	5.70	0.27%	-
	Prefix_Difusco (S=16)	DM	5.69	0.04%	-
	HyCO (POMO)	Hybrid	5.69	0.03%	-
TSP-100	Concorde	Exact	7.76	0.00%	-
	AM*	RL+G	8.12	4.53%	-
	POMO*	RL+G	7.84	1.07%	-
	DIFUSCO ($T_s=50$)	DM	7.85	1.21%	-
	T2T ($T_s=50, T_t=15$)	DM	7.77	0.20%	-
	Prefix_Difusco	DM	7.81	0.62%	-
	Prefix_Difusco (S=16)	DM	7.76	0.04%	-
	HyCO (POMO)	Hybrid	7.76	0.02%	-
TSP-500	Concorde	Exact	16.55	0.00%	37.66m
	POMO	RL+G	19.13	15.62%	0.49s
	LEHD	RL/SL+G	16.82	1.64%	1.82s
	DIFUSCO	SL+G	18.11	9.41%	5.70m
	Prefix_Difusco	SL+G	17.92	8.23%	0.14m
	Prefix_Difusco (S=16)	SL+S	17.31	4.58%	2.10m
	HyCO (POMO)	Hybrid	17.24	3.56%	1.20m
	HyCO (LEHD)	Hybrid	16.81	1.57%	0.35m
TSP-1000	Concorde	Exact	23.53	0.00%	6.65h
	POMO	RL+G	27.15	15.38%	0.94s
	LEHD	RL/SL+G	24.29	3.23%	3.84s
	DIFUSCO	SL+G	25.68	9.14%	11.5m
	Prefix_Difusco	SL+G	25.86	9.91%	0.35m
	Prefix_Difusco (S=16)	SL+S	24.96	6.07%	5.94m
	HyCO (POMO)	Hybrid	24.61	4.58%	2.43m
	HyCO (LEHD)	Hybrid	24.24	3.04%	0.36m

在最大独立集（MIS）图覆盖基准上，HyCO 同样展现出优异跨任务迁移能力：在 ER-700-800 图基准上，强化学习基线 LWD 的最优差距为 13.16%，条件扩散基线 prefix_Coexpander ($s=5$) 差距为 9.16%，而相同采样预算下 HyCO ($S_{\text{cand}}=5$) 的 Gap 骤降至 5.76%，显著领先更大算力消耗的 prefix_Coexpander ($s=64$)（差距 9.03%）。在定向越野问题 OP-200 上，HyCO 将 AM 的 13.05% 差距大幅压缩至 1.08%，超越了采样 64 次的纯扩散求解器（2.77%）。

消融实验¶

1. 核心触发机制消融（TSP-100 基准）¶

评测不同触发信号组合对交接时机、求解差距与触发率的影响：

触发机制配置	触发描述	最优差距 (Gap) ↓	平均耗时 (Time) ↓	平均触发步数	触发率 (Trig. Rate)
HyCO (Entropy)	仅依赖策略熵 ($H > H_{\text{th}}$)	0.05%	1.903s	2.36	99.8%
HyCO (KL)	仅依赖模型分歧 ($D_{\text{KL}} > D_{\text{th}}$)	0.09%	1.305s	1.35	97.0%
HyCO (Full Model)	双信号触发 (Entropy + KL)	0.02%	1.749s	0.52	100.0%

2. 自适应触发与预言机最优触发（Oracle Grid Search）对比¶

验证自适应轻量触发器是否能有效逼近全局网格搜索得到的实例级最佳固定触发步 $\tau_{\text{oracle}}$：

数据集	成本偏差 $\Delta_{\text{cost}}$ ↓	相对成本偏差 $\Delta_{\text{cost}} / f^*$ ↓	步数偏差 $\Delta_{\text{step}}$ ↓	归一化步数偏差 $\Delta_{\text{step}}^{\text{r}}$ ↓
TSP-100	0.0028	0.036%	1.48	1.48%
TSP-500	0.3424	2.057%	3.23	0.65%
SATLIB (MIS)	0.3812	0.089%	22.60	1.77%
ER 700-800 (MIS)	1.0460	2.330%	18.62	2.48%

关键发现¶

双信号触发的不可或缺性：单独依靠策略熵（Gap 0.05%）或单一KL分歧（Gap 0.09%）均显著弱于双信号联合触发（Gap 0.02%）。策略熵能有效检出RL的“犹豫不决”，而KL散度能精准捕捉RL“过于自信却违背全局结构”的致命陷阱，两者在轨迹级形成互补保护。
自适应触发逼近预言机水平：跨多项任务的预言机检验表明，自适应触发决策与最优步数的归一化距离均低于 2.5%，相对成本偏差在 TSP-100 与 SATLIB 上仅为 0.036% 和 0.089%，有力印证了轻量自适应探测能够作为期望最优交接点 $\tau^*$ 的高精度实用代理。
样本利用率超越暴力过采样：在 TSP-50/100 及 MIS 上，HyCO 仅需 $S=4 \sim 5$ 次前缀引导采样，即可击败纯扩散模型 16 次乃至 64 次独立采样的暴力解。这表明找准低遗憾子空间的切入时机远比盲目增加后验采样数更具决定性意义。

亮点与洞察¶

从理论遗憾均衡到实用工程落地的闭环：论文不仅在理论上严谨证明了超线性视距累积与次线性子空间遗憾必然导致唯一的最优切换点，还通过将单步扩散先验玻尔兹曼化转化为受限Top-$M$ KL散度，构建了极低开销的在线触发器。
双轨容错生成的工业级稳健性：将扩散模型输出既作为全量端到端独立补全路径，又作为即时动作矫正器植入RL贪婪回环，彻底规避了单一生成模型可能因概率退化或约束冲突导致求解崩溃的问题。
高度通用的即插即用特性：无需对RL骨干网络做重构训练，无论配合基础的AM、对称增强的POMO，还是大规模分治的LEHD，HyCO均能直接作为推理期包装器带来确定性提升。

局限与展望¶

理论假设的平滑性约束：现有理论证明建立在目标连续松弛的Lipschitz连续性及特定误差扩展阶数假设之上，面对非线性强约束（如严格时间窗或动态运力装载约束）时，遗憾函数的单调性与收敛界可能需要重构。
扩散能量探测的计算冗余：虽然单步探测避免了完整扩散轨迹采样，但在长序列每一步评估Top-$M$能量仍需前向调用扩散特征提取器，在大规模实例初期带来了一定常数开销。
未来方向：可进一步探索自适应步长探测（例如跳步监测或轻量级守门员网络）以降低单步检测负担，并将单次交接机制推广到多轮反复握手（RL与DM多阶段循环协作）的通用混合求解范式中。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次从边际遗憾理论切入严格论证序列RL与扩散模型的互补交接机制，立意极其深刻。
实验充分度: ⭐⭐⭐⭐⭐ 覆盖TSP、MIS、OP三大经典CO问题及多个尺度，并配套完备的预言机网格搜索与消融。
写作质量: ⭐⭐⭐⭐⭐ 理论证明完整严密，方法设计图文呼应，问题意识与解决链路高度清晰。
价值: ⭐⭐⭐⭐⭐ 为解决组合优化中神经求解器的泛化与误差累积难题开辟了极具前景的混合范式。

触发机制配置	触发描述	最优差距 (Gap) ↓	平均耗时 (Time) ↓	平均触发步数	触发率 (Trig. Rate)
HyCO (Entropy)	仅依赖策略熵 (\(H > H_{\text{th}}\))	0.05%	1.903s	2.36	99.8%
HyCO (KL)	仅依赖模型分歧 (\(D_{\text{KL}} > D_{\text{th}}\))	0.09%	1.305s	1.35	97.0%
HyCO (Full Model)	双信号触发 (Entropy + KL)	0.02%	1.749s	0.52	100.0%