Teacher-Aware Evolution of Heuristic Programs from Learned Optimization Policies¶

会议: NeurIPS 2026
arXiv: 2605.10634
OpenReview: https://openreview.net/forum?id=dXWka7F0Ie
论文: https://arxiv.org/abs/2605.10634
领域: 优化/理论
关键词: 组合优化, 启发式程序进化, 大语言模型, 神经策略教师, 局部行为对齐

一句话总结¶

将预训练黑盒神经优化策略作为行为教师，在候选启发式程序访问的状态上查询动作偏好形成局部行为反馈，通过大模型反思与帕累托进化搜索出无需神经网络推理的高性能静态可执行程序。

研究背景与动机¶

在作业车间调度（JSSP）、旅行商问题（TSP）、车辆路径规划（CVRP）及图划分（MaxCut）等序贯组合优化问题中，紧凑的手工启发式规则因计算开销极低、可解释性强且易于无依赖部署而长期占据工业界核心地位。然而，设计顶尖启发式往往高度依赖领域专家的试错积累，泛化至新问题类时需要耗费大量人力调校。基于大语言模型（LLM）的自动启发式设计（AHD）近期取得了显著进展，如 FunSearch、EoH、ReEvo 等框架通过生成代码并在迭代进化中根据终点目标值或种群统计信息反思修正。然而，现有 AHD 的进化指导信号完全依赖演化循环内部的延迟标量反馈（如完整求解后的目标值），无法在求解轨迹的中间决策步骤提供细粒度归因。

与此同时，深度强化学习与神经组合优化（NCO）已训练出强大的端到端神经策略，例如调度中的 L2D、路径规划中的 LEHD 以及图优化中的 ECO-DQN。尽管这些模型可以直接作为求解器，但其神经网络前向推理耗时显著、难以向领域工程师解释且在跨规模部署时受显存约束。更关键的是，研究者通常只把它们当成终点解求解器，却忽视了它们蕴含的丰富动作级行为先验：给定任意可行状态与候选动作集，训练好的神经策略能提供明确的动作偏好排序，这恰好是全局延迟目标值所欠缺的即时指导。

如果将神经策略视为单纯的蒸馏或模仿目标，搜索出的规则不仅容易受限于教师自身的归纳偏差与次优决策，还会牺牲最终任务指标。核心 idea：将预训练黑盒神经优化策略转变为查询式行为教师，在候选程序自身诱导的在策略（on-policy）状态下查询教师的局部动作偏好，提取决策级对齐信号与分歧案例指导 LLM 结构重写与参数校准，并依据任务真实目标而非教师保真度挑选最终的无神经开销静态启发式程序。

方法详解¶

针对序贯组合优化问题，候选启发式程序 $h$ 定义了从当前状态 $s_t$ 及可行候选动作集 $\mathcal{A}(s_t)$ 中选择动作的确定性规则 $a_h(s_t) = h(s_t, \mathcal{A}(s_t))$，例如通过评分函数 $u_h(s_t, a)$ 选出得分最大者。求解目标是在目标分布上最小化延迟终点目标 $\mathbb{E}_{x \sim \mathcal{D}}[F(h; x)]$。本文提出的教师感知进化框架并不强求程序复现教师的所有轨迹，而是在程序自身运行探索的路径上向黑盒教师问询建议，构建反思与进化机制。

整体框架¶

整体框架由评估与状态采样、教师局部诊断、分析器引导的反思演化、以及双目标种群管理四大阶段构成回环。在每一代进化中，当前种群中的候选程序在任务设计实例上执行完整展开（rollout），记录终点任务目标 $F(h)$ 并采样轨迹中访问到的在策略状态集合 $\mathcal{S}_h$。随后，系统将这些在策略状态批量输入给黑盒神经策略教师 $T$，通过对比程序动作与教师偏好提取 Top-1 对齐率及分歧案例。分析器 LLM 据此生成指导摘要，驱动三种专有演化算子生成下一代子代程序。新生成的程序经多目标帕累托保留筛选后进入下一轮迭代。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["候选程序种群 𝒫<br/>Python 启发式源码"] --> B["在策略状态采样与评测<br/>展开轨迹收集 S_h 与目标 F(h)"]
    B --> C["黑盒神经策略查询<br/>在状态 S_h 查询教师动作 a_T"]
    C --> D["在策略教师对齐诊断<br/>计算 Align(h)、相对价值与分歧案例"]
    D --> E["分析器 LLM 反思简报<br/>提炼决策差异并指派演化模式"]
    E --> F["教师感知演化算子生成<br/>结构重写 / 参数校准 / 机制级融合"]
    F --> G["目标-行为帕累托种群管理<br/>多目标非支配排序 F(h) 与 Align(h)"]
    G -->|下一代迭代| A
    G -->|搜索结束| H["终点选择：任务目标最优静态程序<br/>零神经网络推理部署"]

关键设计¶

框架围绕如何从神经黑盒中提取稳定的决策先验、如何将行为反馈转化为程序代码层面的编辑信号、以及如何避免盲目盲从教师三大核心矛盾展开。

1. 在策略教师对齐诊断：在候选程序自身状态流上构建鲁棒的无量纲行为度量
传统策略蒸馏通常迫使代理在专家轨迹或固定离线数据集上拟合，但这会导致分布偏移——一旦被提取的程序偏离教师轨迹，就无法得知在自身面对的新状态下教师会如何决策。本文采用在策略状态采样，对每个候选程序 $h$ 在解题过程中实际访问的状态集合 $\mathcal{S}_h$ 进行教师查询。为了消除不同神经网络教师（如基于 Q 值的 ECO-DQN 与基于策略概率的 LEHD/L2D）在评分量纲和标定尺度上的差异，框架核心采用 Top-1 动作一致率作为主对齐信号： $$\mathrm{Align}(h) = \frac{1}{|\mathcal{S}_h|} \sum_{s \in \mathcal{S}_h} \mathbf{1}[a_h(s) = a_T(s)]$$ 当教师能直接提供连续动作分值 $Q_T(s, a)$ 时，进一步在各状态内部执行最大最小范围归一化得到 $\widetilde{Q}_T(s, a)$，并计算归一化均值 $\mathrm{Value}(h)$ 与动作百分位排名作为辅助诊断特征。这一设计保证了跨任务跨教师的尺度一致性，在动作集规模波动时仍能稳定反映决策重合度。

2. 教师感知反思与三模态程序演化：将局部行为分歧映射为针对性代码变异
单纯将对齐分数作为黑盒奖励无法指导代码的因果修改。本文引入轻量级任务接口适配器（定义函数签名、输入特征含义与诊断字段名，绝不提供预制专家规则），由专门的分析器 LLM 在每代调用一次，对比程序动作与教师首选动作的典型分歧案例（Representative Disagreement Cases），形成精简的修订简报并派发给三种互补的演化操作： - 结构重写（Structural Rewrite）：当分歧案例揭示出候选程序在特定调度或选点阶段存在系统性盲区时（例如早期忽视瓶颈机器负荷或未考虑返回场站边界），修改程序的高层决策骨干，重组特征组合结构； - 参数校准（Parameter Calibration）：当程序选择的候选动作与教师偏好接近但由于阈值或权重失调导致选错时，冻结逻辑骨架，专门微调内部的门控因子、指数衰减参数、松弛惩罚及平局决策偏置； - 机制级融合（Mechanism-level Fusion）：在同一决策层级交叉组合来自“任务目标最优父代池”的优异模块与来自“对齐度最优父代池”的高保真模块，使得子代兼备全局目标收益与教师局部的精细决策直觉。

3. 目标-行为双目标帕累托种群管理：防止次优教师主导与行为塌缩
黑盒神经策略在复杂大组合问题上本身往往不是全局最优解，若盲目追求对齐度会导致搜索迅速收敛至教师的次优局部极值。为此，系统维护双目标向量 $z(h) = (F(h), -\mathrm{Align}(h))$，以最小化形式进行 Pareto 非支配排序。该机制使得在搜索过程中，既有能超越教师全局性能的探索型程序得以存活，也有与教师行为紧密吻合的保守型程序得以提供稳定积木。当边界前沿超出种群容量上限时，采用以任务目标占主导地位的排名加权分 $S(h) = r_F(h) + \lambda r_A(h)$（其中 $\lambda$ 较小）进行截断淘汰。最终搜索结束输出时，完全只按真实任务目标 $F(h)$ 挑选最优程序，彻底解耦了探索期的教师引导与发布期的实用指标。

损失函数 / 训练策略¶

作为程序搜索算法，本方法无需反向传播梯度训练，核心演化控制参数如下： - 种群与代数设置：种群大小 $N = 10$，演化代数 $G = 5$ 代，每代生成 5 个子代程序，搜索预算极其紧凑。每代仅调用 1 次分析器 LLM，总 LLM 请求预算受限且不超同类基线。 - 父代采样概率：采用截断排名加权采样，给定排名标准 $c$，对 Top-$K$ 候选池以单调递减函数 $w(r_c(h))$ 分配采样概率 $p_c(h) \propto w(r_c(h))$。单亲算子从目标优先池采样，双亲融合算子分别从目标池与对齐池各抽一个父代。 - 底层模型配置：LLM 驱动器统一采用 GPT-5.4，解码温度与提示规范严格一致；外部神经教师策略加载各领域的官方预训练检查点（JSSP: Offline-L2D; TSP/CVRP: LEHD; MaxCut: ECO-DQN）。

实验关键数据¶

主实验¶

在四类典型序贯决策任务上全面评测，涵盖 JSSP（随机与 Taillard 基准）、TSP（TSP50/200/TSPLIB70）、CVRP（CVRP50/200/VRPLIB192）和 MaxCut（BA/ER/Physics 图），与纯性能驱动的 LLM 启发式搜索（EoH, ReEvo）、经典运筹启发式以及官方神经策略全面对比。

任务 / 数据集	评测指标	本文 (Ours)	EoH (ICML24)	ReEvo (NeurIPS24)	神经策略基准	经典运筹/SOTA (LKH等)
JSSP 10×10	Makespan ↓ / 时延(s) ↓	915.87 / 1.81	930.10 / 1.44	916.71 / 1.51	976.52 / 12.51 (Offline-LD)	955.38 / 2.85 (FDD-MWKR)
JSSP 15×15	Makespan ↓ / 时延(s) ↓	1379.13 / 6.06	1394.03 / 6.75	1409.71 / 5.78	1499.30 / 114.26 (Offline-LD)	1463.33 / 9.87 (FDD-MWKR)
JSSP 20×20	Makespan ↓ / 时延(s) ↓	1812.15 / 18.59	1866.92 / 20.80	1867.06 / 18.41	1971.33 / 228.69 (Offline-LD)	1946.20 / 27.37 (FDD-MWKR)
JSSP Taillard 30×20	Makespan ↓ / 时延(s) ↓	2411.40 / 6.40	2446.10 / 6.35	2454.20 / 6.32	2607.00 / 41.95 (Offline-LD)	2565.70 / 7.52 (FDD-MWKR)
TSP50 (In-Domain)	路径长度 ↓ / 时延(s) ↓	6.387 / 0.28	6.912 / 0.13	7.014 / 0.05	5.739 / 0.10 (LEHD)	5.709 / 1.05 (LKH)
TSP200 (OOD)	路径长度 ↓ / 时延(s) ↓	12.250 / 4.49	13.520 / 0.77	13.376 / 0.14	10.796 / 2.97 (LEHD)	10.704 / 11.75 (LKH)
TSPLIB70 (OOD)	路径长度 ↓ / 时延(s) ↓	86544.10 / 464.92	94535.89 / 505.64	90623.59 / 6.66	78517.23 / 388.81 (LEHD)	73156.01 / >1h (LKH)
CVRP50 (In-Domain)	路径长度 ↓ / 时延(s) ↓	9.671 / 0.16	9.689 / 1.09	10.056 / 0.45	8.180 / 0.11 (LEHD)	7.828 / >1h (LKH)
CVRP200 (OOD)	路径长度 ↓ / 时延(s) ↓	25.371 / 7.12	26.250 / 59.20	27.270 / 22.89	20.832 / 2.65 (LEHD)	20.34 / >1h (LKH)
VRPLIB192 (OOD)	路径长度 ↓ / 时延(s) ↓	37780.72 / 282.31	38448.92 / 1466.31	39848.49 / 536.32	39120.68 / 234.03 (LEHD)	33281.32 / >1h (LKH)
MaxCut BA200w	割权重 ↑ / 时延(s) ↓	189.85 / 43.41	189.76 / 16.40	181.96 / 20.80	184.32 / 126.19 (ECO-DQN)	—
MaxCut ER800w (OOD)	割权重 ↑ / 时延(s) ↓	1881.80 / 43.90	1863.60 / 13.32	1813.00 / 37.88	1839.00 / 58.27 (ECO-DQN)	—

消融实验¶

在 JSSP（20×20 In-domain 与 Taillard 20×20 OOD）和 TSP（TSP50 In-domain 与 TSP200 OOD）上系统验证教师对齐反馈、分析器简报、专有演化算子和种群更新策略的贡献（指标均为越低越好）：

实验配置	JSSP In-Domain (Makespan)	JSSP OOD (Makespan)	TSP In-Domain (Tour Length)	TSP OOD (Tour Length)	说明
完整模型 (Full)	1812.15	1916.30	6.387	12.250	完整教师感知帕累托进化机制
纯性能驱动 (Performance-only)	1899.79 (+87.64)	1967.20 (+50.90)	7.050 (+0.663)	13.900 (+1.650)	剥离全部教师反馈，退化为传统 AHD
无分析器简报 (w/o analyzer)	1871.77 (+59.62)	1964.00 (+47.70)	7.152 (+0.765)	14.022 (+1.771)	移除分析器 LLM 提炼，直接传粗粒度数据
无教师演化算子 (w/o guided ops)	1852.39 (+40.24)	1966.80 (+50.50)	7.185 (+0.797)	13.497 (+1.247)	禁用专有算子，仅使用通用变异与交叉
无帕累托更新 (w/o Pareto)	1816.24 (+4.09)	1934.90 (+18.60)	6.986 (+0.598)	13.694 (+1.444)	仅凭单一目标保留，失去行为多样性维护
最大对齐选择 (Max-align selection)	1845.26 (+33.11)	1909.10 (-7.20)	6.395 (+0.008)	12.332 (+0.082)	最终挑选程序按教师对齐度而非任务目标
移除结构重写 (w/o structural, s)	1937.92 (+125.77)	2011.50 (+95.20)	7.243 (+0.856)	14.202 (+1.952)	无法依据分歧重构决策骨架（掉点最严重）
移除参数校准 (w/o calibration, p)	1851.72 (+39.57)	1936.80 (+20.50)	7.360 (+0.972)	14.204 (+1.954)	无法微调阈值与权重门控（TSP 极为敏感）
移除机制融合 (w/o fusion, m)	1913.72 (+101.57)	2002.30 (+86.00)	6.793 (+0.406)	13.715 (+1.465)	无法杂交目标优异与对齐优异的代码片段

关键发现¶

局部行为先验显著加速收敛：在搜索动态分析中（Figure 2），本文方法在仅第 2 代就达到了 EoH 与 ReEvo 在第 5 代甚至更多轮次无法达到的求解质量，证明教师局部决策指引大幅缩减了盲目试错空间。
结构重写（s）是性能跃升的核心支柱：在算子消融中，剔除结构重写导致 JSSP makespan 恶化 +125.77，TSP 长度恶化 +0.856。当程序逻辑出现系统性偏差时，仅调参无法弥合性能断层。
不能把教师保真度作为最终裁决依据：在 Max-align selection 变体中，最终选出的程序虽然与教师行为更相似，但在 TSP 域与大部分 OOD 场景下泛化指标反而劣于以实际目标 $F(h)$ 挑选出的程序，证实了“借教师之力拓宽搜索视野，但以真实指标作为唯一裁判”的必要性。
运行效率远超神经教师：在 JSSP 20×20 上，生成的纯 Python 程序运行仅需 18.59 秒，而 Offline-LD 神经策略需要 228.69 秒（提速 12 倍以上）；在 VRPLIB192 上耗时 282 秒，而 LKH 求解器需 1 小时以上。

亮点与洞察¶

将预训练神经网络重塑为“黑盒探针”而非“终身部署单元”：打破了过去 NCO 必须作为在线求解器或单纯进行模型蒸馏的固有思维，将其作为离线程序进化循环中的局部反馈发生器，既榨取了深度模型的行为知识，又摆脱了其实时推理算力与黑盒不可解释的包袱。
在策略（On-policy）状态查询化解分布偏移：不依赖离线轨迹集，而是在候选程序自己探索出的状态分布上询问教师动作偏好，使反思简报能够针对程序“实际容易踩坑之处”对症下药。
跨领域通用的统一动作抽象：将 JSSP、TSP、CVRP、MaxCut 统一抽象为状态感知的可行候选动作打分与选择，使得相同的分析器接口与三模态变异机制可以无缝横跨调度、路径与图划分三大运筹领域。

局限与展望¶

依赖预先存在且可对齐的高质量神经策略：如果目标组合优化问题缺乏成熟的强化学习/NCO 教师模型，或者神经策略的动作空间抽象与代码程序难以建立单射映射，该框架将无法直接发挥作用。
需要轻量级接口适配器的工程搭建：尽管不注入启发式偏置，仍需人工编写定义程序签名与状态特征的适配提示词，未来可探索由 LLM 自动化根据环境环境 API 自适应生成适配层。
演化早期的静态采样成本：每代需对候选程序的所有状态批量查询神经网络，当问题规模很大且种群膨胀时，离线前向批量推理时间会成为主要搜索瓶颈，引入自适应或早退式查询机制将是潜在改进方向。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次提出将深度神经组合优化策略作为 LLM 启发式程序进化的在策略行为教师，架构设计巧妙连贯。
实验充分度: ⭐⭐⭐⭐⭐ 涵盖调度、路径与图优化四大经典基准，提供完备的 In-domain、跨规模 OOD、全面消融与动态分析。
写作质量: ⭐⭐⭐⭐⭐ 问题建模清晰，方法剖析深入透彻，数学与符号规范，图表详实自洽。
价值: ⭐⭐⭐⭐⭐ 成功打通了深度强化学习与符号化算法自动设计之间的壁垒，为低算力工业运筹部署提供了高质量落地范式。