funsearch · 学习资源

Google DeepMind

图1：Google DeepMind 官方头像

当AI开始"做数学题"：FunSearch 与人类数学家的世纪合作

想象一下，你是一位数学家，面对一个困扰同行数十年的数学难题——比如"Cap Set 问题"（在三维空间中找到最大点集，要求任意三点不在同一条直线上）。传统的做法是：翻阅文献、提出猜想、手动推导证明。但现在，你的合作者是一个能够自动生成并进化数学证明程序的 AI 系统——这就是 Google DeepMind 在 2023 年底发表于 Nature 期刊的 FunSearch。

这不仅仅是"AI 解题"的故事。FunSearch 真正令人震撼的地方在于：它发现了一些人类数学家从未想到的新算法。这是人类历史上，AI 首次在真实的、未解决的数学前沿问题上做出可验证的新发现。

背景：LLM 进化论——从"回答问题"到"发明方法"

大语言模型（LLM）问世以来，其能力被广泛用于回答问题、写文章、写代码。但这些本质上都是在已有知识上的检索和组合，鲜少涉及真正的创造性发现。

FunSearch 的核心灵感来自一个古老而强大的范式：进化算法。在进化算法中，候选解（程序）会经历"变异"和"选择"的压力，优胜劣汰，逐代进化，最终得到高质量的解。但传统进化算法的问题是：变异的随机性太强，方向不明确，效率低下。

DeepMind 的创新在于：用 LLM 替代随机变异。LLM 基于海量预训练数据，理解什么是"好的程序结构"，它生成的候选程序不再是盲目的随机修改，而是一种有方向、有意图的"智能变异"。配合一个自动化的"评估器"（Evaluator）来检验这些程序是否正确，最终形成了一个"LLM 提议 → 评估器验证 → 优秀者进入种群 → 下一代 LLM 在此基础上继续改进"的闭环。

核心原理：函数空间中的进化搜索

FunSearch 的名字是 "Function Space Search" 的缩写——在函数空间中进行搜索。它的运作方式可以分为以下几个关键步骤：

1. 问题规范（Specification）

用户需要编写一个"问题规范"文件，这是 FunSearch 的输入。一个典型的规范文件包含两部分：

待进化函数（@funsearch.evolve 装饰）：LLM 需要不断改进这个函数。比如在 Cap Set 问题中，这个函数的职责是给定当前已有的候选点集，输出下一个应该加入的点。LLM 需要写出一个优先级函数来指导如何选择新点。
运行函数（@funsearch.run 装饰）：用于实际评估某个完整程序的质量，即运行候选程序来计算最终解的得分。

# 示例结构（来自 cap_set 问题规范）
@funsearch.evolve
def evaluate(candidate_set):
    # 优先级函数：决定如何选择下一个点
    pass

@funsearch.run
def run(specification):
    # 运行并评估完整程序
    pass

2. 程序数据库（Programs Database）

FunSearch 维护一个种群数据库，其中存储了历史中表现最好的候选程序。每一代从数据库中采样若干程序，将它们的代码片段（作为"灵感"）放入提示词，送给 LLM。

数据库的设计引入了进化论中"岛屿模型"的思想——数据库被划分为多个"岛屿"（islands），每个岛屿独立进化，定期交换最优个体。这确保了种群的多样性，避免过早收敛到局部最优。

3. LLM 提案 + 评估器筛选

LLM 基于提示词（包含问题描述、历史成功程序片段）生成新的候选程序。这些程序被送入评估器（Evaluator），评估其在给定测试集上的表现。只有得分超过阈值的程序才会被写入数据库，成为下一代进化的基础。

关键：评估器是自动化的、无需人工介入的，它负责过滤 LLM 产生的"幻觉"和错误解法。这是 FunSearch 与纯提示工程方法的核心区别——它有严格的验证闭环。

4. 核心代码模块

仓库的 implementation/ 目录实现了 FunSearch 的核心逻辑：

文件	职责
`funsearch.py`	主流程：加载规范 → 初始化数据库 → 主循环（采样→LLM→评估→入库）
`programs_database.py`	种群数据库：岛屿模型、多样性采样、程序评分管理
`sampler.py`	从数据库中采样历史程序，构建 LLM 提示词
`evaluator.py`	执行候选程序，验证结果正确性
`code_manipulation.py`	解析和修改 Python 代码（处理 @funsearch 装饰器）
`config.py`	配置参数：种群规模、岛屿数、每轮采样数等

震惊数学界：从 Cap Set 到 Bin Packing 的多项突破

Cap Set 问题：20 年来最大的突破

Cap Set 问题是极值组合学的核心问题之一——在 n 维向量空间 F_3^n 中，找到最大的"无直线点集"。 Terence Tao 曾将其描述为他"最喜爱的开放问题"。

2023 年 12 月，FunSearch 宣布：在 n=8 的情况下，发现了迄今为止已知最大的 Cap Set，这是该领域 20 年来最大的一次突破。更重要的是，FunSearch 输出的不是一组数字，而是一个可解释的程序——描述了如何构造这个最大点集的算法。数学家 Jordan Ellenberg（威斯康星大学）评价道：

"FunSearch 生成的解决方案远比数字列表要丰富得多。当我研究它们时，我能学到新的数学思想。"

Bin Packing 问题：超越人类设计的启发式算法

Bin Packing（装箱问题）是计算机科学中的经典问题：将不同大小的物品装入最少数量的箱子。广泛应用于物流集装箱装载、数据中心任务分配等场景。

DeepMind 将 FunSearch 应用于在线 1D 装箱问题，发现了超越广泛使用的人类设计启发式算法的新策略。更难得的是，输出的代码可以直接部署到真实工业系统中，可解释且可维护。

2024 年 12 月更新：竞赛编程的 AI 搭档

2024 年 12 月，DeepMind 发布了新进展：FunSearch 的方法被用于竞赛编程，人类程序员编写解决方案的"骨架代码"，LLM 负责进化驱动策略的核心函数。这种人机协作模式在竞赛编程中超过了顶尖人类选手的前百分位。而且现在 FunSearch 不再需要专门的代码模型，Gemini 1.5 Flash 就足以驱动整个流程。

上手体验：零安装，一键 Colab

对于普通研究者和 AI 爱好者，FunSearch 的上手门槛被设计得极低。项目提供了 4 个完整的 Jupyter Notebook（Cap Set、Admissible Set、Bin Packing、Cyclic Graphs），可以直接在 Google Colab 中打开并运行，无需任何安装配置。

对于想要深入研究底层实现的开发者，implementation/ 目录提供了完整的单线程核心代码：

git clone https://github.com/google-deepmind/funsearch.git
cd funsearch
# 打开任意 problem/*.ipynb 即可开始

不过需要注意的是：核心代码本身不包含 LLM 调用接口和沙箱隔离环境。完整的生产级 FunSearch 系统还需要：

一个支持代码生成的 LLM API（如 Gemini API）
一个安全的代码执行沙箱（防止 LLM 生成恶意代码）
分布式任务调度基础设施（implementation/ 是单线程的，真实大规模运行需要分布式扩展）

技术评价：优势与局限

优势

真正的创造性发现：不同于 LLM 的知识检索，FunSearch 能够生成此前不存在的、新颖的数学算法，在 Cap Set 等开放问题上实现了人类数学家未曾做到的突破。
可解释性强：输出的是可读的 Python 程序，而非黑箱模型权重。这意味着数学家可以分析、学习并进一步改进这些"AI 发现"的算法。
泛化能力强：同一套框架在 Cap Set（纯数学）和 Bin Packing（应用算法）两个截然不同的领域都取得了最先进结果，说明方法具有通用性。

局限

依赖问题规范的质量：FunSearch 的效果很大程度上取决于用户编写的规范文件——即问题建模的质量。坏的规范会导致搜索无法收敛。
需要自动化评估器：并非所有问题都能轻松设计自动化评估器。对于难以自动验证答案正确性的问题（如开放式数学证明），FunSearch 的适用性受限。
计算资源要求高：虽然 implementation/ 是单线程的，但完整的 FunSearch 需要 LLM 推理（涉及 API 调用成本）和大量程序评估（计算密集），实际使用需要相应资源支撑。

行业意义：AI for Science 的里程碑

FunSearch 的发表是 AI for Science 领域的标志性事件。长期以来，科学发现的"最后一公里"——提出新假设、新算法、新证明——被视为人类科学家的专属领域。FunSearch 用实验证明了：在特定领域，只要设计好评估机制，LLM 驱动的进化搜索可以超越人类直觉，发现前所未有的解决方案。

更重要的是，FunSearch 的方法论具有很强的可扩展性。任何可以用代码表达、可自动评估的问题——从通信理论到生物信息学，从优化算法到自动定理证明——都有可能借助类似方法实现 AI 辅助发现。它开创了一种人机协作的新范式：人类定义问题和评估标准，AI 在解空间中搜索并进化，这种模式可能在未来十年深刻影响科研工作的组织方式。

项目基本信息

项目	信息
组织	Google DeepMind
GitHub Stars	1,094
编程语言	Jupyter Notebook / Python
开源协议	Apache License 2.0
发表期刊	Nature (2023)
核心依赖	LLM API（如 Gemini 1.5 Flash、PaLM 2）
运行方式	Google Colab / 本地 Python
最新更新	2024 年 12 月（竞赛编程扩展）

Google DeepMind

图1：Google DeepMind 官方头像

当AI开始"做数学题"：FunSearch 与人类数学家的世纪合作

背景：LLM 进化论——从"回答问题"到"发明方法"

核心原理：函数空间中的进化搜索

FunSearch 的名字是 "Function Space Search" 的缩写——在函数空间中进行搜索。它的运作方式可以分为以下几个关键步骤：

1. 问题规范（Specification）

用户需要编写一个"问题规范"文件，这是 FunSearch 的输入。一个典型的规范文件包含两部分：

待进化函数（@funsearch.evolve 装饰）：LLM 需要不断改进这个函数。比如在 Cap Set 问题中，这个函数的职责是给定当前已有的候选点集，输出下一个应该加入的点。LLM 需要写出一个优先级函数来指导如何选择新点。
运行函数（@funsearch.run 装饰）：用于实际评估某个完整程序的质量，即运行候选程序来计算最终解的得分。

# 示例结构（来自 cap_set 问题规范）
@funsearch.evolve
def evaluate(candidate_set):
    # 优先级函数：决定如何选择下一个点
    pass

@funsearch.run
def run(specification):
    # 运行并评估完整程序
    pass

2. 程序数据库（Programs Database）

3. LLM 提案 + 评估器筛选

4. 核心代码模块

仓库的 implementation/ 目录实现了 FunSearch 的核心逻辑：

文件	职责
`funsearch.py`	主流程：加载规范 → 初始化数据库 → 主循环（采样→LLM→评估→入库）
`programs_database.py`	种群数据库：岛屿模型、多样性采样、程序评分管理
`sampler.py`	从数据库中采样历史程序，构建 LLM 提示词
`evaluator.py`	执行候选程序，验证结果正确性
`code_manipulation.py`	解析和修改 Python 代码（处理 @funsearch 装饰器）
`config.py`	配置参数：种群规模、岛屿数、每轮采样数等

震惊数学界：从 Cap Set 到 Bin Packing 的多项突破

Cap Set 问题：20 年来最大的突破

Cap Set 问题是极值组合学的核心问题之一——在 n 维向量空间 F_3^n 中，找到最大的"无直线点集"。 Terence Tao 曾将其描述为他"最喜爱的开放问题"。

"FunSearch 生成的解决方案远比数字列表要丰富得多。当我研究它们时，我能学到新的数学思想。"

Bin Packing 问题：超越人类设计的启发式算法

Bin Packing（装箱问题）是计算机科学中的经典问题：将不同大小的物品装入最少数量的箱子。广泛应用于物流集装箱装载、数据中心任务分配等场景。

2024 年 12 月更新：竞赛编程的 AI 搭档

上手体验：零安装，一键 Colab

对于想要深入研究底层实现的开发者，implementation/ 目录提供了完整的单线程核心代码：

git clone https://github.com/google-deepmind/funsearch.git
cd funsearch
# 打开任意 problem/*.ipynb 即可开始

不过需要注意的是：核心代码本身不包含 LLM 调用接口和沙箱隔离环境。完整的生产级 FunSearch 系统还需要：

一个支持代码生成的 LLM API（如 Gemini API）
一个安全的代码执行沙箱（防止 LLM 生成恶意代码）
分布式任务调度基础设施（implementation/ 是单线程的，真实大规模运行需要分布式扩展）

技术评价：优势与局限

优势

真正的创造性发现：不同于 LLM 的知识检索，FunSearch 能够生成此前不存在的、新颖的数学算法，在 Cap Set 等开放问题上实现了人类数学家未曾做到的突破。
可解释性强：输出的是可读的 Python 程序，而非黑箱模型权重。这意味着数学家可以分析、学习并进一步改进这些"AI 发现"的算法。
泛化能力强：同一套框架在 Cap Set（纯数学）和 Bin Packing（应用算法）两个截然不同的领域都取得了最先进结果，说明方法具有通用性。

局限

依赖问题规范的质量：FunSearch 的效果很大程度上取决于用户编写的规范文件——即问题建模的质量。坏的规范会导致搜索无法收敛。
需要自动化评估器：并非所有问题都能轻松设计自动化评估器。对于难以自动验证答案正确性的问题（如开放式数学证明），FunSearch 的适用性受限。
计算资源要求高：虽然 implementation/ 是单线程的，但完整的 FunSearch 需要 LLM 推理（涉及 API 调用成本）和大量程序评估（计算密集），实际使用需要相应资源支撑。

行业意义：AI for Science 的里程碑

项目基本信息

项目	信息
组织	Google DeepMind
GitHub Stars	1,094
编程语言	Jupyter Notebook / Python
开源协议	Apache License 2.0
发表期刊	Nature (2023)
核心依赖	LLM API（如 Gemini 1.5 Flash、PaLM 2）
运行方式	Google Colab / 本地 Python
最新更新	2024 年 12 月（竞赛编程扩展）