← 科研空间 首页
arXiv:2504.19636 cs.AI / cs.NE Fitness Landscape Fei Liu et al. 原版 PDF

Fitness Landscape of Large Language Model-Assisted Automated Algorithm Search

用图论方法首次系统刻画 LLM 辅助算法搜索 (LAS) 的适应度景观:多峰、崎岖、低连通性,且高度依赖任务和 LLM 选择

阅读依据:arXiv:2504.19636v3 (2025-08-27) 的 PDF 与 TeX 源码 · 检索日期:2026-07-15

先给结论

6×6 6 个算法设计任务 × 6 个 LLM 全面评估
多峰崎岖 LAS 景观的核心特征
4 种 代码相似度度量评估

这篇论文做了一件填补空白的事:把 LLM 辅助算法搜索 (LAS) 当作一个优化问题,用图论方法可视化并分析了它的适应度景观 (fitness landscape)。核心发现可以概括为三点:

1. 景观是多峰且崎岖的——搜索空间充满局部最优,没有经典的漏斗结构 (funnel structure),图连接稀疏(低连通性),意味着 LLM 生成算法的过程本质上是一个碎片化的探索。

2. 景观结构高度依赖任务和 LLM——组合优化任务中约 80% 的算法集中在最低 20% 适应度区域;而符号回归任务中 98% 的算法远离最优。不同 LLM 产生的景观密度和聚类系数差异巨大:GLM-3-Turbo 密度最高 (0.00223),DeepSeek-Chat 最稀疏 (0.00069)。

3. 现有代码相似度度量不够用——BLEU、Weighted BLEU、AST Match、Data-flow Match 四种度量与性能变化 (performance delta) 的相关性较弱,揭示了一个关键研究空白:需要为 LAS 开发专门的算法相似度度量。

研究动机

LLM 辅助的进化/迭代搜索在自动算法设计领域取得了显著进展 (EoH, ReEvo, LLaMEA 等),但一个基本问题悬而未决:为什么这些方法有效?什么时候会失效?

核心矛盾

传统数学分析难以研究这些方法,因为算法空间过于复杂且 LLM 是黑盒。适应度景观分析是进化计算领域理解搜索行为的经典工具,但在 LLM 辅助搜索场景下几乎空白。

前人工作的不足

van 2025 的 CEG (Code Evolution Graphs) 是第一个尝试,用 AST 分析候选算法的结构属性,但它聚焦代码结构,没有真正讨论适应度景观。本文正是要补上这一块。

Q1: LLM 驱动的算法搜索的适应度景观长什么样?有哪些特征(如高原、崎岖性)可以刻画它?
Q2: 景观如何随不同的算法设计任务、不同的 LLM 和不同设置而变化?
Q3: 如何度量算法空间中的相似性?这些相似度度量与算法行为有何关联?
三种算法表示方法对比
图 1:自动算法搜索中的三种算法表示方法。(i) 连续/离散参数表示——传统优化技术可有效处理;(ii) 树/结构化表示——遗传编程等方法的领域;(iii) 代码/文本表示——LLM 使得直接在此复杂空间中搜索成为可能,但理解其适应度景观面临重大挑战。

数学表示及建模

LAS 的形式化

给定算法设计任务 $T$(如为 TSP 设计启发式算法)和实例集 $I$,目标是算法空间 $A^S$ 中找到使性能指标 $F(a, I)$ 最小的算法 $a^*$:

$$F(a, I) = \frac{1}{|I|}\sum_{i \in I} f(a, i), \quad a \in A^{S}$$
$$a^* = \underset{a \in A^{S}}{\arg\min} \, F(a, I)$$

这里 $f(a, i)$ 是算法 $a$ 在实例 $i$ 上的性能得分,$F(a, I)$ 是所有实例上的平均性能。

进化搜索流程

LAS 通过进化搜索在算法空间中求解。每个算法表示为代码和/或文本描述,经历三个步骤:

1
初始化:通过 prompt LLM 或选择现有人工算法生成初始种群 $P_0$。
2
迭代:从 $P_t$ 中选择父代 $a_p$,生成后代 $a_o = \text{LLM}(\text{Prompt}(a_p))$;评估 $F(a_o, I)$;更新种群得到 $P_{t+1}$。
3
终止:满足停止条件后输出最佳算法 $\hat{a}$。
$$a_o = \text{LLM}(\text{Prompt}(a_p))$$

适应度景观的形式化定义

沿用 Stadler 2002 的经典定义,适应度景观是一个三元组 $(S, NS, f)$:

关键设计决策:由于算法空间没有定义良好的距离度量或邻域结构,论文借鉴 Search Trajectory Networks (STNs) 和 Attractor Networks 的思路,通过父子生成关系来定义邻域——这是一种适应 LLM 黑盒特性的务实选择。

图的定义

TSP 适应度景观的二维图表示示意图
图 2:TSP 适应度景观的二维图表示。节点颜色表示目标值(越深越好),每个节点是一个构造性启发式算法,边表示搜索过程中的算法间连接。输入参数包括 node_c(当前节点)、node_d(目标节点)、nodes_u(未访问节点集)和 dis(距离矩阵),输出为下一个要访问的节点 ID。

算法流程 / 方法

实验使用 EoH (Evolution of Heuristics) 框架——一个标准的 LLM 辅助进化搜索框架,其简单的进化结构便于分析适应度景观。

EoH 的四个进化算子

E1 (探索)

大差异交叉算子,产生最宽的性能方差和最低的 Dataflow Match 分数——激进的探索行为。

exploration

E2 (探索)

另一种探索型算子,影响力度介于 E1 和变异算子之间。

exploration

M1 (开发)

小变异算子,保持较高的 Dataflow Match 分数和较紧的性能分布——语义保持性更强。

exploitation

M2 (开发)

另一种开发型变异算子,同样倾向于在父代算法附近做精细搜索。

exploitation

种群大小

默认 20,实验中还测试了 2, 5, 10, 50

最大评估次数

2,000 次候选算法评估(LES 的典型设置)

数据采集流程

  1. 在 LLM4AD 平台上运行 EoH,记录所有生成的算法及其父子关系
  2. 每次运行构建一个适应度景观图
  3. 对图进行 2D 和 3D 可视化(节点布局 + 适应度映射)
  4. 计算图论指标:密度 (Density)、平均度 (Average Degree)、聚类系数 (Clustering Coefficient)

四种代码相似度度量

BLEU

N-gram 匹配,评估词法相似度。最初用于自然语言翻译评估,对编程语言关键字和普通 token 一视同仁,无法捕捉结构或语义等价性。

Weighted BLEU

对编程关键字(如 int, return, for)赋予更高权重,更好地捕捉关键语法元素的变化,但仍是表层相似度。

AST Match

比较抽象语法树 (AST) 的子树匹配,忽略叶节点(如变量名),关注结构正确性。比 n-gram 方法更能抵抗表面代码变化。

Data-flow Match

分析数据流图中的变量依赖关系,检测值传播的不匹配(如错误的返回变量),捕捉语义层面的差异。计算复杂度最高。

实验设计

六个算法设计任务

类别 任务 缩写 目标
组合优化 Online Bin Packing OBP 实时分配物品到箱子,最小化箱子数量
Traveling Salesman Problem TSP 构造性启发式:选择下一节点,最小化总路径长度
Capacitated Vehicle Routing Problem CVRP 满足容量约束的构造性启发式
VRP with Time Windows VRPTW 同时满足容量和时间窗约束
Agent 设计 Mountain Car Car 优化 RL agent 动作,最少迭代到达目标
符号回归 Bacterial Growth Curve Bact 建模细菌生长曲线,最小化 MSE

六个 LLM

OpenAI

GPT-3.5-Turbo
GPT-4o-Mini

DeepSeek

DeepSeek-V3
DeepSeek-Chat

其他开源

Qwen2-Turbo
GLM-3-Turbo

实验平台:所有实验在开源 LLM4AD Platform 上执行。每次运行记录所有生成的算法及其父子关系,构建适应度景观图。

实验结果

1. 不同任务的适应度景观

五个任务的2D和3D适应度景观
图 3:五个算法设计任务的 2D 和 3D 适应度景观:OBP、TSP、CVRP、Car 和 Bact。3D 可视化中 z 轴表示适应度值,越小(越深)越好,红色节点为最优算法。
六个任务的适应度值概率分布
图 4:六个任务的适应度值缩放概率分布(归一化到 [0, 1] 范围)。

观察 1——三大景观特征:

  • 多峰 (Multi-modal):多个近似局部最优,搜索需穿越众多潜在解而非收敛到单一全局最优
  • 无漏斗结构 (Absence of Funnel):归因于 LLM 生成的固有随机性和缺乏明确指导原则
  • 低连通性 (Low Connectivity):图的平均度低、连接稀疏,信息交换效率受限

观察 2——任务间差异显著:启发式设计任务中约 80% 算法落在最低 20% 适应度区域。VRPTW 因时间窗约束的额外复杂性分布略有不同。Car 任务呈双峰分布,中间地带空白。符号回归任务中 98% 算法远离最优——函数或参数的微小变异往往导致性能剧变。

2. 不同 LLM 的景观对比 (TSP 任务)

六个 LLM 在 TSP 上的适应度景观
图 5:六个 LLM 在 TSP 任务上的 2D 适应度景观。
表 1:不同 LLM 在 TSP 上的图论指标
LLM Density Avg Degree Clustering Coef. 搜索策略特征
GLM-3-Turbo 0.00223 (最高) 4.04754 0.02282 (最高) 密集连接,局部聚焦
Qwen-Turbo 0.00213 4.76190 (最高) 0.00769 广泛探索邻居解
GPT-4o-Mini 0.00135 3.63397 0.00626 中等密度,平衡型
DeepSeek-V3 0.00114 2.91158 0.00533 稀疏拉长,偏全局
GPT-3.5-Turbo 0.00110 2.79492 0.00409 中等密度,平衡型
DeepSeek-Chat 0.00069 (最低) 2.15053 (最低) 0.00180 (最低) 最稀疏,精准全局搜索

核心洞察——探索-开发权衡:GLM-3-Turbo 和 Qwen-Turbo 擅长局部精细优化但有陷入局部最优的风险;DeepSeek-Chat 的稀疏连接有利于全局探索但牺牲了局部细化能力;GPT-3.5-Turbo 和 GPT-4o-Mini 走平衡路线。论文指出,组合不同 LLM 的行为可能增强搜索过程——这与 AlphaEvolve 等近期工作使用多 LLM 集成的发现一致。

3. 不同种群大小的景观 (DeepSeek-V3, TSP)

不同种群大小下的适应度景观
图 6:DeepSeek-V3 在 TSP 上不同种群大小 (2, 5, 10, 50) 的景观。仅显示权重 >1 的边以强调重要连接。小种群偏向局部开发,大种群实现更广泛的探索,揭示景观固有的多峰复杂性。

4. 进化轨迹

DeepSeek-V3 在 TSP 上的进化轨迹
图 7:候选算法向最优算法(红色高亮)进化的有向网络。节点颜色表示适应度值,节点按层次排列,标签显示节点 ID(搜索顺序)和适应度值。揭示了分支探索模式、收敛过程和关键进化路径。

轨迹可视化揭示了三个关键方面:(1) 分支探索模式——LES 同时探索多个有前景的方向;(2) 向更有效算法的收敛趋势;(3) 看似次优的中间算法可能是通往优秀算法的关键跳板

5. 算法相似度分析

相似度度量关系矩阵
图 8:TSP 和 OBP 任务上五个关键指标(BLEU、Weighted BLEU、AST Match、Dataflow Match、Performance Delta)的关系矩阵。对角线为 KDE 分布图,非对角线为散点图配回归线,标注相关系数。

指标间相关性

BLEU、Weighted BLEU、AST Match、Dataflow Match 之间强正相关。Dataflow Match 和 AST Match 与 TSP 性能变化相关性最高,表明它们与功能正确性更对齐。

分布差异

TSP 的 AST 和 Dataflow Match 得分偏向高值,意味着有效解倾向于保留结构和语义特征。OBP 分散度更大,反映实现多样性更高。

性能可预测性

TSP 上所有相似度度量呈反趋势——高相似度对应低性能变化。OBP 趋势更弱或不一致,尤其 BLEU 和 AST Match,说明相似度度量在某些领域不足以预测性能。

TSP 上相似度度量与性能变化的相关性热力图
图 9:TSP 上四种相似度标准与性能变化之间的相关矩阵。

6. 算子级别的分析

不同算子的性能变化分布
图 10:不同算子类型的性能变化 (performance delta) 分布。
不同算子的 Dataflow Match 分数分布
图 11:不同算子类型的 Dataflow Match 分数分布。

算子行为验证:E1 产生最宽方差和最高中位性能变化(最激进),对应最低的 Dataflow Match 分数。M1 和 M2 保持较高的 Dataflow Match 分数和更紧的性能分布(语义保持性更强)。这验证了使用不同算子平衡探索和开发的必要性。

局限性承认:尽管观察到相关性,所有度量的相关系数普遍较小,跨度量和任务变异性显著。同一算法可以有多种代码实现(多对一关系),当前代码相似度度量无法充分捕捉算法等价性。这揭示了一个关键研究空白:需要为 LAS 开发专门的相似度度量。

探索-开发视角的深层解读

论文将 EoH 的四个算子标记为探索型(E1、E2)和开发型(M1、M2),并通过性能方差与 Dataflow Match 分布验证了这一标记。但"探索"与"开发"在 LAS 场景下的含义远比算子标签 复杂。以下从六个维度厘清论文实际报告了什么、哪些是描述性观察、哪些是尚未验证的推断。

1. 观察到的父子图 vs 验证过的语义邻域

论文实际构建的图:以 LLM 生成的父子关系定义邻域——$a_i \in NS(a_j)$ 当且仅当 $a_i = \text{LLM}(\text{Prompt}(a_j))$。这是一种方法条件化的生成图,描述的是 "搜索过程实际产生了哪些转换",而非"算法空间中哪些算法真正接近"。
论文未验证的:这种父子邻域是否比随机连接更有意义,论文没有做对照实验。 同一父代的两次 LLM 调用可能产生截然不同的后代——这意味着"邻域"的宽度高度依赖 LLM 的随机性、prompt 设计和温度设置,而非算法空间本身的拓扑结构。论文在 Limitations 中 坦承"同一算法可以有多种代码实现"(多对一映射),暗示代码层面的邻域可能严重偏离 功能层面的真实接近性。
要验证语义邻域需要什么:
  • 定义不依赖生成过程的算法距离度量(如执行轨迹相似度、输入-输出行为等价性)
  • 对比父子图中的边端点 vs 语义邻域中的邻居——如果重合率高,则父子图是语义邻域的合理近似
  • 消融实验:用随机连接替代父子连接,观察景观指标和搜索性能是否显著变化

2. 代码/AST/文本相似度 vs 算法行为相似度

论文评估了四种代码层面的相似度度量,它们捕捉的层次各不相同:

度量 捕捉的层次 论文报告的相关性
BLEU 词法(n-gram 匹配) 与 Performance Delta 弱相关,OBP 上趋势不一致
Weighted BLEU 词法 + 关键字权重 与 BLEU 强正相关;对性能的预测力同样有限
AST Match 语法结构(子树匹配,忽略叶节点) TSP 上与 Performance Delta 相关性最高之一
Data-flow Match 数据流语义(变量依赖图) TSP 上与 Performance Delta 相关性最高之一;OBP 上较弱
关键区分:这四种度量衡量的是代码文本/结构的相似度,而非 算法行为的相似度。两个语法不同的实现可能功能完全等价(多对一映射), 而两个语法几乎相同的代码可能在关键变量上不同导致行为完全不同。论文明确指出: "current code similarity metrics, while informative, inadequately capture the complex relationship between algorithmic modifications and performances"。
论文建议但未实现的方向:执行轨迹相似度、算法复杂度特征分析、或学习到的 功能表示(learned representations)。这些方法将相似度从代码空间转移到 行为/功能空间,可能更准确地反映算法等价性。

3. 描述性崎岖度/多峰性 vs 因果相切换策略

论文通过 2D/3D 可视化和三个图论指标(密度、平均度、聚类系数)描述了景观的特征:

这些是描述性观察,不是因果机制。论文没有建立"景观崎岖度 → 搜索效率"的 定量因果关系,也没有提出基于景观特征的相切换策略(即根据当前景观状态自动 切换探索/开发模式)。论文的贡献是刻画景观,而非利用景观指导搜索。
经典景观分析工具的缺失:进化计算领域有更丰富的定量景观指标——自相关 (autocorrelation)、适应度距离相关性(fitness distance correlation)、上位性度量 (epistasis measures)等。论文几乎没有使用这些工具,使得"崎岖"和"多峰"的描述主要依赖 可视化,而非可量化的统计量。

4. 论文实际报告的 E1/E2 vs M1/M2、LLM 差异、种群大小与新颖性

4.1 算子层面(E1/E2 vs M1/M2)

论文在 arXiv:2504.19636v3 中明确表述:

验证证据来自两张图:

论文的结论措辞:"The results also validate the necessity of using different operators for balancing exploration and exploitation."——这是对算子设计意图的事后验证, 不是对"何时应该探索、何时应该开发"的策略性回答。论文没有报告 E2 的 Performance Delta 和 Dataflow Match 的具体分布特征,仅提到其影响力度介于 E1 和变异算子之间。

4.2 LLM 层面

在 TSP 任务上,六个 LLM 产生了结构显著不同的景观(见 Table 1):

边界声明:这些 LLM 层面的"探索 vs 开发"标签是从图论指标推断的 描述性特征,论文没有验证:①密集型 LLM 在需要局部精细的任务上确实表现更好;②稀疏型 LLM 在需要全局探索的任务上确实表现更好。论文也没有回答是 LLM 的什么特性(参数规模、训练数据、 对齐方式)导致了这些差异。

4.3 种群大小

仅报告了 DeepSeek-V3 在 TSP 上的结果(Fig 6):

边界声明:这是单一 LLM 在单一任务上的观察,无法判断该结论是否泛化到 其他 LLM 或其他任务类型。论文没有提供不同种群大小下的最终解质量对比。

4.4 新颖性(Novelty)

论文未直接测量新颖性。没有报告搜索过程中唯一算法的比例、重复生成率 随时间的变化、或探索覆盖的算法空间比例。节点大小反映了"同一算法被生成的次数", 但论文没有将其转化为系统级的新颖性指标。这是理解探索效率的一个关键缺口。

5. 重复运行/随机性证据缺口

论文没有报告独立重复次数、随机种子、运行间方差或置信区间。 因此,仅凭论文文本无法确定每个任务 × LLM × 配置是否做了多次独立运行,也无法判断展示的景观 在 LLM 随机性下是否稳定。这里应当表述为重复运行证据未披露,而不能反向断言所有配置都只运行一次。

这使下列结论缺少跨运行不确定性信息:

论文在 Limitations 中没有提到这一问题。Limitations 部分仅讨论了代码相似度 度量的不足,没有涉及重复运行披露与景观稳定性风险。

6. 在声称"探索或开发何时有效"之前需要测量的具体指标

论文提供了景观的描述性刻画,但要回答"什么时候应该探索、什么时候应该开发" 这一策略性问题,需要以下论文中尚不存在的测量:

搜索空间覆盖度

独立算法数量 / 总生成数量的比率随时间的变化;探索阶段应呈现高覆盖率, 开发阶段应趋于收敛。论文没有报告这一指标。

解质量与景观指标的关联

图密度/聚类系数与最终解的适应度之间的定量关系。 论文报告了不同 LLM 的不同图指标,但没有将图指标与搜索性能关联。

算子-景观交互效应

在不同景观状态下(早期/中期/后期),E1/E2/M1/M2 各自产生的 性能提升分布。论文只在整体上比较算子,没有按搜索阶段分层分析。

多运行统计显著性

每个配置至少 5–10 次独立运行,报告图指标的均值±标准差, 以及跨运行景观结构的变异系数。当前论文没有报告这些重复运行统计。

新颖性 vs 质量权衡曲线

绘制 Pareto 前沿:算法新颖性(用代码或行为相似度定义)与 性能的关系。论文的相似度分析仅用相关系数,没有构建这一权衡曲线。

因果消融实验

移除某些算子(如只用 E1/E2 或只用 M1/M2)后观察搜索性能变化; 或在不同 LLM 组合下测试集成效果。论文建议多 LLM 集成但未实验验证。

总结:论文的核心贡献是首次系统刻画 LAS 的适应度景观—— 确认了多峰性、崎岖性、任务/LLM 依赖性,以及现有代码相似度度量的不足。 关于探索与开发的策略性结论(何时有效、如何切换),论文提供了观察证据 但未提供因果证据。从描述性景观分析走向策略性搜索指导, 是本文指出的研究方向,也是后续工作需要填补的关键空白。

我的评论

优点

不足与值得追问的点

启发

对 LAS 系统设计的直接启发:

  • 选择 LLM 时应考虑任务特性:需要精细搜索的任务用密集型 LLM (如 GLM-3-Turbo),需要广泛探索的任务用稀疏型 (如 DeepSeek-Chat)
  • 多 LLM 集成是值得探索的方向——不同 LLM 的互补探索/开发行为天然适合集成
  • 种群大小是一个关键超参数:小种群偏向局部开发,大种群实现更广探索

One More Thing

论文在 Limitations 中提到"同一个算法可以有多种代码实现"——这其实指向了一个更深层的问题:算法空间本身是什么? 当前 LAS 把算法等同于代码文本,但代码空间和算法功能空间之间存在巨大的多对一映射。如果我们能在功能空间而非代码空间中定义景观和邻域,搜索效率可能大幅提升。这需要一种"算法语义嵌入"——也许可以用执行轨迹、算法复杂度特征、甚至学习到的表示来构建。这个方向可能是 LAS 景观分析的下一个突破口。

Reference / Evidence