🤖 AI

Algorithm Discovery With LLMs: Evolutionary Search Meets Reinforcement Learning

本論文は、強化学習による微調整を通じて LLM 探索演算子を継続的に洗練させることにより、アルゴリズム発見のための LLM 基盤進化探索を強化し、組合せ最適化タスクにおいて優れた解の同定を加速する新たな枠組みを提案する。

原著者： Anja Surina, Amin Mansouri, Lars Quaedvlieg, Amal Seddas, Maryna Viazovska, Emmanuel Abbe, Caglar Gulcehre

公開日 2026-05-26

📖 1 分で読めます☕ さくっと読める

原著者： Anja Surina, Amin Mansouri, Lars Quaedvlieg, Amal Seddas, Maryna Viazovska, Emmanuel Abbe, Caglar Gulcehre

原論文は CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) でライセンスされています。 ✨ これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。免責事項の全文を読む

完璧なケーキを焼くための、新しく超効率的なレシピを発明しようとしていると想像してください。あなたはレシピを書き起こすことができる非常に才能のあるシェフ（大規模言語モデル、または LLM）を持っています。

旧来の方法：「静的なシェフ」
以前の手法（「FunSearch」など）では、シェフにレシピを書いてもらいます。それを焼いて味見し、良し悪しを判断します。まあまあならそのまま残し、素晴らしいものなら、その素晴らしいレシピを見て、それを基に少しだけ良いレシピを書き起こすようシェフに依頼します。これを数千回繰り返します。

問題は何でしょうか？シェフは実際にはプロセスから学習しません。彼らは毎回試行の後にすべてを忘れる天才のようなものです。彼らは元のトレーニングに基づいて推測し続け、単なる幸運によってより良いレシピにたどり着こうとします。彼らは良いケーキを作る要因についての内部知識を更新しません。

新しい方法：「EvoTune」（学習するシェフ）
この論文の著者たちは、EvoTuneと呼ばれる新しい手法を提案しています。これは同じ才能あるシェフを雇うようなものですが、今回は特別なトレーニングループを与えます。

味見テスト（進化的探索）： 以前と同様に、シェフは多くのレシピを書きます。それらを焼いて味見し、スコア付けします。最高のものを選び、悪いものは捨てます。
教訓（強化学習）： これが魔法のステップです。悪いレシピを捨てるだけでなく、シェフに「勝者」と「敗者」を見せ、「違いを見てください！勝者はこれをし、敗者はあれをしました」と伝えます。
更新： その後、これらの教訓に基づいてシェフに簡単な「復習コース」（ファインチューニング）を与えます。シェフの脳は、なぜ勝者のレシピが機能したのかを理解するように実際に変化します。
繰り返し： これで、次にシェフにレシピの次のバッチを書くよう頼むとき、彼らはもう単に推測しているだけではありません。新しく更新された知識を使って、より早く良い場所を目指します。

なぜこれが優れているのか？
巨大な森で隠された宝を探すことを考えてみてください。

旧来の方法： 地図はあるが記憶がない斥候を送ります。彼らは歩き回り、場所を見つけ、宝があるか確認し、その後すべてを忘れます。次の場所を見つけるために、またランダムに歩き回らなければなりません。
EvoTune： 斥候は場所を見つけ、「ああ、ここは木が密集しているから、宝は近くにあるはずだ」と気づき、内部の地図を更新します。次に外に出るとき、彼らはランダムに歩き回るのではなく、有望な地域に向かってまっすぐ歩きます。

何を実験したのか？
研究者たちは、コンピュータが物事を整理する最良の方法を見つける必要がある 3 つの難しい「パズル」ゲームでこれをテストしました。

ビンパッキング： さまざまなサイズの箱を、可能な限り少ない数のトラックに詰め込むこと。
巡回セールスマン： 経路を重複させずに都市のリストを訪問する最短ルートを見つけること。
フラットパック： 複雑なテトリスのように、奇妙な形をしたブロックを重ならないようにグリッドに収めること。

結果
彼らは、「学習するシェフ」（EvoTune）が、「静的なシェフ」（旧来の手法）よりもはるかに速く優れた解決策を見つけ出したことを発見しました。

より良いスコア： EvoTune によって見つけられたレシピ（アルゴリズム）はより効率的でした。
より多様性： 学習するシェフは、ただ一つの良いレシピを見つけそこで止まったのではなく、多様で高品質な解決策の幅広いバリエーションを見つけました。
現実世界での勝利： 一つの特定の課題（データセンター内のサーバー配置に関するグーグルのハッシュコード大会）において、EvoTune は大会で人間チームによって見つけられた最良の解決策よりも実際に優れた解決策を見つけました。

秘密のソース
この論文はまた、シェフの創造性を維持するために使用した特定のトリックについても言及しています。モデルに教えすぎると、時に「行き詰まり」、同じことを繰り返し書くだけになってしまいます。これを防ぐために、彼らは「勝者から学びつつ、新しいアイデアを探求し続ける」ようシェフに強制する特別な数学的規則（「Forward KL」と呼ばれる）を使用しました。

要約すると
EvoTune は、探索（多くのことを試すこと）と学習（機能したことに基づいて AI の脳を更新すること）を組み合わせたシステムです。これは、静的なツールを、問題を解決しようとするほどに賢くなる自己改善型のパートナーへと変えます。

技術的サマリー：LLM によるアルゴリズム発見：進化探索と強化学習の融合

問題定義

数学や組み合わせ最適化における複雑な問題に対する効率的なアルゴリズムの発見は、歴史的に相当な人間の専門知識に依存してきました。大規模言語モデル（LLM）と進化探索（FunSearch 法など）を組み合わせる最近の進展は、この発見を自動化する可能性を示していますが、既存のアプローチは LLM を静的な生成器として扱っています。これらの手法は、過去の成功に基づいて LLM に新しいプログラムを提案させますが、進化探索中に得られた信号に基づいてモデルの内部パラメータを更新することはありません。その結果、LLM のパラメトリックな性質を活用して時間とともに探索方針を洗練させる機会を逃し、最適でない収束や解空間の非効率的な探索につながる可能性があります。

手法：EvoTune

著者は、進化探索と強化学習（RL）を密に統合し、LLM 探索演算子を継続的に洗練させるフレームワークEvoTuneを提案します。この手法は、2 つの交互フェーズからなる反復ループで動作します。

進化探索（探索）:
- LLM は、過去の反復で発見された高スコア・プログラムから構築されたプロンプトに基づき、候補となる Python プログラム（アルゴリズム）を生成します。
- これらのプログラムは、特定の組み合わせ最適化タスク（例：ビンパッキング、巡回セールスマン問題、フラットパック）で評価され、報酬スコア（通常は最適性ギャップの負の値）が得られます。
- 有効なプログラムとそのスコアは、多様性を維持し早期収束を防ぐために「島」に整理されたプログラムデータベースに格納されます。
- 探索は「ブートストラッピング」戦略を採用しており、LLM は高パフォーマンスと低パフォーマンスのプログラムの差異を分析して、新しい候補の生成を導きます。
RL 学習（洗練）:
- 定期的に（ $f_{RL}$ 反復ごと）、進化探索から蓄積されたデータを用いて、LLM の生成方針（ $\pi_\theta$ ）が更新されます。
- 著者はこれを選好最適化問題として定式化します。プロンプト $x$ 、より高い報酬を持つプログラム $y^+$ 、より低い報酬を持つプログラム $y^-$ からなるトリプレット $(x, y^+, y^-)$ で構成される選好データセット $D_{pref}$ を構築します。
- モデルは直接選好最適化（DPO）を用いてファインチューニングされます。標準的なオフライン DPO と異なり、EvoTune はデータが進化するモデル自体によって動的に生成されるオフポリシー設定で動作します。
- 多様性維持: 重要な設計選択として、DPO の目的関数内で、より一般的な逆 KL 散度ではなく前方 KL 正則化を使用します。これは「マス・カバリング」行動を促進し、モデルが単一のモードに収束するのを防ぎ、効果的な進化探索に不可欠な出力多様性を維持します。

主要な貢献

進化探索への RL の統合: 本論文は、LLM ベースの進化探索と RL によるファインチューニングをループ内で密に統合する可能性を初めて実証したと主張しています。LLM を単なる静的な生成器としてのみ使用する以前の手法とは異なり、EvoTune は探索から得られた洞察をより効果的に利用するためにモデル重みを更新します。
アルゴリズム発見の加速: RL による探索方針の洗練により、優れたアルゴリズムの発見が加速されます。3 つの指示調整済み LLM（Llama3.2 1B、Phi 3.5 Mini、Granite 3.1 2B）を用いた実験では、ベースラインの FunSearch 法に対して一貫した性能向上が示されました。
多様性を維持するアライメント: 著者は、出力多様性を維持するために修正されたアライメント目的（前方 KL 正則化付き DPO）を使用する利点を示しました。モード収束が新たな解の発見を妨げる可能性があるため、これは進化戦略にとって重要です。
広範な適用性: この手法は、標準的な組み合わせ問題（ビンパッキング、TSP、フラットパック）、現実世界の Google Hash Code チャレンジ（データセンター最適化、自動運転ライド）、および記号回帰タスク（LLM-SR）を含む多様なベンチマークで検証されました。

実験結果

著者は、EvoTune をモデル学習を行わない FunSearch スタイルのベースライン（進化探索のみ）に対して、複数のタスクとモデルで評価しました。

性能向上: EvoTune は、発見された上位 50 プログラムについて、ベースラインと比較して一貫して高い最終報酬スコア（低い最適性ギャップ）を達成しました。サンプリング予算が増加するにつれて性能差が拡大する傾向が見られ、より大きな予算が手法の利点を増幅させることを示唆しています。
汎化能力: 進化されたプログラムは、同じ分布から抽出された検証用摂動セットおよびテストセットにおいて堅牢性を示し、学習された方針がトレーニング中に観測された特定のインスタンスを超えて汎化することを示しました。
現実世界のベンチマーク:
- Google Hash Code データセンター最適化タスクにおいて、EvoTune は418のスコアを達成し、人間のトップスコア 407 を上回り、FunSearch ベースライン（414）よりも優れた性能を示しました。
- 記号回帰タスク（LLM-SR）において、EvoTune は進化ベースラインを上回っただけでなく、より大規模またはプロプライエタリなモデル（例：Mixtral 8x7B、GPT-3.5-turbo）を使用するベースラインをも凌駕しました（より小さなモデル Phi-3.5 Mini、38 億パラメータを使用しながら）。
アブレーション研究:
- 前方 KL と逆 KL: 実験により、逆 KL と比較して前方 KL 正則化がより高い報酬とより多くの固有解をもたらすことが確認され、多様性維持の重要性が実証されました。
- 代替 RL: 高スコア出力に対する教師ありファインチューニング（ReSTEM）を DPO の代替としてテストしました。結果、DPO は ReSTEM を一貫して上回り、ハイパーパラメータ調整に対する感度も低いことが示されました。

意義と主張

本論文は、Sutton (2019) の「苦い教訓（Bitter Lesson）」（探索と学習は相乗的であるという主張）に対処することで、自動化されたアルゴリズム設計における重要な前進として EvoTune を位置付けています。著者は以下を主張しています。

相乗効果: 探索は新しいデータを生成し、学習はそのデータからパターンを抽出して将来の探索をより効果的に導きます。
効率性: RL を統合することで、システムは単に集団の平均スコアを向上させるだけでなく、上位 k 性能（top-k performance）で測定される優れた解へと進化探索を積極的に導きつつ、イノベーションに必要な多様性を維持します。
スケーラビリティ: データセンター最適化や応力 - ひずみモデリングなどの複雑な非合成問題での成功により、この手法は現実世界の設定へ拡張する可能性を示しています。

著者は、実験が 10 億から 38 億パラメータの範囲のモデルで行われたこと、および手法の可能性を完全に理解するにはモデルサイズとサンプリング予算のさらなるスケーリングが必要であることを控えめに認め、限界を指摘しています。また、RL 学習フェーズの追加計算コストと、推論効率および解の質の向上との間のトレードオフも強調しています。