Funsearch记录与分享

0.引言

  funsearch是课程的大作业，需要做相关的代码项目，所以去阅读了funsearch的初始论文。这次记录主要是为了个人学习用的，以及防止未来忘了原理要从0重新看论文。如有错误，还请多多指教。之后如果我有新的理解或者发现记录的一些错误，可能也会回来修改。

1.背景

  funsearch是指searching in the function space，也就是在函数空间内进行搜索。简单来说，它是让训练好的大语言模型将初始代码不断地进化，最终选出得分最高的代码。funsearch寻找的是描述如何解决问题的程序，而不是答案本身。

  以capset问题为例：

  Capset 问题（上限集问题）的核心是：在三元域$F^n_3$ 的高维空间中，寻找不包含任何“三点共线/三项等差数列”的最大子集的大小。

  每个点坐标为(x1,x2,……xn)，$x_i$的取值为{0，1，2}。capset问题就是在一个$3^n$大小的集合里，找出满足要求的最大子集的大小。

n=3时情况如下，一共只有9个点，满足要求的最大子集大小为4

图1

  Capset 问题目前没有确定的精确解，它仍然是一个开放问题；但它的地位很高，是加法组合学和极值组合学中的经典模型问题，也被陶哲轩称为自己最喜欢的开放问题之一。

Funsearch基本流程：

1、选定代码骨架、评估函数、一个已经训练好的大语言模型LLM

2、岛屿初始化：选定岛屿数量，每个岛屿一开始各自放一个相同的代码骨架，每个岛屿都会针对代码骨架持续进化

3、进化方式：每次随机选择一个岛屿，从岛屿里选择代码，作为提示词输入llm，llm再生成代码放回同一个岛屿里

4、淘汰方式：每隔一段时间，都会淘汰分数最低的一半岛屿，然后从存活岛屿里选择程序，让他们在空岛屿上继续播种

5、停止迭代：当代码的总数量达到设置值时，或者找到满足要求的代码时，程序就停止进化了。

图2

  funsearch的每个模块之间都是异步通信的。LLM对岛屿的进化是持续进行的，而programs database里的岛屿淘汰是每隔一段时间进行，不会相互冲突、相互等待。

  FunSearch 和常规问题解决方法的一个重要区别是，它返回的不是某个具体问题的答案，而是一段可以构造答案的程序。相比端到端训练的深度神经网络，FunSearch 的可解释性通常更强，因为神经网络往往难以清楚说明内部是如何得到答案的，而 FunSearch 输出的是一段人类可以阅读、验证和修改的代码。这些代码在某些问题上可能比人类已知的启发式规则效果更好，人类也可以反过来从中学习新的构造思路，并进一步优化。

  那么问题来了：既然直接用llm可以返回代码，funsearch也是利用llm返回代码，那我为什么不直接问llm呢？   区别在于：直接问llm其实相当于一次性采样，没法被反复比较和验证，llm的幻觉和随机性没有被系统性过滤掉。而funsearch是把llm放进一个闭环的进化系统里，llm负责"变异"，评估函数负责”自然选择"，即使 llm90% 的输出是错的也没关系，只要偶尔有一次灵光一现，评估器就能把它捕捉并保留下来。

2.代码骨架与评估函数

图3

  以capset为例，图3为代码骨架，funsearch只需要利用llm不断优化priority函数就行了。需要注意的是，代码骨架至少得是一个能算出结果的最低配版本，不能纯留白或报错。

  图3的代码其实也给出了评估函数，主要有2个标准：

1、代码给出的答案是否满足capset要求的子集定义，不满足则直接丢弃

2、满足要求，则记录子集大小。

3.岛屿进化

个人觉得这是funsearch里最核心的模块。

1）选择

  每轮循环只对一个岛屿进行进化，均匀随机选择一个岛屿，保证每个岛屿都有进化的机会。之后再在岛屿里选择k个代码，这里k取2。

  实际上岛屿上有很多的代码，而不同的代码会按签名signature聚类，相同签名的代码会聚类在一起作为一个簇。代码的签名，是一个包含该代码在“每一个输入”上的“得分”的元组（Tuple）。比如，capset问题中，输入的n取值分别为(4,5,6,7)时，输出都为(5,5,5,5)的代码都分到同一个簇里，输出结果我瞎编的，大致是这么个意思。相当于在一个班级里，把考试分数相同的学生分到同一个小组里。

  一个岛屿里有那么多的簇和代码，我们要怎么在里面选择2份代码呢？论文里给出的方法是按概率采样，倾向于选择平均分比较高的簇，在簇内倾向于选择代码长度比较短的代码。由于要选择2份代码，所以要采样两次，因为是按概率采样，所以选到代码会有所不同。

——对于岛内选簇：

图4

$P_i$是每个簇被选择的概率，概率越大，被选择的可能性越高。$s_i$一般是一个簇内所有代码的平均分。

$T_{cluster}$是所有簇的一个共同温度，主要用来控制采样，倾向于选局部最优，还是倾向于探索不同的可能。$T_{cluster}$比较大时，概率分布比较平滑，采样时更愿意尝试不同的可能；$T_{cluster}$比较小时，概率分布比较尖锐，采样倾向于精准捕捉局部最优的簇。

$T_0$是一个人为设定的初始值。n是岛屿内的代码数量。N是控制温度循环变化的周期，mod是取余的操作。随着n增大，$T_{cluster}$越来越小，岛内对簇的选择倾向，从探索不同的可能，转化为更容易选取概率最大的簇，随着n到达N的倍数，取余后$T_{cluster}$又重新变成$T_0$了，重新新一轮温度衰减。

——对于簇内选代码：

图5

$\ell_i$是第i份代码的长度取负。比如第i份代码有5个字符，那么$\ell_i$=-5。

$\tilde{\ell}i$是第i份代码的归一化长度，而exp($\tilde{\ell_i}$ / $T{program}$)则将归一化后的长度映射为权重，代码长度越短，权重越大。而概率公式可以参考图4的形式。

$T_0$和$T_{cluster}$的值一般都设为0.1。

2）进化

图6

在选择阶段，我们进行2次采样，分布得到2份代码。这2份代码可以作为提示词prompt输入给LLM，格式可以入图6所示。

2份代码按得分从低到高排列，依次为v0和v1。把v0和v1拼接在一起，再贴上一个空函数v2，组合成一个全新的prompt输入给LLM。LLM会生成多份代码，对每个代码进行评估。连capset子集要求都不满足的直接淘汰，满足要求的代码保留下来，放进原来的岛屿里，在岛屿内又根据signature分进对应的簇里。

4.岛屿淘汰

从进化过程来看，岛屿里代码的数量是会越来越多的，任由这样发展下去，电脑的内存可能会被挤爆，所以需要引入优胜劣汰的机制。比如每隔4个小时，清理得分最低的一半岛屿，岛屿并不是没了，而是里面的代码被清空了。岛屿的分数取决岛屿内代码的最高分。被情况的岛屿。

被清空的岛屿需要从幸存的岛屿里选择种子进行播种。每个被清空的岛屿各自随机挑选一个幸存的岛屿，从幸存岛屿中选择最高分的代码作为种子（两个一样得分的代码，就看谁是最早进入这个岛屿），重新参与进化的过程。

图7是每个岛屿进化、淘汰、播种，再重新进化的过程，不过这图没有把簇画出来，蓝色的点指的是代码。

图7

5.迭代结束之后

迭代结束之后，从所有岛屿里，选择在训练集里得分最高的冠军代码，在测试集里验证这份代码泛化能力。也可以像 Nature 原论文作者那样，对funsearch生成的代码进行人工阅读与提炼，解析其内在逻辑，并将其作为人类可读的启发式规则部署到实际中

论文在挑战极难的直接构造 n=8 维 Cap Set 问题时，进行了 140 次相互独立的完整实验，最终仅有 4 次成功突破历史记录。这种多轮独立实验的设计，极大地验证了 FunSearch 的稳定性，也体现了自动启发式设计在面对海量解空间时的真实效能。