利用进化算法优化IBP约化种子策略：从遗传算法到Funsearch的实践

1. 项目概述与核心挑战

在粒子物理理论的高阶计算中，费曼积分的计算是一个绕不开的核心环节。简单来说，当我们计算一个物理过程到更高精度时，会得到大量结构复杂、难以直接计算的积分。IBP（分部积分）约化技术，就是将这些“复杂积分”用一组数量少得多的“基础积分”（称为主积分）线性表达出来的数学过程。这就像把一屋子杂乱无章的乐高零件，整理归类成几十种标准件，后续的计算就只需要处理这些标准件了。

然而，这个“整理归类”的过程计算量极其巨大。传统的IBP约化方法，比如矩形播种（Rectangular Seeding），需要生成并求解一个包含数万甚至数十万个方程的线性系统，消耗的CPU时间动辄以十万小时计，已经成为许多前沿精度计算的瓶颈。问题的症结在于“种子”的选择。种子，就是我们在生成IBP方程时，所选取的那些具有特定指数组合的积分。选多了，方程系统庞大，求解慢；选少了，方程系统不完整，无法完成约化。因此，一个高效的“播种策略”至关重要，它直接决定了约化过程的效率。

近年来，领域内发展出了一些启发式策略，如“黄金法则”和“改进播种”，它们通过引入对传播子重复数、分子幂次等参数的约束，显著减少了所需种子的数量。但一个根本性问题依然存在：是否存在一个理论上“最优”的播种策略？我们能否找到一组最精简的种子集合，既能保证约化完整性，又能将计算开销降到最低？这正是我们本次探索的起点。

面对这个组合优化问题，我们决定跳出传统的手工设计范式，尝试让机器自己来“寻找”好策略。我们选用了两圈三角-箱图积分作为测试基准，目标是将积分I(1,1,1,1,1,1,-3)约化到其16个主积分。我们先后尝试了三种基于进化思想的算法：传统遗传算法、基于大语言模型的Funsearch，以及强类型遗传编程。本文将详细拆解这三轮探索的过程、结果与背后的思考，希望能为计算物理领域面临类似组合优化问题的同行，提供一条切实可行的自动化策略搜索路径。

2. 背景知识：IBP约化与进化算法基础

在深入我们的实验之前，有必要先厘清两个核心概念：IBP约化到底在做什么，以及我们将要使用的进化算法是如何工作的。

2.1 IBP约化与种子策略详解

一个L圈、E条外线的费曼图，对应的积分族通常由一组分母因子D_i（传播子）和可能的分子因子（不可约标量积，ISP）来参数化，用一组整数(a1, a2, ..., an)来标记，其中ai>0对应分母，ai<0对应分子。

IBP恒等式的核心思想源于一个简单的观察：在维度正规化下，一个对圈动量k^μ的全空间导数的积分应为零。即：0 = ∫ [d^D k] ∂/∂k^μ ( q^μ / ∏ D_i^{a_i} )其中q^μ是IBP矢量，通常取为圈动量或外动量。将这个导数展开，就会得到一系列指数ai被增减的积分之间的线性关系。对所有可能的IBP矢量（本例中为2个圈动量×4个独立动量基，共8个）和洛伦兹不变性生成元应用此操作，就能得到一组庞大的线性方程。

种子策略的演进：

1. 矩形播种：最朴素的方法。设定分子总幂次s ≤ smax和传播子总幂次r ≤ rmax，将所有满足条件的积分(a1,...,an)都作为种子。在我们的基准案例中（smax=3, rmax=7），这产生了14,588个种子。系统庞大，效率低下。
2. 黄金法则：在矩形播种基础上，增加对“点”的约束，即传播子重复数d ≤ dmax（d = Σ(ai-1)，对ai>1求和）。这迫使在约化到传播子数更少的“低阶” sector 时，重复数也不会增加。当dmax=1时，种子数降至2,148。
3. 改进播种：一个更巧妙的启发式。它要求对于传播子数为t的 sector，其分子幂次满足s ≤ t - l + 1，其中l是一个参数。这直观地限制了在低阶 sector 中分子幂次过高的情况。当设定dmax=0（即不允许点），l=4时，种子数骤降至92，相比矩形播种减少了超过两个数量级。

我们的目标很明确：以“能否成功约化目标积分”为有效性标准，以“所用种子数Ns的负值”作为适应度函数f，在这个巨大的组合空间中，搜索能使f最大（即Ns最小）的播种策略。对于无效策略，我们施加一个巨大的惩罚f = -Ns - NR（NR是矩形播种的种子数），以避免算法沉迷于生成空集或极小但无效的集合。

2.2 进化算法家族概览

进化算法是一类受生物进化论启发的全局优化算法，其核心流程是“生成种群 -> 评估适应度 -> 选择 -> 交叉/变异 -> 新一代”。

1. 传统遗传算法：个体的“基因”通常被编码为一个固定长度的二进制串或实数向量。在我们的初代尝试中，一个种子列表就被编码为一个长度为NR的二进制向量，1表示选中该种子。通过选择、交叉（交换基因片段）、变异（翻转比特）来迭代进化。
2. 遗传编程：这是遗传算法的进阶版，个体的“基因”是一个可以执行的程序（通常表示为语法树）。评估适应度就是运行这个程序。通过交换程序的子树（交叉）或随机修改子树（变异）来产生新个体。它的搜索空间更大，能发现人类难以直观设计的复杂规则。
3. Funsearch：可以看作是一种特殊形式的遗传编程，由DeepMind团队提出。其革命性在于两点：第一，它用Python源代码文本作为程序表示，而不是语法树；第二，它的“变异”和“交叉”操作由一个大语言模型来完成。你给LLM看两个表现较好的程序（v0,v1）和一个待补全的程序框架（v2），LLM会基于前两者的“智慧”生成v2的新代码。这使得Funsearch特别适合探索性工作，因为你不需要为问题专门设计遗传操作符，LLM会尝试理解代码逻辑并生成新的变体。

我们的实验路线图正是沿着这个从传统到前沿的脉络展开：先用简单的遗传算法建立基线，再用Funsearch进行“黑盒”探索，最后利用从Funsearch中获得的洞见，设计一个更专业、更高效的强类型遗传编程方案。

3. 初探：传统遗传算法的局限

我们的第一次尝试尽可能保持简单和通用，以验证问题的难度并建立一个性能基线。

3.1 算法设计与实现

我们将问题建模为一个二进制优化问题。对于一个给定的矩形播种列表（例如rmax=7, smax=3下的 14,588 个候选种子），一个播种策略直接对应一个长度为NR的二进制向量。向量中第i位为 1，表示选择第i个种子；为 0 则表示不选。

种群初始化：随机生成一定数量（100-500）的个体，每个比特位以50%的概率随机设置为0或1。这意味着初始策略平均会包含一半的种子。

适应度评估：使用Kira初始化并求解在单个运动学点上生成的IBP系统。如果系统能成功将目标积分约化为16个主积分，则适应度f = -Ns；否则，f = -Ns - NR - 1。额外的-1是为了确保即使失败，使用完整矩形播种（Ns = NR）的策略也比任何失败但Ns更小的策略得分更高，防止算法陷入“选择空集”这个简单的局部最优。

遗传操作：

• 选择：采用轮盘赌选择，同时保留历代最优个体（精英保留）。
• 交叉：单点交叉，随机选择一个位置，子代个体由此位置前父本A���片段和此后父本B的片段拼接而成，交叉概率设为90%。
• 变异：以5%的概率随机翻转个体中的某个比特位。

3.2 实验结果与瓶颈分析

在rmax=7（14,588种子）的矩形播种空间中进行搜索，算法在初期展现出了一定的优化能力。通常，初始种群中就能找到一些策略，其种子数量约为矩形播种的一半（约7000个），并且能够成功完成约化。

然而，优化进程很快陷入平台期。在后续上百代的演化中，优化速度变得极其缓慢，每代可能只能减少几十个种子，并且随着种子数降低，优化越发困难。运行100代（约24 CPU小时）后，最优策略的种子数可能仅比初始时减少500个左右，与“改进播种”的92个种子相去甚远。

更令人失望的是，当我们以一个更好的起点（例如，直接以“改进播种”策略对应的二进制向量作为种群初始成员之一）开始时，算法几乎无法做出任何改进。它被困在了这个局部最优解附近。

问题根源：

1. 表示维度灾难：二进制向量的长度高达万位，搜索空间是2^14000级别的天文数字。随机的交叉和变异操作，在如此高维空间中，更像是一种盲目的扰动，难以系统地构造出有意义的模式（如“限制总点数d”或“关联s和t”）。
2. 缺乏问题语义：算法完全不知道“ai”代表什么，不知道“传播子”、“分子”、“点”这些概念。它只是在操作一串毫无意义的0和1。变异操作翻转一个比特，可能对应着随意地添加或删除一个看似无关的种子，无法导向具有明确物理/数学意义的约束规则。
3. 评估成本高昂：每次适应度评估都需要调用Kira求解一次IBP系统，虽然只是在单个点上，但对于数万规模的种群和数百代的演化来说，计算开销依然巨大。

这次尝试明确地告诉我们：对于IBP种子优化这种具有丰富内在结构的问题，传统的、与问题无关的遗传算法效率太低，无法进行深层搜索。我们需要让算法“理解”问题的领域知识，或者采用一种能自动发现领域知识的更强大方法。

4. 突破：基于Funsearch的启发式规则发现

鉴于传统遗传算法的困境，我们转向了Funsearch。它的魅力在于，我们不需要预先设计复杂的基因编码和遗传操作符，只需要提供一个评估函数和一个初始的、可能很简单的“优先级函数”priority(a_list)。这个函数接收一个表示积分指数的列表a_list，返回True或False来决定是否将其选为种子。剩下的，就交给LLM去探索和进化这个函数。

4.1 实验设置与提示工程

我们基于一个开源分支进行了部署，关键配置如下：

• LLM模型：Code Llama 7B，一个专注于代码生成的轻量级模型。
• 运行环境：使用Apptainer进行沙箱隔离，确保自动生成的代码安全运行。Kira求解器在容器外调用，保持环境轻量。
• 评估函数：与之前类似，成功约化则f = -Ns，失败则f = -Ns - NR。
• 初始提示：这是影响Funsearch性能的关键。我们提供了两种起点：
  1. 知识注入起点：我们提供了一个实现了“黄金法则（dmax=1）”的priority函数作为初始v0。这个函数计算了传播子数num_props、分子数numerators和点数dots，并规定dots <= 1。这相当于从一个包含2148个种子的优质策略开始进化。
  2. 空白起点：我们提供了一个总是返回True的priority函数，这相当于从完整的矩形播种（14588个种子）开始。

4.2 进化历程与惊人发现

使用“知识注入起点”的Funsearch表现出了强大的优化能力，其进化过程并非匀速，而是呈现跳跃式进步。

1. 快速突破：Funsearch很快找到了一个仅用444个种子的策略，这已经远优于我们传统遗传算法辛苦优化上百代的结果。
2. 逼近状态：在大约1000代（16小时）后，它发现了一个策略，将种子数减少到214个。分析其生成的代码（图4），它除了限制点数dots=0和分子数num_negs<=1，还引入了一个看似奇怪的约束：a_list中偶数元素的个数不能超过4。这个约束在物理上缺乏直接解释，但在此特定问题上确实起到了筛选作用。
3. 追平业界最优：继续运行至约2400代（总38小时），Funsearch找到了一个仅用92个种子的策略。其代码（图5）显示，它学会了计算nz = sum(a_list)（即所有ai之和），并约束3 <= nz <= 8。回顾第2.1节，在dmax=0（无点）的情况下，改进播种策略的条件s ≤ t - l + 1可以转化为Σai ≥ l-1。这里nz就是Σai（因为ai=0的项不影响和）。Funsearch发现的nz>=3和nz<=8，恰好与l=4时改进播种策略的约束（Σai ≥ 3）以及rmax=6的上限相符。它独立地重新发现了“改进播种”这一人类设计的启发式规则！
4. 超越人类设计：最令人兴奋的结果出现在总计约3800代后。Funsearch找到了一个仅需88个种子的策略（图6），比改进播种的92个还要少。分析其代码，它在继承了92种子策略所有约束（dots=0,num_props>=2,3<=nz<=8）的基础上，增加了一个新条件：num_props >= 4，即传播子数t必须大于等于4。这意味着它主动排除了所有只有3个传播子的 sector 的种子。在我们这个特定的基准问题中，这些3-传播子的种子被证明是冗余的。Funsearch发现了一个针对此问题的、更特化的、性能更优的启发式规则。

4.3 从“空白起点”出发的探索

为了测试Funsearch在缺乏先验知识下的“创造力”，我们进行了从“空白起点”（总是返回True）开始的实验。经过34小时的运行，最佳策略将种子数从14588降低到了476个。

然而，分析其生成的代码（图8）却充满了“诡异”之处：大量冗余的条件判断（如检查连续两个0或两个1），对列表中1和0的个数进行复杂但似乎无物理意义的组合限制。这些规则看起来更像是在对训练数据（即成功的种子列表）进行某种表面模式的过拟合，而没有抓住像“总和约束”、“点数约束”这样的核心数学结构。这导致其优化很快陷入平台期，无法接近更优的解。

4.4 经验总结与局限性

Funsearch的优势：

1. 探索能力强：能够从简单的起点出发，发现复杂、非直觉的启发式规则，甚至超越人类已有设计。
2. 代码可解释：输出是Python代码，我们可以直接阅读、分析其发现的规则，并理解其逻辑（尽管有时逻辑显得古怪）。
3. 无需设计遗传操作：省去了为特定问题设计交叉、变异算子的繁琐步骤，LLM承担了“智能变异”的角色。

Funsearch的局限与实操要点：

1. 提示词至关重要：初始priority函数的质量极大影响搜索效率和最终结果。提供一个蕴含领域知识（如计算dots,num_props）的起点，相当于给LLM一个正确的“思维框架”，能引导其向有物理意义的方向进化。从空白开始，LLM容易陷入“数字游戏”的局部最优。
2. 代码可能包含“废话”：Funsearch生成的代码常常包含无效或冗余语句（例如检查ai < 1/2，而ai是整数，这等价于ai <= 0）。这是LLM基于代码上下文和注释进行补全的特性所致，需要在分析结果时进行清理和提炼。
3. 计算成本高昂：每一代都需要多次调用LLM生成代码并在沙箱中执行评估，虽然种群规模小，但总时间开销依然不小，且严重依赖GPU资源。
4. 策略的泛化性存疑：Funsearch发现的某些最优规则（如“偶数个数限制”、“t>=4”）可能高度针对我们使用的这个特定两圈三角-箱图积分。其普适性需要到更多不同的积分族中进行验证。

尽管有局限，Funsearch成功地为我们指明了方向：除了传统的t, r, d, s约束外，对指数列表a_list的整体和（Σai）以及其中0和1的个数进行约束，可能是构造高效播种策略的关键。这个洞见，为我们下一阶段使用更高效的算法进行定向搜索提供了宝贵的“先验知识”。

5. 优化：强类型遗传编程的定向高效搜索

Funsearch的探索给了我们关键的启发，但它的运行效率还有提升空间。我们决定利用这些启发，转向一个更传统但可高度定制的工具——强类型遗传编程，来进行更快速、更集中的搜索。我们使用了DEAP库来实现这一过程。

5.1 从Funsearch的成果中提炼“基因”

分析Funsearch发现的优秀策略（尤其是92种子和88种子版本），我们可以抽象出一些反复出现或新出现的核心“构件”：

1. 基本约束：dots == 0（无点），num_props >= 2（至少两个传播子，用于排除平凡sector）。
2. 核心启发式：3 <= nz <= 8，其中nz = sum(a_list)。这对应了改进播种的思想。
3. 潜在优化点：num_props >= 4（传播子数下限），count(ai == 1)（等于1的指数个数），count(ai == 0)（等于0的指数个数）。

在强类型遗传编程中，我们需要定义程序的“语法树”节点类型。我们将其设计为返回布尔值的逻辑表达式树。节点类型包括：

• 终端节点：t（传播子数），r（总幂次），d（点数），s（分子幂次），nz（指数和），count1（等于1的个数），count0（等于0的个数），以及整数常量。
• 函数节点：比较运算符（<,<=,>,>=,==,!=），逻辑运算符（and,or,not）。

这样，一个播种策略就可以表示为一棵如(nz >= 3) and (nz <= 8) and (d == 0) and (t >= 4)的语法树。

5.2 算法配置与加速技巧

我们配置DEAP进行强类型遗传编程：

• 种群与岛屿：使用多个“岛屿”（子种群）并行进化，以维持种群多样性，防止早熟收敛。定期在岛屿间迁移优秀个体。
• 选择：采用锦标赛选择，每次随机选取k个个体，保留其中适应度最高的进入交配池。
• 交叉：子树交叉，随机选择父代语法树中的两个节点，交换它们对应的子树。
• 变异：包括“点变异”（随机改变终端节点或常量值）、“子树变异”（用随机生成的新子树替换原子树）和“缩并/膨胀”变异（简化复杂树或增加树深度）。
• 适应度函数：与之前相同。我们额外加强了对“零种子策略”的惩罚（f = -Ns - 2*NR），因为空集是一个容易陷入的、适应度看似不错（Ns=0）但实际无效的陷阱。

关键加速策略：

1. 记忆化评估：由于不同的策略可能会生成相同的种子集合，我们对每个独特的种子集合进行哈希缓存，避免对相同集合的重复Kira调用。
2. 并行化评估：利用多核CPU，同时评估种群中的多个个体。
3. 精英保留：确保历代最优个体不被丢失。

5.3 性能对比与结果

使用从Funsearch经验中提炼出的构件，强类型遗传编程展现出了惊人的收敛速度。

• 收敛效率：在相同的测试案例上，强类型遗传编程仅用了30代左右，就稳定地找到了与Funsearch耗时3800代发现的、88个种子的最优策略等效（甚至相同）的解。计算时间从数十小时缩短到数小时。
• 搜索定向性：因为我们将搜索空间限制在了由有物理意义的变量（t, r, d, s, nz, count1, count0）构成的逻辑表达式内，算法不再需要像Funsearch那样去“猜测”变量名或发现“偶数个数”这种可能偶然有效的特征。搜索更加高效、直接。
• 可解释性与可控性：生成的策略是清晰的逻辑表达式树，没有Funsearch代码中那些冗余的“废话”，更容易被人类理解和移植到实际的IBP代码中。

对比总结：

这次实践清晰地表明：将自动化探索（Funsearch）与基于领域知识的定向搜索（强类型遗传编程）相结合，是一条非常有效的技术路径。Funsearch充当了“侦察兵”，在广阔的未知领域中发现有价值的线索（如关注nz,count1）；然后，我们利用这些线索，构建一个专门的、高效的“工程部队”（强类型遗传编程）进行快速攻坚，最终以更低的成本获得最优解。

6. 总结、应用展望与实操建议

回顾整个项目，我们从最朴素的二进制遗传算法出发，经历了Funsearch的“黑盒”探索惊喜，最终利用获得的洞察，通过强类型遗传编程高效地复现并确认了最优结果。这条技术路线不仅成功地将一个特定IBP问题的种子数从数万个优化到不足百个，更重要的是，它验证了机器学习辅助的启发式发现在计算物理复杂优化问题上的巨大潜力。

6.1 核心发现与通用性讨论

1. 关键约束维度：我们的实验强烈暗示，对于无点（d=0）的IBP系统，指数列表的总和Σai是一个极其重要的约束参数，它与改进播种策略中的参数l直接相关。此外，指数中“1”和“0”的个数也可能包含有价值的筛选信息。
2. 问题特异性：Funsearch发现的88种子策略（t >= 4）是否具有普适性？很可能没有。它很可能是针对我们这个特定两圈三角-箱图积分拓扑的“特调”策略。但这正是自动化搜索的价值所在——它可以为每一个具体的积分族，寻找其“量身定制”的最优或近似最优播种策略，而无需人类为每个新问题苦思冥想。
3. 策略的可迁移性：虽然精确的最优规则可能因问题而异，但搜索方法本身是通用的。对于新的积分族，我们可以沿用“Funsearch初步探索 + 强类型遗传编程精调”的流程。甚至可以将从多个问题中学习到的优秀“基因”（逻辑表达式片段）作为一个共享的初始种群或构件库，加速对新问题的适应。

6.2 在实际IBP计算流水线中的集成方案

如何将这项技术落地到日常的费曼积分计算中？我建议以下步骤：

1. 预处理与基准建立：

   • 对于一个新的积分族，首先用传统的“矩形播种”或“改进播种”生成一个完整的种子列表S_full，并确认其能成功约化目标积分。
   • 将此列表S_full以及对应的积分指数向量列表，作为优化算法的输入空间。

2. 快速探索阶段：

   • 编写一个适配的priority函数模板，至少包含计算t, r, d, s, nz, count1, count0的代码。
   • 使用Funsearch（配置一个较小的计算预算，如500代）进行初步探索。目标不是找到最优解，而是观察Funsearch倾向于生成哪些新的约束条件。关注输出代码中新出现的变量或组合条件。

3. 定向优化阶段：

   • 根据Funsearch的探索结果，更新强类型遗传编程的“终端节点”集合。例如，如果Funsearch频繁使用count(a_list[i] == 1 and a_list[j] == 1)这样的条件，可以考虑加入“相邻指数对是否为1”这样的定制终端节点。
   • 运行强类型遗传编程，种群规模可设为100-200，岛屿数4-8，进化50-100代。由于其高效性，这通常能在可接受的时间内（数小时）收敛到一个稳定解。

4. 验证与部署：

   • 将遗传编程得到的最优逻辑表达式，翻译成你所用IBP代码（如Kira, FIRE, LiteRed）支持的种子筛选条件。
   • 至关重要的一步：必须在多个、不同的运动学点上验证新策略的完备性。单点验证（如我们一直做的）可能因为偶然性而漏检。至少应在2-3个随机生成的运动学点上进行测试，确保都能成功约化到正确数量的主积分。
   • 将验证通过的策略集成到自动化计算流程中。

6.3 避坑指南与经验之谈

1. 评估开销是主要瓶颈：无论是Funsearch还是遗传编程，适应度评估（调用Kira）都是最耗时的部分。务必实现种子集合的哈希缓存，这能轻易减少一个数量级的冗余计算。
2. 警惕过拟合：算法找到的策略可能极度优化于你的“训练数据”——即那个特定的积分和特定的(smax, rmax)边界。在应用策略到更高rmax或smax的问题，或者另一个积分族时，必须重新验证。自动化搜索找到的是“特解”，而非“通解”。
3. Funsearch的代码清洁：Funsearch输出的代码需要人工审查和简化。删除所有冗余和无效条件（如对整数判断x < 1/2），提取出核心逻辑。这个过程本身也能加深你对有效约束的理解。
4. 参数空间的选择：在我们的案例中，我们固定了smax=3。在实际应用中，你可能需要将smax也作为一个可优化参数，或者针对不同的smax分别寻找最优策略。这会使搜索空间更大，但框架依然适用。
5. 从简单开始：如果你的积分非常复杂，初始的矩形播种列表NR可能极大（数十万）。直接在此空间上搜索可能非常缓慢。一个实用的技巧是：先在一个缩小的空间（例如，用较大的dmax或较小的l预筛选）中找到好策略，再以此策略为起点，在完整空间中进行微调。

6.4 未来可能的延伸

本次研究只是一个起点。基于此框架，还有许多值得探索的方向：

• 多目标优化：目前我们只优化了种子数量Ns。实际上，IBP求解时间不仅与方程数量有关，还与方程的稀疏性、数值稳定性等有关。可以设计一个综合考虑Ns和方程求解预估时间的复合适应度函数。
• 与符号学习结合：能否将学到的优先级函数priority(a_list)表示为一个可解释的符号公式？或许可以结合符号回归技术，将语法树或代码压缩为更简洁的数学不等式。
• 跨问题迁移学习：建立一个不同积分族最优策略的数据库。当面对一个新问题时，首先在数据库中寻找拓扑结构或代数结构相似的问题，将其策略作为初始种群，可以极大加速进化过程。

最终，这项工作的价值在于提供了一种范式：将计算物理中那些依赖经验、启发式的“手艺活”，转化为一个可自动化、可优化的工程问题。通过让机器去探索那些庞大而反直觉的组合空间，我们或许能一次次地突破那些由人类直觉设定的效率边界，让高精度计算走得更远。