谷歌DeepMind在数学AI领域再次取得突破。其研发的AlphaEvolve系统，通过大语言模型（LLM）驱动的代码进化，一次性改进了五个经典拉姆齐数（Ramsey number）的下界，打破了其中一些尘封十年的纪录。
论文地址：https://arxiv.org/pdf/2603.09172
这项成果并非依靠人工设计五套不同算法，而是通过一个统一的“元算法”（meta-algorithm）自动完成的。该元算法能自主发现针对特定拉姆齐数问题的搜索流程。
具体突破如下：
- R(3,13)： 60 → 61（此前纪录保持11年）
- R(3,18)： 99 → 100（此前纪录保持20年）
- R(4,13)： 138 → 139（此前纪录保持11年）
- R(4,14)： 147 → 148（此前纪录保持11年）
- R(4,15)： 158 → 159（此前纪录保持6年）
在拉姆齐数这个组合数学的经典难题上，即使是微小的推进也极其困难。AlphaEvolve不仅创造了五项新纪录，还成功匹配或恢复了所有已知精确值的拉姆齐数下界，以及大量其他情况下的当前最佳下界，总共覆盖了28个R(r,s)值。
DeepMind的研究负责人Pushmeet Kohli在社交媒体上分享了这一进展。
DeepMind联合创始人兼CEO Demis Hassabis也对此表示祝贺，称这是“人工智能在数学领域的一个重大里程碑”。
图灵奖得主Yann LeCun同样向团队表达了祝贺。
拉姆齐数为何如此困难？
拉姆齐理论的核心问题之一是确定拉姆齐数 R(r, s)。简单来说，它指的是：对于一个足够大的完全图，无论你如何对其边进行着色（比如红色或绿色），都必然会出现一个全是红色的 r 个顶点的完全子图，或者一个全是绿色的 s 个顶点的完全子图。
最著名的例子是 R(3,3)=6，即“六人集会问题”：在任何六人中，总能找到三人彼此都认识，或三人彼此都不认识。
然而，随着 r 和 s 增大，确定精确的拉姆齐数变得异常困难。著名数学家保罗·埃尔德什（Paul Erdős）曾用一个生动的比喻描述其难度：如果外星人威胁人类必须算出 R(5,5)，否则就毁灭地球，那么人类最明智的选择可能是直接投降。
因为仅 R(5,5) 这一个问题的搜索空间就包含大约 10^271 种可能的图，暴力求解所需的时间远超宇宙年龄。几十年来，数学家们每想在一个具体的拉姆齐数上取得进展，都不得不从零开始手工设计一套定制的搜索算法。
AlphaEvolve 改变了这一范式。它不是一个直接寻找反例图（用于确定下界）的程序，而是一个搜索“搜索算法”的元算法。
AlphaEvolve 如何工作：不算题，算算法
传统路径是：人类专家设计算法 -> 计算机执行算法寻找图。
AlphaEvolve 的路径是：LLM 根据反馈进化算法代码 -> 执行进化出的算法 -> 评估结果并进一步指导进化。
其核心流程可以概括为以下元算法：
Algorithm 1: AlphaEvolve: Ramsey Program Search
Input: Ramsey parameters (r,s,nSoTA)
Output: Program p* with best graph
1 Init: Population P ← {Pbase} // Pbase returns empty graph
2 while compute budget remaining do
3 Pnew ← LLM.Mutation(Select(P))
4 (G1,G2) ← Pnew.run()
5 if G1 has no r-cliques or s-independent sets then
6 v1,v2 ← |V(G1)|,|V(G2)|
7 S ← {4·v1 if v1 > nSoTA
2·v1 if v1 = nSoTA
v1 otherwise}
8 if v2 > v1 then
9 Eviol ← (v2²)/2^(½) + (v2²)/2^(½)
10 S ← S + ½ max(0,1 − count_viol(G2)/Eviol)
11 else
12 S ← −1
13 score(pnew) ← S
14 P ← P ∪ {(pnew,S)}
15 return arg max p∈P score(p)
简单来说：
- 初始化种群：从一个最简单的基线程序（如返回空图）开始。
- LLM变异：从种群中选择表现较好的程序，让大语言模型（如 Gemini）对其进行代码变异，修改搜索策略、初始化方式或启发式规则。
- 执行与评分：运行变异后的程序。如果它能构造出更大的合法图（无r-团且无s-独立集），则获得高分。对于接近合法（违规很少）的图，也会给予奖励，以引导搜索向边界推进。
- 进化迭代：将高分程序加入种群，重复选择、变异、评估的循环。
最终，AlphaEvolve 输出的不是图，而是一段能够找到更好图的代码。
AI 发现的四大算法家族
研究人员对 AlphaEvolve 为 28 个 R(r,s) 值生成的算法进行了归纳，大致可分为四类，其分类依据主要是算法的初始化方法：
Table 2: Taxonomy of Ramsey Search Algorithms by Initialization Method
1. 随机与随机化初始化
从随机图（如 Erdős–Rényi 图 G(n,p)）或空图/贪心基线图开始，主要依靠模拟退火等随机优化方法逐步消除违规结构。适用于一些较小规模的拉姆齐数。
示例：R(3,5) 的搜索算法
示例：R(3,7) 的搜索算法
2. 代数结构播种
使用具有良好数学性质的图作为起点，如 Paley 图、二次剩余图、三次剩余图等。这些图本身已接近满足拉姆齐约束，为后续优化提供了一个“高起点”。
3. 循环图与循环引导
从循环图（Circulant Graph）家族出发，利用无和集（sum-free set）等代数性质来保证部分约束（如无三角形），再进行迭代扩展。本次多项新纪录（如 R(3,13), R(3,18)）的算法属于此类。
示例：R(3,13) 的搜索算法
示例：R(3,18) 的搜索算法
4. 混合、分形与谱方法
最复杂的一类，融合了分形自相似构造、谱性质分析、多种启发式并行等策略。
示例：R(3,11) 的搜索算法
这些算法高度针对其对应的 (r,s) 参数，相当于为每个具体问题“量身定制”。而定制过程，是完全自动化的。
透视AI设计的算法：以R(4,15)为例
近距离观察一个突破性算法，能更直观地感受AI设计的精巧之处。以刷新R(4,15)下界的算法为例，它包含以下几个关键创新：
Algorithm 6: Search algorithm for R(4,15) lower bound
- 和声遗传记忆：维护一个全局记忆池，跨代记录在成功图中频繁出现的“边”和“轨道”（循环距离）。这为初始化提供了概率指导。
- 谱初始化：新图的候选要么来自广义Paley图等代数构造，要么基于“和声记忆”中的概率分布，通过扩展已有最佳图来生成。
- 前瞻与和声评分：在删除一条边以破坏一个4-团时，评分不仅考虑直接的团数变化，还评估此操作引发大独立集的风险，并对历史表现好的边给予“和声”保护加分。
- 和声隧穿：当搜索陷入局部最优（仍有4-团未消除）时，算法会识别出在剩余4-团中出现频率最高的“有毒轨道”（一个特定的循环距离 d*），然后*一次性翻转所有距离为 d 的边**。这种大规模突变帮助搜索跳出局部陷阱。
这种将长期记忆、启发式评分与激进逃逸机制相结合的策略，在人类设计的算法中并不常见，但AlphaEvolve通过进化找到了它。
对比人类专家：AI的优势何在？
与人类专家手工设计的顶尖算法相比，AlphaEvolve生成的算法展现出一些显著特点：
1. 懂得利用已知的强代数结构
AI并非盲目随机搜索，它会主动选择Paley图、循环图、三次剩余图等数学上已知的、性质良好的图作为搜索起点。这表明LLM在代码变异过程中，能够隐含地运用领域知识。
2. 擅长串联多种启发式策略
人类算法往往侧重于一种核心策略（如模拟退火）。而AlphaEvolve生成的算法经常将多种方法串联或混合使用，例如先进行禁忌搜索，再结合退火，中间可能还穿插着局部修复或遗传算法的思想。
3. 自创高效的计算技巧
对于需要频繁检查图中是否存在4-团或13-独立集的任务，精确计算开销巨大。AI生成的算法会自发地采用位运算加速、启发式预过滤、增量更新等技巧来大幅提升效率。
R(4,13)：同一起点，不同路径
此前最佳纪录（Exoo & Tatarevic, 2015）的算法从三次剩余图出发，使用标准模拟退火。AlphaEvolve选择了完全相同的起点，但后续采用了不同的策略组合。
R(4,14)：更换赛道
对于同一个问题，人类专家（Exoo, 2015）使用三次图初始化，而AlphaEvolve则转向了循环图领域，并采用了随机轨道采样和基于位运算的高速过滤技术。
R(4,10)：发明新策略
与此前的最佳算法（Harborth & Krause, 2003 的分支定界法）相比，AlphaEvolve发明了一套基于循环图自适应概率采样、结合禁忌搜索与“近似命中仓库”机制的策略。论文作者指出，这种策略“在已有文献中找不到先例”。
总结：AI正在改写科学发现的范式
AlphaEvolve在拉姆齐数上的成功，是AI向纯数学领域深度渗透的又一例证。它展示了一条新的科研路径：不是用AI直接解决问题，而是用AI来发现解决问题的工具（算法）。
这项工作的意义不仅在于推进了几个具体的数学下界，更在于它验证了“元搜索”范式的有效性。从打破矩阵乘法纪录，到优化数据中心调度和芯片设计，再到此次攻克组合数学难题，AlphaEvolve作为一个“发现算法的算法”，其通用性和威力正在多个领域显现。
当然，当前方法仍有局限。它专注于通过构造反例来推高“下界”，而拉姆齐数的“上界”证明需要完全不同的、逻辑严密的数学论证，这超出了当前系统基于搜索和构造的能力范围。
然而，在其擅长的道路上，AlphaEvolve已经证明了自己可以超越人类直觉，自主探索出新颖、高效甚至人类未曾想到的算法策略。这标志着一个新的阶段：AI正从执行人类设定的规则，逐渐转变为参与甚至主导“规则”（即算法）的创造过程。
对于此类前沿的人工智能与算法研究动态，技术开发者与爱好者可以关注云栈社区的“开发者广场”等板块，获取更多深度资讯与讨论。
参考资料：
发表于 前天 01:40
|
查看: 13|
回复: 0
