🔭 astrophysics

The Inefficiency of Genetic Programming for Symbolic Regression

该论文利用改进的等式饱和算法枚举语义唯一表达式，通过对比真实世界数据集上的实验结果，揭示了遗传编程在符号回归中搜索效率低下，仅探索了极小部分解空间且存在大量重复评估的问题。

原作者： Gabriel Kronberger, Fabricio Olivetti de Franca, Harry Desmond, Deaglan J. Bartlett, Lukas Kammerer

发布于 2026-03-30

📖 1 分钟阅读☕ 轻松阅读

原作者： Gabriel Kronberger, Fabricio Olivetti de Franca, Harry Desmond, Deaglan J. Bartlett, Lukas Kammerer

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

这篇论文探讨了一个有趣但令人担忧的问题：在让计算机“发明”数学公式（符号回归）时，一种叫“遗传编程”（Genetic Programming, GP）的流行方法，其实效率非常低，甚至不如随机乱猜。

为了让你轻松理解，我们可以把这项研究想象成在一个巨大的、充满各种乐高积木的房间里找特定的模型。

1. 核心任务：寻找完美的乐高模型

想象你手里有一堆乐高积木（数学符号，如 $+$ , $-$, $\times$ , $\div$ 等）和一张图纸（真实世界的数据，比如水流速度或星系运动）。你的目标是拼出一个乐高模型（数学公式），让它完美匹配图纸上的数据。

遗传编程 (GP)：就像一群“进化中的机器人”。它们随机拼出一些模型，把表现好的模型“生宝宝”（交叉、变异），一代代进化，希望能拼出完美的模型。
穷举搜索 (ESR)：就像一位“超级耐心的数学家”。它不靠运气，而是把房间里所有可能拼出的、且本质上不同的模型都列出来，然后一个个测试，直到找到最好的那个。

2. 研究者的发现：机器人在“原地打转”

研究者利用改进后的“超级数学家”（穷举搜索），把房间里所有真正独特的模型都找了出来。然后，他们让“机器人”（GP）进去跑了几十次，看看它们的表现。

结果令人惊讶：

🚫 问题一：机器人只逛了房间的 1%

如果房间里有 100 万种独特的模型，机器人跑了几十万次，却只真正“看”到了其中很少的一部分（大约 1% 到 10%）。大部分时间，它们都在重复看那些已经看过的东西。

🚫 问题二：机器人分不清“长得像”和“其实一样”

这是最有趣的部分。

场景：机器人拼出了模型 A（比如 2 + 3）和模型 B（比如 3 + 2）。
人类视角：这两个模型虽然积木摆放顺序不同，但算出来的结果是一模一样的（都是 5）。它们是**“双胞胎”**。
机器人视角：因为积木摆放顺序不同，机器人以为这是两个完全不同的新模型！于是，它把 2+3 测了一遍，觉得不错；过会儿又测了 3+2，又觉得不错。
后果：机器人浪费了大量时间，反复测试那些本质上完全相同的模型。这就好比你为了找一把钥匙，把同一把钥匙放在不同的口袋里，然后反复去摸那个口袋，却忘了它们其实是同一把钥匙。

🚫 问题三：随机乱猜反而更聪明

研究者做了一个对比实验：让另一个程序在所有独特的模型中随机挑选一个来测试（就像闭着眼睛在房间里乱抓一个模型）。

结果：在寻找好模型这件事上，这个“闭眼乱抓”的随机程序，竟然比费尽心机“进化”的机器人更快、更准！
原因：因为机器人太执着于“进化”，导致它总是在同一个区域打转，反复测试那些重复的模型；而随机程序因为不重复，反而更容易碰到那些真正的好模型。

3. 两个真实的“考场”

研究者用两个真实的科学难题来测试：

水管里的水流（尼库拉兹数据集）：就像研究水在粗糙管道里流得有多快。
星系的运动（径向加速度关系）：就像研究星星转得有多快，这涉及到暗物质和引力的奥秘。

在这两个考场上，机器人（GP）都表现得很挣扎。它很难找到那个“满分答案”，而且它花了很多时间在做无用功（重复测试）。

4. 为什么这很重要？

这就好比我们在教 AI 做数学题。我们以为 AI 像达尔文的进化论一样，通过不断试错能越来越聪明。但这篇论文告诉我们：如果 AI 不懂得“去重”，不懂得识别“本质相同但长相不同”的公式，它就是在做无用功。

比喻：想象你在找一把藏在迷宫里的钥匙。
- 随机搜索：你闭着眼在迷宫里乱走，虽然可能走弯路，但你不会在同一个死胡同里转圈。
- 遗传编程（现状）：你手里拿着一张地图，但你总是把“向左转”和“向右转但其实是同一条路”当成两个不同的路口。你在这个死胡同里转了 100 圈，以为自己在探索新世界，其实只是在原地踏步。

5. 结论与启示

这篇论文并不是说遗传编程完全没用，而是指出它在处理符号回归（找公式）时，存在一个巨大的效率漏洞：它太容易重复访问那些本质上相同的解了。

未来的方向：我们需要给这些“机器人”装上更聪明的“眼睛”（比如论文中使用的等式饱和技术），让它们能一眼看出 2+3 和 3+2 是一样的，从而不再浪费时间去重复测试。只有这样，它们才能真正发挥“进化”的优势，而不是在原地打转。

一句话总结：
这篇论文发现，让计算机通过“进化”来找数学公式，就像让一群没戴眼镜的工人在迷宫里找钥匙——它们不仅走得慢，还总是在同一个地方反复撞墙，甚至不如闭着眼睛随机乱走的人找得快。我们需要给它们戴上“眼镜”，帮它们看清哪些路其实是重复的。

论文技术总结：遗传编程在符号回归中的低效性

1. 研究背景与问题定义

符号回归 (Symbolic Regression, SR) 旨在从参数化函数族中寻找一个数学表达式，以准确拟合给定的数据集。遗传编程 (Genetic Programming, GP) 是解决 SR 问题的主流进化算法。然而，GP 在搜索过程中面临两个核心挑战：

搜索空间巨大且冗余：许多结构不同的表达式（基因型）在数学上是等价的（即语义相同，如 $x(x+1)$ 与 $x^2+x$ ），导致搜索空间中存在大量冗余。
效率低下的搜索行为：现有的研究缺乏对 GP 在有限且可穷举的搜索空间内行为的确切量化。GP 是否有效地探索了独特的表达式？还是花费了大量时间重复评估语义相同的表达式？

本文旨在通过穷举所有可能的解，量化 GP 在有限设置下的搜索效率，并将其与理想化的随机搜索 (Random Search, RS) 进行对比，以揭示 GP 在寻找最优解时的低效性。

2. 方法论

2.1 改进的穷举符号回归 (Improved Exhaustive Symbolic Regression, ESR)

为了构建基准，作者改进了 ESR 算法，使其能够生成并评估特定长度限制内所有语义唯一的表达式。

语法生成：使用广度优先搜索 (BFS) 生成表达式树。
语义去重 (核心创新)：利用等式饱和 (Equality Saturation, eq-sat) 技术。
- 引入 MetaTheory.jl 包和一组重写规则（交换律、结合律、分配律等）。
- 将表达式转换为规范形式 (Canonical Form)。
- 通过哈希值识别并剔除语义重复的表达式。
- 这使得生成的解空间比原始基因型空间小几个数量级（例如，长度 12 的树有 $10^9$ 种结构，但去重后仅约 $10^6$ 种唯一表达式）。
参数优化：对每个唯一表达式进行参数拟合（使用 VAR1 或 BFGS 优化器），以计算其适应度。

2.2 遗传编程 (GP) 实验设置

算法：基于 TinyGP 实现，并针对单变量函数和参数优化进行了适配。
数据集：
1. Nikuradse 数据集：描述粗糙管道中湍流摩擦与相对粗糙度的关系。
2. 径向加速度关系 (RAR) 数据集：描述星系动力学中可见物质加速度与总动力学加速度的关系（涉及暗物质与修正牛顿动力学 MOND 的争论）。
实验设置：
- 设置不同的最大长度限制（10, 12, 20 个节点）。
- 运行 50 次独立实验，记录所有评估过的表达式。
- 对比对象：改进的 ESR（用于生成唯一表达式集合）和基于唯一表达式的理想化随机搜索 (RS)。

2.3 评估指标

成功概率 (Success Probability)：在给定评估次数下找到特定质量解（如 MSE 低于某阈值）的概率。
唯一性分析：统计 GP 访问的表达式中，有多少是结构独特的，有多少是语义重复的（通过 eq-sat 简化后识别）。

3. 主要结果

3.1 解空间特征

解的分布极度偏斜：在 Nikuradse 和 RAR 数据集中，绝大多数（>99%）表达式的拟合效果很差。只有极少数（约 0.01% - 1%）的表达式接近全局最优解。
冗余度随长度指数增长：随着表达式长度限制的增加，基因型（树结构）数量与唯一语义表达式的数量差距呈指数级扩大。

3.2 GP 的搜索效率低下

无法找到全局最优：在 50 次独立运行中，GP 未能找到 ESR 穷举出的全局最优解（即使在长度限制为 20 时，也未找到最优解）。
成功率低于随机搜索：在相同的评估次数下，理想化随机搜索 (RS) 找到高质量解的概率显著高于 GP。
- 例如在 Nikuradse 数据集（长度 10）中，RS 仅需约 100 次评估即可达到 50% 的成功率，而 GP 需要约 600 次。
- 对于更严格的阈值，GP 的成功率甚至趋近于零，而 RS 仍能找到解。
大量重复评估：
- 语义重复：GP 评估的表达式中，仅 10% - 20% 是语义唯一的。这意味着约 80%-90% 的评估是浪费在重复的、语义等价的表达式上。
- 退化现象：大量生成的表达式在简化后退化为常数模型（如 $p_1$ ），这些表达式虽然结构简单但适应度尚可，导致 GP 容易陷入局部陷阱。

3.3 不同长度限制的表现

即使将 GP 的长度限制放宽到 20（而 ESR 基准限制为 12），GP 在寻找长度 $\le 12$ 的最优解方面，其成功率依然远低于在长度 12 空间内直接进行随机搜索的效率。

4. 关键贡献

量化了 GP 的低效性：首次通过穷举法证明了在受限的 SR 搜索空间中，GP 的搜索效率甚至低于简单的随机搜索（在唯一表达式空间内）。
引入了等式饱和 (Eq-sat) 进行语义去重：
- 不同于以往仅依赖适应度值或参数化形式来检测重复，本文利用 eq-sat 将表达式简化为规范形式，从而能够检测出参数不同但函数等价的表达式。
- 这揭示了 GP 在搜索过程中产生了大量的“同义反复”。
提供了基准数据集与算法：利用改进的 ESR 算法，为 Nikuradse 和 RAR 数据集提供了完整的唯一解空间分布，为未来 SR 算法的评估提供了黄金标准。
挑战了冗余有益论：以往有观点认为搜索空间中的冗余（同义表达）有助于跳出局部最优。本文结果表明，在有限长度下，这种冗余主要导致了搜索效率的急剧下降，而非帮助。

5. 局限性与未来工作

长度限制：由于计算复杂度，ESR 仅能穷举较短的表达式（长度 $\le 12$ ）。实际应用中 GP 常使用更长的表达式（如 100 节点），其冗余比例是否依然如此之高尚待研究。
未考虑进化路径：研究仅关注“访问了哪些表达式”，未分析“如何到达”（即进化路径/谱系）。
多变量扩展：目前主要针对单变量函数，多变量情况下的搜索空间特性可能不同。

6. 结论与意义

本文通过严格的实验分析表明，遗传编程在符号回归任务中存在严重的低效性。其主要原因并非仅仅是参数优化的困难，而是 GP 在搜索空间结构上的盲目性，导致其花费大量计算资源重复评估语义相同的表达式。

这一发现对 SR 领域的启示是：

现有的 GP 算子（交叉、变异）可能过于粗糙，未能有效利用语义信息。
未来的 SR 算法应更积极地集成语义去重机制（如等式饱和），在生成阶段就剔除冗余，或者设计能够感知语义空间的搜索策略，以避免在巨大的冗余空间中无效探索。
在评估 SR 算法时，仅看最终结果是不够的，必须分析其搜索过程的效率和唯一性。