A*探索のための効率的なLLMベースのヒューリスティック設計に向けたアルゴリズム的プロンプト拡張

TL;DR（結論）

A探索の性能を決定づけるヒューリスティック関数を、大規模言語モデル（LLM）を用いて自動設計する新手法「A-CEoH」が提案されました。従来の自動設計手法は貪欲法などの単純なアルゴリズムに限定されていましたが、本研究ではプロンプトにAアルゴリズム自体のソースコードを組み込む「アルゴリズム的文脈拡張」を導入することで、LLMが探索の動態を深く理解し、より高精度な評価関数を生成することを可能にしました。倉庫物流におけるユニットロード再配置問題（UPMP）や、20×20という巨大なサイズのスライディングパズルを用いた検証において、A-CEoHは専門家が手作業で設計した既存のヒューリスティックを凌駕する成果を達成しました。特に、32Bクラスの比較的小型なローカルモデルであっても、適切なアルゴリズム的文脈を提供することで、巨大な汎用モデルを超える性能を発揮できることが示され、計算リソースを抑えつつ高度な最適化を実現する道が開かれました。

なぜこの問題か

組合せ最適化問題は、現代の物流や製造現場において効率化の鍵を握る重要な課題ですが、これらを解くための高品質なヒューリスティック（近似解法）の設計は、依然として困難を極めています。伝統的に、こうしたアルゴリズムの設計はドメインの深い専門知識を持つ専門家による手作業に依存しており、膨大な試行錯誤と時間を必要とする知識集約的なプロセスでした。近年、大規模言語モデル（LLM）と進化的アルゴリズムを組み合わせることで、この設計プロセスを自動化しようとする試みが注目を集めていますが、既存研究の多くは巡回セールスマン問題（TSP）やオンライン・ビンパッキング問題（oBPP）のような、常に実行可能な解が得られる「構築型」の貪欲法に焦点を当ててきました。しかし、現実世界の多くの最適化問題には、厳しい制約や状態に依存した移動制限が存在し、単純な貪欲法では解が見つからなかったり、解の質が著しく低かったりするという課題があります。…

核心：何を提案したのか

本研究の最大の貢献は、既存のヒューリスティック進化フレームワークである「Evolution of Heuristics (EoH)」を革新的に拡張し、A探索を最適に導くための評価関数を自動生成する新手法「Algorithmic - Contextual EoH (A-CEoH)」を提案したことにあります。この手法の核心的なアイデアは、LLMに与えるプロンプトの中に、Aアルゴリズム自体の具体的なソースコードを直接埋め込むという「アルゴリズム的文脈拡張」にあります。これにより、LLMは単に「評価関数を書け」という抽象的な指示を受けるのではなく、その関数がどのようなアルゴリズム環境で実行され、探索の動態にどのように寄与するのかを、コードの論理構造を通じて理解することが可能になります。…

続きはログイン/プランで閲覧できます。