💻 computer science

Latent Heuristic Search: Continuous Optimization for Automated Algorithm Design

本論文は、エンコーダ、微分可能な代理モデル、および正規化フローを活用して学習された潜在多様体内における連続最適化を利用する「潜在ヒューリスティック探索」という枠組みを導入し、凍結された大規模言語モデルを条件付けることで、組み合わせ最適化問題に対して高パフォーマンスなヒューリスティックを効率的に生成することを可能にする。

原著者： Cheikh Ahmed, Mahdi Mostajabdaveh, Zirui Zhou

公開日 2026-05-19

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

CC BY 4.0

原著者： Cheikh Ahmed, Mahdi Mostajabdaveh, Zirui Zhou

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

複雑なパズル、例えばトラックの配送ルートを整理したり、スーツケースを完璧にパッキングしたりするような、新しい超効率的な解決法を発明しようとしていると想像してください。伝統的には、人間は試行錯誤を繰り返し、ルールを何度も微調整しながらこれを行ってきました。

最近、科学者たちは、コードを書くのと同じ種類の AI である「大規模言語モデル（LLM）」を活用し、これらのルールを自動的に発明させる取り組みを始めました。彼らは AI を創造的なパートナーのように扱い、新しい「レシピ」（アルゴリズム）を生成させ、どれが最も効果的に機能するかをテストしています。

しかし、現在のこの手法は、料理本の中で単語を一つずつランダムに変更しながら完璧なレシピを見つけようとするようなものです。「塩」を「砂糖」に変え、次に「小麦粉」を「砂」に変え、より良い料理に偶然たどり着くことを期待します。これは遅く、散漫で、言葉や記号の混沌とした「離散的」な空間を探索しているため、しばしば食用にならない結果をもたらします。

この論文は、「潜在ヒューリスティック探索（Latent Heuristic Search: LHS）」というより賢明な方法を提案します。

以下に、日常の比喩を用いた簡単な仕組みの解説を示します。

1. 「魔法の地図」（潜在空間）

研究者たちは、レシピを単語ごとに見るのではなく、まずすべての可能なレシピを、滑らかで連続的な地図上の単一の点に変換します。

比喩: すべての可能な配送ルートが、巨大な 3 次元の風景上の点だと想像してください。良いルートは高く日当たりの良い丘にあり、悪いルートは深く暗い谷にあります。
問題点: 旧来の方法では、点をランダムに飛び移る必要がありました。この新しい方法では、AI がこの風景の形状を学習し、最高の丘へと滑らかに「滑り降りる」ことができます。

2. 「翻訳者」（エンコーダーとサロゲート）

この地図を機能させるために、システムは 2 つの特別なツールを使用します。

エンコーダー: これは、散らかった書き言葉のレシピ（コード）を、地図上のきれいな座標に変換する翻訳者のようなものです。
サロゲート: これは、地図上の座標を見るだけでレシピがどれほど優れているかを予測する「水晶玉」です。実際にケーキを焼く（コードを実行する）ことなく、味が良くなるかどうかを知る必要はありません。水晶玉が推測します。これにより、莫大な時間の節約になります。

3. 「安全網」（正規化フロー）

ここが難しい部分です。地図上をただ滑り回っていると、有効なレシピが存在しない場所、例えば「砂糖を 500 ポンド加える」という座標のような場所へ滑り落ちてしまう可能性があります。

解決策: 研究者たちは正規化フローを使用します。これは、魔法の伸縮性のあるゴムシートのようなものです。それは、散らかり不規則なレシピの地図を、完璧で滑らかで丸い球体（ガウス分布の形状）に引き伸ばします。
なぜ役立つのか: AI が最高のレシピを探す際、この完璧な球体の中を滑り回ります。球体が非常に整った形をしているため、AI が「 nonsensical（ nonsensical）」な領域へ滑り込む可能性は大幅に低くなります。これにより探索は安全かつ整理されたものになります。

4. 「逆翻訳者」（マッパーと LLM）

AI が滑らかな球体上の完璧な座標（最良の場所）を見つけると、その座標を再び実際に実行可能なコンピュータプログラムに戻す必要があります。

プロセス: 「ソフトプロンプト」（見えない特別な指示のセット）を使用して、LLM にささやきます。「ねえ、この地図上の完璧な場所に基づいて、新しい配送ルートアルゴリズムを書いてくれ」と。
LLM は実際のコードを生成し、それが本当に機能するかテストされます。

彼らは何を見つけたか

研究者たちは、この方法を 4 つの古典的なパズルでテストしました。

巡回セールスマン問題: 多くの都市を訪問する最短経路を見つける。
車両経路計画: 限られたトラックの容量で多くの家へ荷物を配送する。
ナップサック問題: 重量制限のある袋に最も価値のあるアイテムを詰める。
ビンパッキング: 到着するアイテムを箱に収める。

結果:

性能: 新しい方法は、ランダムな単語の入れ替えに依存する既存の最良の方法と同等か、それ以上の解決策を見つけました。
効率性: これらの解決策を、より速く、より確実に見つけました。
安定性: 「安全網」（ゴムシート）のおかげで、システムは実行不可能な壊れたコードを生成することはほとんどありませんでした。

結論

この論文は、探索プロセスを「次の単語を推測する」という混沌としたゲームではなく、滑らかな数学的な滑り台に変えることで、問題解決アルゴリズムの発明を自動化する方法を提示します。これは、AI の力を借りて良い解決策の「形状」を理解し、ノイズに迷い込むことなく、直接最良のアイデアへと滑り降りることを可能にします。

技術的概要：潜在ヒューリスティック探索（LHS）

問題定義

組合せ最適化問題（例：巡回セールスマン問題、車両経路計画、ナップサック問題）に対する高品質なヒューリスティックアルゴリズムの設計は、従来、反復的な改良と深いドメイン知識を必要とする専門家主導のプロセスであった。近年の進展では、この発見を自動化するために大規模言語モデル（LLM）を進化フレームワーク（例：FunSearch、EoH、ReEvo）に統合している。しかし、これらの既存の手法は主にプログラムの構文の離散空間で動作する。これらは、高度に非凸な最適化ランドスケープをナビゲートするために、確率的サンプリング、トークンレベルの突然変異、および再結合に依存している。このアプローチは、一貫した改善を発見するために多くの高コストな実行ベースの評価を必要とし、離散探索空間の脆さに対処する際に困難をきたす。

手法

本論文は、最適化プロセスを離散トークン空間から学習された連続的な潜在多様体へ移行させるフレームワーク、**潜在ヒューリスティック探索（LHS）**を提案する。手法は、4 つの相互接続されたコンポーネントで構成される。

潜在エンコーディング: 事前学習されたコードエンコーダ（ $E$ ）が、離散的なヒューリスティックプログラムを連続的なベクトル埋め込み（ $z \in \mathbb{R}^d$ ）にマッピングする。
代理モデル化: 微分可能な代理モデル（ $f_\theta$ ）は、ヒューリスティックの潜在埋め込みに基づいてその性能スコアを予測するように訓練される。ノイズのある評価やスケールの変化に対する堅牢性を確保するため、モデルは点ごとの回帰ではなく、候補の相対的な順序に焦点を当てた**ペアワイズランキング損失（RankNet）**を用いて訓練される。
正規化フローによる正則化最適化: 生エンコーダ埋め込みでしばしば見られる異方性や低密度領域に対処するため、フレームワークは可逆的な正規化フロー（ $F_\phi$ ）を採用する。このフローは、複雑なプログラム埋め込み空間を構造化された凸ガウス事前分布空間（ $u \in \mathbb{R}^d$ ）にマッピングする。最適化は、探索軌道が妥当で有効なヒューリスティックの多様体の近くに留まることを保証しつつ、この事前分布空間内で勾配上昇によって行われる。
ソフトプロンプトによるデコーディング: 最適化された潜在ベクトルは、学習された潜在からプロンプトへのマッパー（ $\phi_\omega$ ）を用いて、凍結されたデコーダのみの LLM の入力空間へ投影される。このマッパーは、LLM が新しい実行可能なヒューリスティックコードを合成するよう導く連続的な「ソフトプロンプト」（条件付け埋め込み）を生成する。生成されたコードは構文検証され、ベンチマークインスタンスで評価されてデータセットを更新する。

全体のプロセスは反復的である。シードプログラムはエンコードされ、潜在事前分布空間で最適化され、新しいコードにデコードされ、評価され、代理モデルとフローモデルを洗練させるためにトレーニングプールに追加される。

主要な貢献

連続的なヒューリスティック発見: 本論文は、離散トークンレベルの進化探索から、学習されたプログラム表現上の連続最適化へのパラダイムシフトを導入し、ヒューリスティック設計に対する勾配ベース手法の利用を可能にする。
フロー正則化探索: プログラム埋め込みを構造化された事前分布へマッピングするために正規化フローを使用する必要性を実証する。この正則化は、探索が潜在空間の無効な領域へ逸脱することを防ぎ、生埋め込み空間での直接最適化と比較して、生成されたコードの成功率を大幅に向上させる。
ランキングベースの代理モデル: ペアワイズランキング代理モデルの使用は、勾配上昇のための安定した学習信号を提供し、ノイズのある評価環境における絶対スコア回帰に伴う脆さを回避する。
ソフトプロンプト条件付け: フレームワークは、潜在ベクトルをソフトプロンプトへ変換する学習可能なマッパーを利用し、内部パラメータを変更することなく凍結された LLM を誘導することを可能にする。

実験結果

LHS フレームワークは、4 つの組合せ最適化タスク（TSP、容量制約付き車両経路計画問題（CVRP）、ナップサック問題（KSP）、オンラインビンパッキング（OBP））で評価された。

性能: ルーティングタスク（TSP および CVRP）において、LHS は最先端の性能を達成し、離散進化ベースライン（FunSearch、EoH、ReEvo）および MCTS ベースのアプローチを常に上回った。例えば、TSP-200 において、LHS は目的関数値 12.49 を達成し、ReEvo（12.58）および EoH（13.15）を上回った。
効率性: LHS は競争力のある、あるいは優れた実行時間効率を示した。TSP 実験において、LHS はより良い結果を達成しながら、ReEvo（29.61 秒）と比較して著しく少ない時間（TSP-200 で 4.86 秒など）を要した。
アブレーション研究:
- No-Flow: 正規化フローを除去し、生埋め込み空間で直接最適化した場合、生成されたコードの成功率が大幅に低下した（74% から 61%）。これは、フローが探索を安定化させる役割を果たしていることを確認する。
- No-Grad: 勾配上昇を単純な補間と置き換えた場合、高い妥当性（86%）が得られたが、最適化能力は低かった（目的関数値が悪化）。これは、高品質なヒューリスティックを発見するために勾配信号が必要であることを浮き彫りにする。
汎化性: この手法は、探索フェーズで使用されたものよりも大きなインスタンスサイズ（例：TSP-100、TSP-200）においても良好に動作する、強力なクロスサイズ汎化性を示した。

意義と主張

著者らは、LHS が既存の離散進化アプローチに対する補完的な方法論的代替案を提供すると主張する。プログラムを連続的な潜在ベクトルとして扱うことで、このフレームワークは、実行ベースの評価の厳密性を維持しつつ、勾配情報を通じてヒューリスティック設計空間を体系的にナビゲートすることを可能にする。

本論文は、連続最適化が離散探索に対する強力な補完であり、固定された評価予算内で優れた目的関数値を達成し得ることを強調している。しかし、著者らは限界についても謙虚に述べており、LHS の有効性は本質的に代理モデルの品質と初期トレーニングコーパスに依存していることに言及している。過度に攻撃的な最適化ステップは、候補を実行可能コードの多様体から押しやる可能性があり、今後の研究では、大域的な探索と局所的な洗練のバランスを取るために、LHS を離散進化演算子とハイブリッド化することが検討されるべきであると示唆している。このフレームワークは、特に初期データ生成のコストを償却できる関連タスク間での反復探索を伴うシナリオにおいて効果的な、自動化されたアルゴリズム設計のためのより微分可能なパイプラインへの一歩として提示されている。