AHD Agent：用于自动启发式设计的代理强化学习

# AHD Agent：用于自动启发式设计（AHD）的智能体强化学习

来源：https://arxiv.org/html/2605.08756

作者：Haoze Lv$^{1,2}$, Ning Lu$^{1,3,\dagger}$, Ziang Zhou$^1$, Shengcai Liu$^{1,2}$

1. 南方科技大学计算机科学与工程系，广东省类脑智能计算重点实验室
2. 中关村学院
3. 香港科技大学

项目主页：https://github.com/Antoniano1963/AHD-Agent

###### 摘要

自动启发式设计（AHD）已成为解决 NP 难组合优化问题（COPs）的一种有前景的范式。最近的研究表明，当大型语言模型（LLMs）被整合到精心设计的框架中（即 LLM-AHD）时，能够自主发现高性能的启发式算法。然而，现有的 LLM-AHD 框架通常将 LLM 视为固定工作流中的被动生成器，模型仅从人工设计的有限上下文中生成启发式算法。这种上下文可能无法捕捉状态依赖的信息（例如，特定的失败模式），导致低效的试错探索。为了克服这些局限性，我们提出了 **AHD Agent**，这是一种新颖的工具集成、多轮交互框架，赋予 LLM 主动决策的能力，即决定是生成启发式算法，还是调用工具从求解环境中检索有针对性的证据。为了有效地训练这种动态决策智能体，我们引入了一种智能体强化学习（RL）系统，该系统利用一种新颖的环境合成流水线，优化紧凑模型的可泛化 AHD 能力。在八个不同领域（包括四个保留任务）上的实验表明，我们的 4B 参数智能体使用比现有最先进基线小得多的模型，即可达到或超越其性能，且所需的评估次数显著更少。模型和推理扩展分析进一步揭示，AHD Agent 为实现真正自主的启发式设计提供了一条有效途径。

## 1 引言

NP 难组合优化问题（COPs）是许多实际系统（如交通、规划和决策）的基础\[30\], \[35\]。高效地解决这些问题严重依赖于精心设计的启发式算法\[7\]。传统上，启发式设计是一个高度手动且耗时的过程，需要专家分析求解过程并进行大量的试错。为了缓解这些局限性，自动启发式设计（AHD）作为一种有前景的启发式生成范式应运而生\[2\]。然而，传统的 AHD 方法（如遗传编程 GP）仍然严重依赖专家设计的组件\[22\], \[31\]。

最近，大型语言模型（LLMs）被引入 AHD，作为进化计算（EC）框架中的启发式生成器\[36\], \[33\]。在这些框架中，LLM 根据预定义规则选择的候选者生成新的启发式算法。生成的启发式算法随后进行评估，形成反馈-生成循环。

**图 1：传统基于 LLM 的 AHD 与我们的 AHD Agent 对比。** 传统 AHD 将 LLM 置于固定循环中。AHD Agent 使 LLM 能够通过主动调用工具、生成候选者和执行评估来设计启发式算法。

然而，现有的基于 LLM 的 AHD 框架（例如 EoH\[26\]，ReEvo\[59\]）仍面临关键局限性。如图 1 所示，它们将 LLM 视为固定工作流中的被动启发式生成器。这些工作流依赖于人工设计且有限的上下文（例如，基于顶级启发式的交叉\[26\]），这可能无法捕捉特定设计步骤所需的信息，如先前启发式算法的失败模式。因此，模型无法识别信息差距或检索有针对性的证据，而是依赖低效的试错生成。

我们在图 2 中的初步研究进一步表明，在这些固定工作流中简单地向 LLM 提供所有可用信息（工具）带来的增益有限，甚至可能损害性能，这表明关键挑战不仅仅是信息的可用性，而是缺乏获取和使用相关信息的状态依赖机制。此外，现有框架通常使用未针对 AHD 特别对齐的通用 LLM，导致昂贵的试错搜索。

**图 2：工具对 AHD Agent 的帮助大于固定工作流的基于 LLM 的 AHD。** 报告的是在 DeepSeek-V4-Flash\[6\]下的平均验证差距。对于 EoH 和 ReEvo，在每次 LLM 生成步骤中调用所有工具。详细信息见附录 D.6。

为了克服这些局限性，我们提出了 **AHD Agent**，这是首个用于基于 LLM 的 AHD 的工具集成多轮框架。与遵循固定流水线不同，AHD Agent 使 LLM 能够主动决定是生成启发式算法，还是使用工具检索相关信息。这使得模型能够根据中间反馈（如评估结果和工具输出）调整其设计策略。基于 AHD Agent，我们进一步开发了一种智能体强化学习（RL）系统，通过 GRPO\[53\]优化基础模型，以提高其可泛化的 AHD 能力。我们引入了一种 AHD RL 环境合成流水线，通过变化评估实例、求解器骨干和初始启发式算法来构建多样化的训练环境。经过 RL 训练的智能体在显著减少启发式评估次数的情况下，匹配或超越了传统的基于 LLM 的 AHD 框架。模型和推理扩展进一步揭示了我们框架的潜力，表明这是一条基于 LLM 的 AHD 的有效且高效的路径。

我们的贡献总结如下：

*   我们引入了 **AHD Agent**，这是首个用于基于 LLM 的 AHD 的工具集成多轮框架，它使启发式生成能够进行主动的、状态依赖的工具使用，而不是遵循具有静态上下文的固定工作流。
*   我们开发了一个具有 AHD 环境合成流水线和跨域联合训练的智能体 RL 系统，显著提高了模型在不同设置下的可泛化 AHD 能力。
*   我们在涵盖不同问题领域、实例规模和求解器骨干的八个评估设置中进行了广泛实验。我们的 4B 参数智能体优于使用更大模型的基线，并表现出强大的泛化能力，确立了 AHD Agent 作为传统方法的具有竞争力且高效的替代方案。

## 2 相关工作

**基于 LLM 的 AHD。** 最近的基于 LLM 的 AHD 方法在反馈驱动搜索循环中使用 LLM 作为代码生成器，其中候选启发式算法被生成、评估和精炼。FunSearch\[36\]和 EoH\[26\]确立了这一范式，后续工作通过反射和树搜索等固定工作流对其进行了扩展\[59\], \[64\], \[25\], \[5\], \[42\]。其他扩展将 LLM-AHD 应用于路由、调度、MILP、SAT 及相关优化问题\[13\], \[24\], \[62\], \[4\], \[61\]。尽管结果令人鼓舞，但大多数方法仍然由外部规定搜索过程，使 LLM 主要充当候选生成器。

**AHD 的强化学习。** 最近的工作开始使用 RL 来增强基于 LLM 的启发式生成\[48\], \[65\], \[15\]。例如，CALM 在固定进化搜索工作流中共进化 LLM 和启发式种群。这些方法表明 RL 反馈可以改善启发式搜索，但它们要么仍然局限于固定工作流，要么专门针对特定求解器和问题家族。相比之下，AHD Agent 从多领域 RL 训练中学习了可迁移的启发式设计策略。学到的策略控制多轮设计过程本身：它决定何时评估、调用哪些工具以及如何根据反馈修订候选启发式算法。我们的实验表明，该策略可以泛化到未见过的问題家族，并跨评估协议迁移。

**LLM 智能体与强化学习。** LLM 越来越多地被用作优化\[17\], \[28\]、程序生成\[60\]、智能设备操作\[63\], \[14\]、交互式游戏\[51\]和机器人控制\[66\]等领域的自主决策智能体。早期研究主要通过 ReAct\[57\]和 Reflexion\[43\]等提示策略利用冻结的预训练模型，通常辅以记忆、检索和外部工具\[52\], \[49\], \[29\], \[38\], \[56\], \[18\]。最近的工作转向通过监督微调或强化学习（RL）适应模型参数\[19\], \[1\], \[9\], \[55\], \[11\]，使智能体能够通过与环境直接交互来改进，而不仅仅依赖手工设计的工作流。代表性的 RL 方法包括 PPO\[39\]、MCTS\[44\]、RLOO\[21\]和 GRPO\[53\]。

## 3 方法

我们提出了 **AHD Agent**，一种用于基于 LLM 的 AHD 的工具集成、多轮框架。与固定工作流的 LLM-AHD 方法不同，AHD Agent 将 LLM 视为多轮设计过程中的决策智能体。我们首先对问题进行了形式化描述，并介绍了 AHD Agent 的交互协议和工具集。然后，我们展示了智能体 RL 训练过程，包括 AHD 环境合成流水线和跨域训练。

### 3.1 AHD Agent 框架

#### 3.1.1 形式化

令 $\mathcal{I}$ 表示目标优化问题的实例空间，令 $\mathcal{D}_{\text{design}} \subset \mathcal{I}$ 为在一次启发式设计 episode 中可见的设计集。AHD 的目标是构建一个启发式算法 $h$，以可执行代码形式表示。评估器在指定的求解器设置下在 $\mathcal{D}_{\text{design}}$ 上运行 $h$，并返回标量分数 $\operatorname{Score}(h; \mathcal{D}_{\text{design}})$ 以及执行反馈。我们将 $\operatorname{Score}$ 归一化，使得较大的值总是更好。

在 AHD Agent 框架中，AHD 过程被形式化为一个有限时域马尔可夫决策过程（MDP）$\mathcal{M}=(\mathcal{S}, \mathcal{A}, P, R)$。这里 $\mathcal{S}$ 表示状态空间，其中每个状态 $s_t$ 可以是观测序列或交互历史；$\mathcal{A}$ 是令牌级动作空间，涵盖启发式生成/评估、工具调用和最终响应；$P$ 和 $R$ 分别表示转移动态和奖励生成过程。初始状态 $s_0$ 包含问题描述和种子启发式算法 $h_0$。在每个时间步 $t$，智能体策略 $\pi_\theta$ 根据当前状态 $s_t$ 和交互历史 $\tau$ 生成动作。

#### B.3.3 提示中使用的信息

表 6 总结了插入到 `{problem.description}` 及相关占位符中的领域特定信息。这些条目有意保持简洁，因为本工作的贡献在于智能体交互策略，而非领域特定的提示工程。

表 6：提示中使用的每个问题的信息。相同的系统和用户提示模板跨领域重用；仅实例化这些领域特定字段。

## 附录 C RL 训练细节

本节提供 RL 训练过程的更多细节，包括训练数据统计、训练配置和训练曲线。

### C.1 GRPO

我们使用 GRPO 算法\[41\]优化 AHD Agent。令 $\pi_\theta$ 为可训练的 LLM，$\pi_{\text{ref}}$ 为冻结的参考 LLM，$q$ 为输入提示。对于每个 $q$，GRPO 采样一组 $G$ 个 rollout $\{o_i\}_{i=1}^G \sim \pi_{\theta_{\text{old}}}(\cdot \mid q)$，获得奖励 $r_i$，并计算归一化优势 $\hat{A}_i = (r_i - \mathrm{mean}(\{r_j\})) / (\mathrm{std}(\{r_j\}) + \delta)$。LLM 通过以下裁剪目标更新：

$$
\begin{aligned}
\mathcal{J}_{\mathrm{GRPO}}(\theta) &= \mathbb{E}_{q, \{o_i\}} \left[ \frac{1}{G} \sum_{i=1}^{G} \frac{1}{\|o_i\|} \sum_{t=1}^{\|o_i\|} \left( \min \left( \rho_{i,t} \hat{A}_i, \mathrm{clip} \left( \rho_{i,t}, 1-\epsilon_{\mathrm{clip}}, 1+\epsilon_{\mathrm{clip}} \right) \hat{A}_i \right) \right. \right. \\
&\quad \left. \left. - \beta D_{\mathrm{KL}} \left( \pi_\theta \| \pi_{\mathrm{ref}} \right) \right) \right],
\end{aligned}
$$

其中 $\rho_{i,t}(\theta) = \frac{\pi_\theta(o_{i,t} \mid q, o