GAE: 通过强化优化进行科学发现的图增强进化

# 图增强进化：基于强化优化的科学发现  
来源：https://arxiv.org/html/2607.10127 ###### 摘要  

由大型语言模型（LLM）引导的进化程序搜索已成为自动化科学发现的一种强大范式。然而，当前方法本质上受到三个瓶颈的制约：结构盲目的父代选择、稀疏的整体程序评估奖励，以及在搜索过程中无法自适应的静态变异算子。我们提出了 **GAE**（图增强进化），这是一个通过紧密耦合的三支柱架构解决这些局限的框架。首先，一个**关系图神经网络（GNN）** 将程序解析为类型化计算图，生成结构感知的嵌入。其次，一个**RL优化的元控制器**利用这些嵌入替代盲目的进化采样，采用有导向的策略，根据奖励历史动态选择最优父代和变异方向。第三，一个**在线 GRPO 微调循环**，在测试时使用组归一化评估奖励持续更新 LLM 变异算子，直接将模型的生成分布与高适应度的结构编辑对齐。我们在一个具有挑战性的科学发现任务——复杂非线性振荡器系统的符号回归——上评估 GAE。通过将随机搜索转化为有导向、自改进的轨迹，GAE 高效地发现了封闭形式的物理方程，持续匹配或超越静态 LLM 驱动的基线，并实现了最先进的分布外性能。  

机器学习，ICML  

## 1 引言  

新算法和程序的发现是人工智能辅助科学的前沿。近期的工作遵循一个简单而强大的配方：将大型语言模型与程序化评估和迭代搜索相结合。FunSearch（romera2024mathematical）首次证明这种循环可以发现真正的新数学对象，超越数十年的手工组合搜索。AlphaEvolve（novikov2025alphaevolve）将该原则推广到完整代码库，在硬件调度、矩阵乘法以及数学与工程中的开放问题上取得了最先进的结果。沿着这一工作路线，整个流程可以被视为一个迭代搜索框架，其中 LLM 充当程序变异算子，生成候选代码修改；任务特定评估器根据预定义评分标准分配适应度；选择机制在搜索空间中迭代地保留和精炼高表现程序。  

尽管取得了这些成功，三个相互关联的瓶颈阻碍了有效的进化搜索，尤其是在可靠地将程序变异导向大型复杂程序空间中的高质量区域方面。  

（1）**奖励稀疏性**。每次适应度评估都需要一次完整的程序执行——在程序搜索情况下是一次完整训练运行，在符号回归情况下是一次数值积分。只有当子代击败其 MAP-Elites 单元中的当前占据者时，存档才会更新，因此搜索过程仅收到一个标量信号，指示候选者是否在定义的适应度分数上优于现有程序。那些几乎击败现有程序（例如性能非常接近当前最优）的程序，或包含部分正确或结构上有意义的子表达式的程序，如果未严格改进单元，则仍被丢弃。结果，大量评估过的程序被缩减为一系列稀疏的二进制改进事件，丢失了关于改进接近度和中间结构修改贡献的细粒度关系信息。  

（2）**无信息的父代选择**。AlphaEvolve 通过适应度排名和随机多样性采样父代，将种群视为一个无结构的程序包。然而，程序种群可能携带大量的结构信息。有效的程序进化依赖于程序空间中局部结构相似性的存在，而不仅仅是高层适应度比较。没有这种局部性，小的变异会引发程序行为的不可预测变化，将搜索过程转变为很大程度上随机的探索。相反，当程序表现出有意义的局部相似性时，邻近程序往往会在功能上引发更一致和渐进的改变，允许迭代变异逐步精炼性能。  

（3）**静态变异算子**。在 AlphaEvolve 中，用于变异的 LLM 在整个搜索过程中是固定的，这将程序编辑空间限制在一个静态的预训练分布上。结果，系统持续从相同的结构变换集合中采样，而不考虑累积的搜索经验。  

#### 我们的贡献。  

我们提出了图增强进化（Graph-Augmented Evolution），这是一个在 OpenEvolve 骨干中同时解决所有三个局限的框架。一个**关系 GNN** 将每个程序解析为类型化计算图，并在线训练以预测适应度（§3.3）。一个**离散 SAC 元控制器** 获取每个程序的 GNN 嵌入并学习下一步应用哪种结构编辑，通过自动熵正则化平衡任务分数提升与种群新颖性和复杂度（§3.4）。一个**GRPO 微调循环** 使用组归一化评估奖励和父代 GNN 嵌入作为方差缩减基线，在线更新 LLM 变异算子，在搜索过程中逐步提升变异质量（§3.5）。  

我们在一个重要的科学任务——非线性振荡器系统的符号回归——上评估 GAE。我们使用 LLM-SR（shojaee2024llm）的基准数据集进行实验。在 LLM-SR（§4）实验中，GAE 发现了新颖的程序，在基准上持续匹配或超越先前的基线，达到有竞争力或最先进的性能。  

论文其余部分组织如下：§2 综述相关工作，§3 完整描述 GAE 框架，§4 呈现实验结果，§5 讨论局限和未来方向。  

## 2 相关工作  

先前的工作最多孤立地解决上述一个瓶颈。EvoTune（surina2025algorithm）分别通过 DPO 和 GRPO 微调 LLM，但父代采样仍是无信息的。基于替代模型的优化（white2021bananas；falkner2018bohb）提高了评估效率，但通常操作在固定的手动编码表示上，不支持开放式代码进化。质量-多样性 RL 方法（nilsson2021policy；faldor2023map；batra2023proximal）用策略梯度更新替代随机选择，但需要仅在程序终止时才可获得的密集每步奖励。没有现有方法同时弥合这三个差距。  

GAE 建立在 LLM 驱动的进化搜索之上，但偏离了其静态算子假设。FunSearch（romera2024mathematical）、AlphaEvolve（novikov2025alphaevolve）和 OpenEvolve（openevolve2025）都在搜索过程中冻结模型权重，仅依赖提示多样性进行探索。EvoPrompting（chen2023evopromptinglanguagemodelscodelevel）通过少样本提示扩展了这一思想，但选择策略仍是固定的。PACEvolve（yan2026pacevolve）通过手工设计的规则解决了脚手架级失效模式，如上下文污染、模式崩溃和弱协作，但变异模型和选择策略保持冻结。ThetaEvolve（wang2025thetaevolve）引入了测试时 RL 微调以提升变异质量，但权重更新绑定到单个任务特定目标，而非通用的可重用选择器。ShinkaEvolve（lange2025shinkaevolve）通过基于多臂老虎机的 LLM 集成和基于新颖性的拒绝过滤提高了样本效率，但选择策略仍然是静态的、由提示驱动，没有可学习组件。  

我们的工作在此骨干之上添加了一个可学习的选择器和微调循环，因此*“变异哪个”*和*“如何变异”*的决策都会随时间改善。  

在保持种群多样性的同时改进选择正是质量-多样性 RL 的目标，但现有方法与程序进化存在根本性不匹配。MAP-Elites（mouret2015illuminating）存档多样的精英，但均匀采样父代。策略梯度扩展 PGA-MAP-Elites（nilsson2021policy）、DCG-MAP-Elites（faldor2023map）、DCRL-MAP-Elites（faldor2025synergizing）和 PPGA（batra2023proximal）改进了这一点，但都需要在整体程序评估中缺失的密集每步奖励。AURORA（grillotti2022unsupervised）通过无监督学习行为描述符来放松手指定特征轴。GAE 在存档索引中采纳了这一精神，同时通过跨种群传播的图结构信号弥合了密集奖励的差距。  

## 3 方法论  

### 3.1 背景：MAP-Elites 和 OpenEvolve  

#### MAP-Elites。  
设 $\mathcal{X}$ 为程序空间，$\mathcal{B}$ 为 $k$ 维行为描述符空间，划分为单元 $\mathcal{C}$。MAP-Elites 维护一个存档 $\mathcal{A}:\mathcal{C}\to\mathcal{X}\cup\{\emptyset\}$，将每个单元映射到其当前精英程序。QD 分数聚合质量和覆盖率：$\mathrm{QD}(\mathcal{A})=\sum_{c\in\mathcal{C}}f(\mathcal{A}[c])\cdot\mathbf{1}[\mathcal{A}[c]\neq\emptyset]$。确定性更新规则仅在 $\beta$ 严格改进其单元的现有程序时才将其插入 $\mathcal{A}$，保证 $\mathrm{QD}$ 非递减。  

#### OpenEvolve。  
OpenEvolve 将程序存档 $\mathcal{A}$ 作为质量-多样性种群维护，使用 MAP-Elites 方案，程序被映射到多维特征网格，每个单元保留最佳执行者（openevolve）。每代，它从 $\mathcal{A}$ 中采样一个父代，从父代代码和 top-$k$ 精英（与父代分开抽取，因此灵感程序不同于展示给 LLM 的程序）组装 LLM 提示，并通过 SEARCH/REPLACE diff 或完整重写查询 LLM 获取变异子代。子代由用户提供的评估器在多阶段验证级联模式下评分，仅当在其单元中占据优势时才被接纳到 $\mathcal{A}$ 中。为保持大规模多样性，$\mathcal{A}$ 被分为多个独立演化的岛屿，通过定期迁移防止过早收敛，全部由中央控制器并行编排。  

### 3.2 图增强进化  

图增强进化在 OpenEvolve 循环中扩展了三个协同自适应组件，所有这些组件都基于一个共享的关系 GNN 编码器（§3.3），该编码器将每个程序的抽象语法树解析为类型化计算图，并生成结构嵌入 $z\in\mathbb{R}^{d}$。父代从固定大小的精英存档中均匀采样；共享嵌入随后条件化一个离散 Soft Actor-Critic 元控制器（§3.4），该控制器将父代状态 $z$ 映射到一个变异类型提示，将 LLM 导向结构上有希望的编辑类别，而非无方向编辑。其策略基于每代最佳子代的三部分奖励（任务分数、嵌入空间新颖性和复杂度惩罚）进行训练。每当 LLM 提议一组 $G$ 个子代时，在线 GRPO 微调（§3.5）将其组相对优势 $\hat{A}_{i}\propto R_{\beta_{i}}-R_{\alpha}$（子代奖励减父代奖励）转换为对 LLM 权重的原位 PPO-clip 更新，在不中断进化的同时适应变异策略，同时保持存档和 GNN 不变。GNN 编码器本身每 $K$ 代通过一个 MSE 替代损失单独更新，该损失将其嵌入回归到观测奖励上，之后刷新所有存档嵌入。三个组件不共享梯度，以不同时间尺度运行，使每个模块可独立替换。图 1 展示了完整架构，算法 1 总结了 GAE 循环的一代。  

![图 1](https://arxiv.org/html/2607.10127/S3.F1)  
**图 1：GAE 框架概览。** 关系 GNN 编码器将每个程序的抽象语法树解析为类型化计算图，并产生结构嵌入 $z$，在线根据观测奖励微调以跟踪不断演化的程序分布。父代从固定大小的精英存档中采样；父代嵌入 $z_{\alpha}$ 随后作为离散 Soft Actor-Critic 元控制器（策略 $\pi_{\phi}$ 与孪生评判器 $Q_{\theta_1}, Q_{\theta_2}$）的状态，该控制器采样一个变异类型提示 $a\sim\pi_{\phi}(\cdot\mid z_{\alpha})$ 来引导变异。每个父代由本地 LLM 生成 $G=8$ 个候选，由数值评估器评分。SAC 策略基于每代最佳子代进行训练，奖励为 $r=\mathrm{clip}(R(\beta)) + \lambda_1 \cdot \text{novelty} - \lambda_2 \cdot \text{complexity}$，而子代组相对奖励通过 GRPO 调整 LLM 生成策略。  

**算法 1** GAE — 一代  

```
1: 存档 P（固定大小 N）；GNN 编码器 Φ: code → ℝᵈ（d=128）；
   SAC 策略 π_φ（动作空间 A），孪生评判器 Q_θ₁, Q_θ₂；
   LLM 算子 π_θ_LLM，参考 π_ref；
   回放缓冲区 B；GNN 窗口 L；组大小 G；GNN 间隔 K；预热 W；代索引 s。
2: // 父代选择和变异提示
3: α ~ Uniform(P); z_α ← Φ(α)
4: if s − W < 0:
5:   a ← Uniform(A)
6: else:
7:   a ← π_φ(· | z_α)
8: // 变异和评估：生成 G 个子代
9: for i = 1 to G do
10:   β_i ← π_θ_LLM(α, a)      // 基于父代 α 和提示 a 的 LLM 变异
11:   R(β_i) ← evaluator(β_i)  // 评估（例如，符号回归拟合误差）
12: end for
13: // 更新 GNN 窗口
14: L.append({α, β_i, R(β_i)})
15: // 归档：如果 β* = argmax_i R(β_i) 改进其单元，则插入 P
16: // 元控制器训练（§3.4）：将 β* 添加到 B
17: SAC.update(B)              // 仅当 |B| > 0
18: // GRPO 微调（§3.5）：使用参考 LLM 的 KL 惩罚
19: θ_LLM ← GRPO_update(θ_LLM, {R(β_i)}, π_ref)  // 仅当 max_i R(β_i) > −10
20: // 定期 GNN 微调（§3.3）
21: if s mod K = 0 and |L| ≥ 10:
22:   微调 Φ（方程 5）；刷新 z_p ∀p ∈ P
```

### 3.3 程序图与 GNN 编码器  

#### 图表示。  
我们通过静态抽象语法树（AST）分析将每个候选程序解析为类型化计算图 $\mathcal{G}=(\mathcal{V},\mathcal{E})$。任何解析失败都会产生单个未知节点，保证总是返回有效图。具体到符号回归，节点是数学运算，边编码数据流。  

#### 关系 GNN 编码器。  
每个节点带有一个 $F$ 维独热编码表示其节点类型。我们通过一个关系图神经网络将每个程序图嵌入到 $z\in\mathbb{R}^{d}$。设存档大小为 $N$，输入投影为：
$$
h^{(0)} = \mathrm{GELU}(XW_{\mathrm{in}} + b_{\mathrm{in}}), \quad X\in\mathbb{R}^{N\times F},\; W_{\mathrm{in}}\in\mathbb{R}^{F\times d}.
$$

...（后续内容翻译略，原则同上）  

（注意：原论文后续还有内容，但用户只提供了这个范围。我们已翻译了摘要和§1-§3.3。如果用户需要更多，可继续提供。但根据提示，我们应只翻译给出的部分。）  

最终输出应为纯翻译的markdown，无额外说明。