组合优化与调度

路径规划、芯片布局、数据中心调度、编译器优化等问题用 RL 学习启发式或直接构造解。本章讲指针网络/注意力模型构造解的范式、与传统求解器的结合方式，以及 AlphaDev、芯片布局等案例的实际贡献与争议。

范式：用 RL 学构造解

组合优化问题（TSP、车间调度、装箱）的 RL 化范式：把"构造解"当作序列决策——

• 状态：已构造的部分解；动作：下一步选哪个节点/分配；奖励：解的质量（完工即给）；
• 构造式（constructive）：从空解逐步添加（指针网络 Pointer Networks、注意力模型 Kool et al. 2019 的 AM）——每步用注意力对候选打分，训练用 REINFORCE/POMO 类的多种子策略梯度；
• 改进式（improvement）：从一个初始解出发，动作用"局部交换/移动"，RL 学改进策略（学启发式而非构造解）。

构造式的优势是一次前向出一个解；改进式的优势是可以借传统启发式的初始解。

案例：贡献与争议

芯片布局（chip placement）：把宏单元放到芯片上，RL（策略梯度 + 图表示）端到端布局。Google 的 AlphaChip（Mirhoseini et al., 2021, Nature）声称数小时内达到人类专家数周的水平；争议在于基准与比较方法的公平性——后续复现（Cheng et al.）指出与强基线（模拟退火 + 人工流程）的比较不充分，预训练数据与计算成本也常被低估。这个案例的价值不在结论，而在它暴露了"RL 论文如何被评估"的问题（→ 评估协议与可复现性）。

AlphaDev（Mankowitz et al., 2023, Nature）：用 RL（AlphaZero 式学习 + 搜索）发现更快的汇编级排序算法，部分例程已进 LLVM。贡献真实（有被采用的开源补丁），但适用范围窄（底层例程、可精确验证的奖励）——它是"RL + 可验证奖励"在系统层的成功案例（与 RLVR 的关系见 → GRPO 与可验证奖励）。

数据中心调度：DeepMind 的冷却优化（降低约 40% 冷却能耗）是早期落地案例——设定是"可测量、可安全回滚"的控制系统，RL 作为改进控制器而非替代。

编译器优化 / 调度：搜索空间巨大、奖励可测量（延迟）的任务，RL 与搜索结合（AlphaDev、MLGO）。

RL 的实际定位：改进器而非替代品

跨案例的共同规律：RL 通常作为求解器的改进器而非替代品——

• 传统求解器（CP-SAT、Gurobi、模拟退火）在问题规模、最优性保证上仍是基座；
• RL 的位置：学启发式（传统方法要人工设计的部分）、加速搜索（价值网络引导剪枝）、处理不可精确建模的目标（真实延迟、人工布局的后续指标）；
• 纯 RL 端到端替代求解器，在精度要求高的场景（最优性保证）尚未成立。

泛化：核心难点

组合优化 RL 的核心难点是泛化到更大规模实例：在 100 节点 TSP 上训练的模型，到 1000 节点上性能崩塌（分布外）——这与 RL 泛化的普遍规律一致（→ 泛化、过拟合与 Sim-to-Real）。修复：按规模课程训练、与求解器混合（大规模用传统方法）、改进式（局部移动对规模更鲁棒）。

本章要点

• RL 通常作为求解器的改进器而非替代品
• 泛化到更大规模实例是核心难点
• 基准与比较方法的争议