大規模言語モデルが組合せ最適化のための補完的ヒューリスティクスを発見

組合せ最適化（CO）は科学、工学、産業において不可欠であるが、新しい問題変種ごとに有効なヒューリスティクスを設計するには、深いドメイン知識と数か月にわたる専門家の反復作業が必要となる。本論文は、アルゴリズム設計を入力スキーマ、出力スキーマ、ツールライブラリ、ヒューリスティック・ポートフォリオ（I-O-T-H インターフェース）に分解し、時間制約付きの補完的進化によってポートフォリオを洗練するフレームワーク LACE（LLM-driven Algorithm Construction via Complementary Evolution）を導入する。このインターフェースは検証済みの問題契約を定義し、大規模言語モデルの能力を問題固有の実装ではなく高レベルのアルゴリズム推論へ向ける。補完的進化は、厳しい実行時間予算内で異種インスタンスを解ける専門ヒューリスティクスを反復的に生成・選択する。36 の古典的な CO-Bench 問題において、LACE は平均スコア 0.945 を達成し、既存の最強の LLM ベース手法は 0.870、フレームワークなしの直接 LLM プロンプティングは 0.571 であったことから、利得はモデルではなくフレームワークにあることが示される。構造的に新しい 4 問題では LACE が 0.97～0.99 に達する一方、既存の 5 つの LLM ベースベースラインは実行可能なアルゴリズムを生成できなかった。これらの結果は、このような問題に対する効果的なアルゴリズム発見を大幅に自動化できることを示している。

(出典：Nature)