FunSearch（即函数空间搜索的简称）是由Google DeepMind开发的一种人工智能方法，用于发现解决数学和算法问题的计算机程序。它结合了大型语言模型、自动化评估器和进化搜索流程，生成候选程序、对其进行评分，并利用高性能程序来产生新的候选。该系统于2023年公布，相关论文发表在《自然》期刊上，并已应用于极值组合学和在线装箱问题。
FunSearch代表了大型语言模型用于发现任务方式的一种转变。它并非直接生成答案，而是将问题框架化为对计算机程序的搜索，使模型能够提出代码，然后对这些代码进行严格测试。这种方法利用了诸如Generative AI中使用的模型的生成能力，同时确保输出是可验证的，并且通常能被研究人员解释。
方法
FunSearch通过迭代生成和评估候选程序来运作。用户提供问题规范、评估函数和初始程序框架。在每一步中，系统从数据库中采样现有程序，优先选择得分较高的程序，并为预训练的大型语言模型构建提示。模型生成一个修改后的程序，然后由评估器执行并评分。有效的程序被添加回数据库，使搜索能够建立在先前成功的基础上。
该搜索使用基于岛屿的进化方法来维持候选程序之间的多样性，降低收敛到局部最优的风险。正如原始论文所指出的，一个关键优势是FunSearch输出的程序可以被研究人员检查、简化和解释，而不仅仅是提供最终数值答案或大量对象列表。
算法表述
FunSearch可以被描述为对程序片段空间的搜索，这些片段通常是嵌入在固定框架中的函数。设\(\mathcal{F}\)为候选函数空间，\(S: \mathcal{F} \to \mathbb{R}\)为通过运行调用候选函数的固定求解器获得的评估器得分。给定初始函数\(f_0\)，FunSearch维护一个已评估的有效函数数据库\(D\)。它反复从\(D\)中采样高分函数，用它们为大型语言模型构建提示，并要求模型生成新的候选函数\(f'\)。新函数在问题特定框架内执行并评分。如果有效，则将其添加到\(D\)中，使后续提示能够基于更强的候选进行构建。
理想目标是找到具有高评估器得分的候选函数，\(f^* \in \arg\max_{f \in \mathcal{F}} S(f)\)，尽管在实践中FunSearch返回搜索过程中发现的最佳有效函数。原始实现使用基于岛屿的进化过程来保持多样性，同时偏向于得分更高的程序。
应用
帽集问题
FunSearch首次在帽集问题上得到演示，这是加法组合学中的一个问题，涉及\(\mathbb{Z}_3^n\)中无三点共线的最大可能子集。在维度8中，FunSearch找到了大小为512的帽集，改进了先前已知的构造。该论文还通过发现与可容许集相关的构造，报告了帽集容量的改进下界。Google DeepMind将该结果描述为使用大型语言模型在数学中生成可验证新知识的一个例子。《自然》新闻文章报道称，该系统在与纸牌游戏Set相关的组合学问题上改进了人类的努力。
在线装箱
FunSearch还应用于在线装箱问题，其中物品到达时必须被分配到箱子中。在这种设置下，FunSearch进化出程序化启发式规则，决定新物品应放入哪个箱子。原始论文报告称，发现的启发式规则在模拟数据和OR-Library基准实例上优于常见的最先适应和最佳适应基线。
软件
Google DeepMind在公共GitHub仓库中发布了FunSearch软件，允许研究人员复现结果并将该方法应用于其他问题。该发布包括进化搜索的代码、评估器接口以及帽集和装箱问题的示例。这种开放可用性支持了Machine learning和Artificial intelligence领域的进一步实验。
意义
FunSearch因其将大型语言模型与进化计算相结合而引人注目，这一方向在更广泛的Deep learning领域已受到关注。通过生成可解释的程序，它为AI系统提供了一条路径，使其不仅能解决问题，还能提供人类可以理解并在此基础上构建的见解。该方法已在Google DeepMind更广泛的AI应用于科学发现的努力背景下被讨论，与Generative AI中的其他举措并列。
尽管FunSearch在特定数学和算法任务上显示出潜力，但其普遍适用性仍是一个活跃的研究领域。对预训练语言模型的依赖以及对明确定义评估器的需求，可能限制其在其他领域的应用。尽管如此，该方法激发了关于使用语言模型进行程序合成和优化的进一步工作，为AI研究的不断演变格局做出了贡献。