ついに、Google DeepMindがまた大きな成果を上げました。彼らが開発したシステムAlphaEvolveは、極値組み合わせ問題において突破を果たし、かつてない5つの古典的ラムジー数の下限を同時に更新しました。
論文はこちら：https://arxiv.org/pdf/2603.09172
驚くべきことに、これは人間が5種類の異なるアルゴリズムを手作業で設計したのではなく、一つの統合された「メタアルゴリズム」によって達成されました。
これらの探索アルゴリズムを導き出すのは極めて困難で、過去10年以上改善されていませんでした。しかしDeepMindは大規模言語モデルに自律的にアルゴリズムを書かせ、10年近く眠っていた数学的記録を一掃しました。
DeepMindの研究者が喜びの報告をした後、CEOのハサビスもすぐに祝福のメッセージを送り、AlphaEvolveのこの成果はAIが数学の分野でまた一つの重要なマイルストーンになると語りました。
さらに、チューリング賞受賞者のルカンもチームに祝福の言葉を送りました。
ラムジー数問題がなぜこれほど難しいかを説明しましょう。それは、史上最高の数学者でさえも絶望させる問題です。
著名な数学者ポール・エルデシュ（パウル・エルデシュ）はかつて言いました。「もし宇宙人が地球に『制限時間内にR(5,5)を計算せよ、できなければ人類を滅ぼす』と告げたら、人間がもっとも理性的な選択は降伏することだろう」と。
何十年にもわたり、ラムジー数は組合せ数学における最も厄介な問題の一つでした。数学者が特定のラムジー数で前進を遂げようとすると、通常はゼロからその問題専用の探索アルゴリズムを設計しなければなりませんでした。
しかし今回、AlphaEvolveは5つすべてを同時に突破しました。
それに加えて、これはAlphaEvolveの能力の一部に過ぎません。過去に、このシステムは56年間変わらなかった行列乗算の記録を打ち破り、Googleデータセンターのスケジューリングを最適化し、さらにはAIチップ設計において人間のエンジニアが見落としていた構造の簡略化を見出しました。
アルゴリズムを自動的に発見し、さらにそのアルゴリズムで自分の計算基盤を最適化できるシステムは、まさに新たな知能の種の誕生を示しています。
--- ラムジー数の基本 ---
約100年前、イギリスの論理学者フランク・ラムジーは次のような定理を示しました：6人の集団では、相互に知り合っている3人か、互いに知らない3人が必ず存在します。
グラフ理論において、R(r,s)は、どのような無向グラフにしても、n個以上の頂点を持つと必ず次のいずれかが成り立つ最小の整数nを表します：r個の頂点からなる完全部分グラフ（クリーク）またはs個の頂点からなる独立集合が存在する。
たとえば、R(3,3)=6です。つまり、任意の6頂点のグラフは三角形か、互いに結びついていない3点を含まなければなりません。
現在、小規模なパラメータ（例えば(3,s)（s≤9）や(4,s)（s=4,5））についてはラムジー数は既に正確に求まっていますが、大きなパラメータに対しては依然として上限と下限の間に大きなギャップがあります。
下限を得る方法は、r-クリークでもs-独立集合でもない頂点数nのグラフを構築すれば、R(r,s)≥n+1ということになります。
--- 5つの10年記録を一度に塗り替える ---
今回、DeepMindの研究者3名は論文で、AlphaEvolveによって5つの古典的ラムジー数の下限が同時に更新されたことを発表しました。
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年保持）
各数値がわずか1だけ増加したように見えますが、ラムジー数の分野ではこれが非常に大きな進歩であり、他の多くの数学分野で桁が変わるほどの進歩に匹敵します。
さらに重要なのは、この5つの記録がすべて同じシステムから生まれたことです。このシステムは既知の正確なラムジー数の下限にも一致し、その他多数の値について現在知られている最良の下限を合わせて28個のR(r,s)をカバーしています。
--- AlphaEvolve ― アルゴリズムを進化させる ---
AlphaEvolveはどのようにしてこれを実現したのでしょうか。簡単に言うと、大規模言語モデルを使ってコードを進化させるエージェントです。探索の対象は探索アルゴリズムそのものです。
従来のアプローチは、人間の専門家が数学的直感と領域知識に基づいて探索アルゴリズム（たとえばシミュレーテッドアニーリングやタブーサーチ）を手作業で設計し、それをコンピュータで実行することでした。アルゴリズムの良し悪しは人間の技量に依存します。
AlphaEvolveはこのステップを自動化します。その流れは次の通りです。
まず「アルゴリズムの集団」を維持します。最初は単純なベースラインプログラム（空のグラフを返すだけのもの）から始めます。
次に、LLMでコードを変異させます。集団から性能の良いアルゴリズムを選び、大規模言語モデル（Gemini）にコードを変異させます―探索戦略を変更し、初期化方法を変え、新しいヒューリスティックルールを追加します。
その後、変異後のプログラムを実行し、得点付けを行います。構築した合法グラフのサイズが現在の記録を上回れば高得点、ほぼ合法（違反が少ない）であれば一部報酬を与えます―これは探索を境界へと導くためです。
最後に、高得点アルゴリズムを集団に戻し、選択・変異・評価を繰り返します。これがいわゆる「メタサーチ」―アルゴリズム空間の中で探索を行うプロセスです。
つまり、AlphaEvolveが最終的に出力するのはグラフそのものではなく、「良いグラフを見つけ出すコード」です。
--- AIが発見した4つのアルゴリズムファミリー ---
論文では、28個のR(r,s)に対するAlphaEvolveが発見した具体的な探索アルゴリズムが示されています。これらのアルゴリズムはスタイルが大きく異なりますが、4つのファミリーに分類できます。
第一種：ランダムスタート＋シミュレーテッドアニーリング
最も素朴な手法です。ランダムなグラフから始め、シミュレーテッドアニーリングによって規則違反（三角形または過大な独立集合）を少しずつ取り除きます。
R(3,5)やR(3,7)などの小さな値に対してこの方法が使われます。シンプルですが、大規模な問題には不十分です。
第二種：代数構造によるシード
Paleyグラフ、二次残差グラフ、三次残差グラフなど、深い数学的背景を持つ代数的グラフを出発点とし、そこに局所最適化を施します。これらのグラフは元からラムジー制約に近い性質を持っているため、探索に良いスタート地点を与えます。
R(4,13)の突破はこの種類に属し、有限体F₁₂₇上の三次残差Cayleyグラフから出発しています。
第三種：巡回グラフ＋和集合フリー誘導
巡回グラフ（Circulant Graph）から出発し、和集合フリー（sum-free set）の代数的性質を利用して三角形を自然に避け、それから増加的拡張を行います。
R(3,13)とR(3,18)の突破はこのファミリーに属し、これが最も多くの新記録を生み出しました。
第四種：混合／フラクタル／スペクトル手法
最も複雑な種類で、フラクタル的自己相似構造、スペクトル特性の解析、複数のヒューリスティックを並列実行するなどを組み合わせます。
R(3,11)のアルゴリズムはフラクタル初期化＋適応エネルギー場＋動的温度調整の組み合わせを用いています。
興味深いのは、それぞれのアルゴリズムが特定の(r,s)値に対して高度に特化しているということです。つまり、AlphaEvolveは普遍的な万能アルゴリズムを見いだしたのではなく、各問題ごとに「オーダーメイド」の探索戦略を作り出したということです。ただし、このオーダーメイドのプロセス自体は完全に自動化されています。
--- AIが設計したアルゴリズムの巧妙さ ---
ブレイクスルーアルゴリズムの詳細を見てみましょう。
R(4,15)：ハーモニーメモリー＋スペクトル初期化＋有毒軌道トンネリング
この問題に対して、AlphaEvolveは「ハーモニークジーンメモリー」と呼ばれる仕組みを考え出しました―過去の成功例においてどのエッジやどの巡回距離が頻繁に登場したかを記録するグローバルなメモリプールを世代を超えて維持します。
初期化では、一般化Paleyグラフのような代数構成を用いるか、ハーモニーメモリーの確率分布に従って既知の最良グラフを拡張します。
局所探索ではタブーサーチとシミュレーテッドアニーリングの組み合わせを使いますが、4-クリークを取り除くためにエッジを削除するときは、その効果だけを見るのではなく、削除によって生じ得る大きな独立集合のリスクも評価し、過去に良い成績を収めたエッジには「ハーモニー」保護ボーナスを与えます。
最も驚異的なのは「ハーモニートンネリング」と呼ばれる脱出メカニズムです。探索が行き詰まり（まだ4-クリークが残っている場合）、残りの4-クリークの中で最も頻繁に現れる巡回距離d*を見つけ出し、その距離d*を持つすべてのエッジを一度に反転させます。これはグラフに対する大規模な手術に相当し、現在の局所最適から飛び出すことを可能にします。
このような戦略の組み合わせは人間の専門家が考えつくのは困難ですが、AlphaEvolveは繰り返しの変異と進化を通じて自らこれを見つけ出しました。
--- 人間の専門家は完全に敗北 ---
AlphaEvolveが生成するアルゴリズムの強さは既に示しました。では、トップレベルの人間専門家が手作業で設計したアルゴリズムと比較したとき、どこが勝っているのでしょうか。論文では3組の対比が示され、どれも圧倒的です。
R(4,13)：スタートは同じだが、AIが後半で勝つ
これまでのベスト記録はExooとTatarevicが2015年に樹立したもので、三次残差グラフから出発し、標準的なシミュレーテッドアニーリングで最適化していました。AlphaEvolveも同じ出発点（F₁₂₇上の三次残差グラフ）を選びましたが、その後の戦略は全く異なります―二段階の選別、擾乱に基づく頂点拡張、「戦略的キック」を含むタブーサーチ（停滞500ステップ後に強制的にランダムジャンプ）などです。
R(4,14)：AIはスタートグラフさえも変えた
Exooは2015年に三次グラフで初期化しましたが、AlphaEvolveは巡回グラフを選び、まったく異なる探索空間で探索を行い、ランダム軌道サンプリングと高性能なビット演算で高速化を図りました。
R(4,10)：AIが文献に存在しない戦略を考案
これまでのベストはHarborthとKrauseが2003年に枝刈り境界探索で得たものです。それに対し、AlphaEvolveのアルゴリズムは巡回グラフ分布からサンプリングし、適応確率のタブーサーチと近似ヒットバッファ機構を組み合わせています。論文著者は「この探索戦略は既存の文献には前例がない」と述べています。
以上をまとめると、AlphaEvolveが生み出すアルゴリズムには以下の3つの顕著な特徴があります。
既知の代数構造を活用できる。
- 複数のヒューリスティックを組み合わせることを好む。
- 高速な近似計数方法を自ら考案する。
--- AIが科学発見のルールを書き換える ---
ハサビスはAlphaEvolveの意義を次のように述べました。「知識がさらなる知識を生み、アルゴリズムが他のアルゴリズムを最適化する―この好循環は加速している」。
Geminiがコードを生成し、そのコードがより良いアルゴリズムを進化させ、アルゴリズムがGoogleのインフラストラクチャを最適化し、より効率的なインフラストラクチャがGeminiの訓練を速め、より強力なGeminiがさらに良いコードを生み出す―こうしたサイクルがAI自身の自己改善の基盤となっています。
そして今回のラムジー数でのブレイクスルーは、このストーリーをさらに一歩前に進めました。行列乗算のように明確な最適化目標と連続的な評価基準がある問題とは異なり、ラムジー数は離散的で組み合わせ爆炸的な探索空間であり、勾配を従って登るような手がかりはありません。
論文では現在の限界も正直に述べられています。「現時点では下限しか求められず、上限については特定のサイズ以上のグラフが制約を満たさないことを証明する必要があるため、例を見つけるだけでは解決できない」ということです。この方向についてはまだAlphaEvolveでは対応できませんが、可能な範囲では誰よりも前に進んでいます。
10年前、AlphaGoの手「37番」はAIが特定分野で人間の直感を超えることを示しました。5年前、AlphaFoldは生物学界が50年かけて解けなかったタンパク質構造予測問題を解きました。そして今、AlphaEvolveは固定された舞台から飛び出し、自分自身でルールを考え始めました―まさに新たな知の時代の到来です。