🤖 AI

ImprovEvolve: Basin-Hopping Meets LLM-Guided Evolutionary Search

ImprovEvolve 引入了一种由大语言模型（LLM）引导的进化搜索，通过演化出专门的初始化、改进和扰动算子来驱动跳跃过程（basin-hopping），在成功发现六边形堆积、自相关不等式和球面码等领域的新型最前沿解决方案的同时，显著降低了对语言模型的认知负荷。

原作者： Alexey Kravatskiy, Valentin Khrulkov, Ivan Oseledets

发布于 2026-06-30

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Alexey Kravatskiy, Valentin Khrulkov, Ivan Oseledets

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

想象一下你正在试图解决一个极其困难的谜题，比如将特定数量形状怪异的六边形放入一个容器中而不发生重叠，或者寻找一条能使某个值最大化的完美数学曲线。这些都是“优化问题”，它们之所以极其困难，是因为可能的解空间充满了微小的丘陵和深邃的山谷（局部最优解）。如果你走错了一步，你可能会陷入一个浅谷，从而永远无法找到最深的那个。

长期以来，研究人员一直尝试教人工智能（特别是大语言模型，或 LLM）去解决这类谜题，方法是要求 AI 写出一个单一的、庞大的程序，让它一次性完成所有工作：它必须弄清楚从哪里开始、如何移动以及何时停止。这就像是要求一位厨师不仅要烹饪一顿饭，还要同时设计厨房、发明新的餐具并编写整本食谱。这篇论文称这种方法为“AlphaEvolve”。虽然它有时有效，但往往会让 AI 感到力不从心，导致生成的方案笨拙或不完整。

新思路：ImprovEvolve

作者 Alexey Kravatskiy 及其同事提出了一种更聪明的方法，称为 ImprovEvolve。他们不再要求 AI 从零开始构建整个“超级优化器”，而是将任务分解为三个小巧、易于管理的任务。他们要求 AI 编写一个包含三种特定工具的“工具箱”：

启动器 (generate_config)： 一个仅负责创建一个随机且有效的初始点的工具。
打磨器 (improve)： 一个将混乱的解进行微调并使其变得稍好的工具，用于平滑边缘。
摇晃器 (perturb)： 一个通过随机抖动解来观察是否通过“摇晃”能让其落入更深、更好的山谷中的工具。

“盆地跳跃”之舞

在 AI 构建好这个工具箱后，研究人员并不仅仅是运行它一次。他们使用了一种经典的数学策略，称为盆地跳跃（Basin-Hopping）。你可以把它想象成一名徒步旅行者试图在雾气缭绕的山脉中寻找最低点：

开始： 徒步者投下一个随机位置（使用“启动器”）。
打磨： 他们向着最近的谷底走下去（使用“打磨器”）。
摇晃： 他们进行一次大幅度的随机跳跃（使用“摇晃器”）到一个新位置，希望能落在另一个更深的谷底。
重复： 如果新位置更低，他们就留在那里。如果不是，他们可能会再试一次。他们一遍又一遍地这样做，随着越来越接近底部，跳跃的幅度也会逐渐减小。

通过将“思考”（AI 所做的）与“搜索”（盆地跳跃循环）分离，AI 只需要专注于做好一件特定的事情。这降低了 AI 的“认知负荷”，就像人类在处理复杂问题时，如果将其分解为小步骤而不是试图一次性在大脑中处理整个过程，效率会更高一样。

结果：刷新纪录

论文在三个非常艰深的数学挑战上测试了这种方法：

六边形堆积： 想象一下尝试将 11、12 甚至 23 个六边形装进尽可能小的六边形盒子中。新方法为其中几个数字找到了新的世界纪录堆积方案，击败了以往由其他 AI 系统甚至人类专家创造的纪录。
自相关不等式： 这是一个关于寻找完美波形形状的复杂数学问题。AI 将已知的数学极限（“下界”）从 0.96102 提高到了 0.96258。这是通过利用之前 AI 发现的一个优秀解，并使用新的“打磨器”工具进行进一步精炼实现的。
球面码： 这涉及在球面上排列点，使它们尽可能远离（就像石榴籽一样）。新方法在 90 个不同测试用例中的大多数情况下都改进了排列方式，找到了比以往任何已知配置都更高效的配置。

人类的触感

有趣的是，论文指出，虽然 AI 完成了繁重的体力活，但一位人类专家对代码进行了几次微小的调整（例如更改了特定的设置或更换了某种数学工具）以获得绝对最佳的结果。这表明，最好的结果来自于一种协作关系：AI 生成核心结构和逻辑，而人类提供 AI 可能忽略的最终“微调”。

总结

该论文认为，与其要求 AI 成为一个“超级天才”去一次性解决整个问题，不如要求它成为一个“专家”，去构建一套工具。然后，我们利用这些工具通过智能的迭代循环（盆地跳跃）来探索解空间。这种方法——ImprovEvolve——被证明比以往那些试图包揽一切的方法更有效、更稳健，并且能够发现新的数学纪录。

技术摘要：ImprovEvolve：盆地跳跃法与 LLM 引导的进化搜索

问题陈述

本文探讨了利用大语言模型（LLM）解决复杂数学优化问题的挑战，特别是针对具有崎岖、非凸且非光滑景观（如装箱问题、泛函不等式和球面码）的问题。虽然之前的研究如 AlphaEvolve 成功进化出了直接输出候选解的单体程序，但作者认为这种方法给 LLM 带来了过高的认知负荷。模型必须同时设计初始化方案、搜索策略和终止条件，这往往导致生成的程序依赖于现成的常规程序（如 L-BFGS-B），而这些程序无法有效处理特定约束和非凸性。因此，LLM 生成的解决方案往往是将数学洞察与启发式算法混合在一起，而非严谨地解决优化任务，并且难以泛化到未见的题目规模，也难以超越专家构建的解。

方法论：ImprovEvolve

作者提出了 ImprovEvolve，这是一种算法替代方案，它将优化任务分解为专门的子程序，有效地将 盆地跳跃（Basin-Hopping） 全局优化技术与 LLM 引导的进化搜索相结合。

核心分解

ImprovEvolve 不再进化一个输出解的单一函数，而是进化一个实现三个不同算子的 Python 类：

generate_config(seed)：从随机种子初始化一个可行解。
improve(x)：执行局部优化以精炼配置 $x$ ，返回一个适应度至少不低于 $x$ 的解 $x'$ 。
perturb(x, \sigma)：在特定的强度 $\sigma$ 下随机探索搜索空间。

验证方案（盆地跳跃）

进化的类被用于一个两阶段验证方案（算法 1）中，该方案模拟了单调盆地跳跃（Monotonic Basin-Hopping, $T=0$ ）：

阶段 A（初始化）： 生成多个初始配置并通过 improve 进行精炼。选择最优结果作为起点 $x^*$ 。
阶段 B（迭代搜索）： 算法执行 $R$ $R$ 轮扰动和改进。在每一轮中，扰动强度 $\sigma$ $σ$ 从 $\sigma_{max}$ $σ_{ma x}$ 几何级数衰减至 $\sigma_{min}$ $σ_{min}$ 。过程包括：
1. 扰动当前最优解： $x' = \text{perturb}(x^*, \sigma)$ 。
2. 精炼扰动后的解： $x'' = \text{improve}(x')$ 。
3. 单调接受： 仅当适应度严格提高时，才将 $x^*$ 更新为 $x''$ 。

这种分解将 LLM 的任务从设计端到端的优化器转变为编码特定领域的启发式算法（用于初始化、局部搜索和探索），随后由经典的盆地跳跃框架进行编排。

进化框架

该系统利用 GigaEvo 框架配合 MAP-Elites 循环。候选程序的适应度通过在其上运行完整的两阶段验证方案来确定。LLM（初始化使用 Gemini 3 Pro，进化使用 Gemini 3 Flash）根据适应度反馈和谱系见解对 Improv 类的代码进行变异。

关键贡献与结果

1. 六边形装箱 (HEX $n$ )

任务： 将 $n$ 个单位正六边形装入最小的包围正六边形中。
结果：
- 对于 $n=11$ ，ImprovEvolve 发现了一个新的 SOTA（最先进）装箱状态，其边长 $L=3.9245$ ，优于 AlphaEvolve 的 $3.9301 $和之前的真人纪录$ 3.9434$。
- 进化的程序无需重新进化即可泛化到未见的题目规模（ $11 \le n \le 24$ ），并发现了 $n=12, 15, 16$ 的新 SOTA 装箱。
- ImprovEvolve+E： 通过少量的专家编辑（更换优化器、调整惩罚权重），该系统发现了 $n=14, 17, 23$ 的新 SOTA 装箱，并为 $n=25-30$ 提供了此前不存在结果的结构化装箱。
对比： ImprovEvolve 显著优于 GigaEvo 基准（单体方法），后者由于重叠错误，在 $n > 11$ 时无法泛化。

2. 二阶自相关不等式 (ACI 2)

任务： 寻找一个非负函数 $f$ ，使不等式 $\|f * f\|_2^2 \le C_2 \|f * f\|_1 \|f * f\|_\infty$ 中的常数 $C_2$ 最大化。
结果：
- 基础 ImprovEvolve 程序实现了 $C(f) = 0.9512$ ，超过了开源基准，但未能达到 AlphaEvolve 的 $0.96102$。
- ImprovEvolve+E： 通过从 AlphaEvolve 的解开始恢复优化并应用人工引导的编辑（将分辨率进度提升至 1.6M 步，移除下限裁剪），该系统达到了新的 SOTA 下界 $C(f) = 0.96258$ 。
意义： 这证明了该框架能够精炼由专家或其他模型提供的现有高质量解，而这是单体 LLM 方法难以具备的能力。

3. 球面码

任务： 在单位球面 $S^{d-1}$ 上排列 $N$ 个点，以最小化最大两两内积（相干性）。
结果：
- 在来自 Cohn 目录的 90 个多样化配置（ $d \in [8, 16]$ ）上进行了评估。
- ImprovEvolve++（一个在多维空间中进化的校准通用改进器）严格降低了 90 个配置中 53 个的最大余弦值，实现了 0.1765% 的平均相对提升。
- 这比之前的最佳程序（ImprovEvolve）提升了 2.35 倍。
- 诊断结果（UMAP 和内积分布）显示，ImprovEvolve++ 执行了全局结构重排，将点移动到搜索空间的截然不同的区域，而其他变体仅进行局部调整。

统计稳健性

多次运行研究确认，与 GigaEvo 基准相比，ImprovEvolve 的改进具有统计学显著性（ $p < 0.05$ ），验证了模块化分解相比于学习单体优化器具有可重复的优势。

意义与主张

论文声称，将优化任务分解为模块化子问题是 LLM 引导发现的关键原则。

降低认知负荷： 通过分离初始化、局部改进和扰动，LLM 专注于编码数学结构和启发式算法，而非编排整个搜索过程。
人机协作： 模块化接口允许领域专家进行有针对性的、最小限度的编辑（例如，更改优化器、调整分辨率进度表），从而显著提升性能，弥合了 LLM 生成的代码与专家级调优之间的差距。
泛化能力： improve/perturb 接口使进化的程序能够泛化到未见的题目规模，并能从专家提供的解中恢复优化，克服了单体端到端程序的脆弱性。

作者将这项工作定位为迈向扩展 LLM 驱动的数学发现的一步，并指出未来的系统应结合此类定制的分解方式与能够自主决定精炼哪些模块的智能体工作流。该论文在广泛泛化性方面保持了谦逊，指出目前的定量评估仅限于这三个特定的优化领域。