PathWise: 自己進化するLLMによる、世界モデルを通じた自動ヒューリスティック設計のための計画立案

TL;DR（結論）

PathWiseは、組合せ最適化問題に対するヒューリスティック設計を、固定されたルールに基づく進化ではなく「帰結グラフ」を活用した逐次的な意思決定プロセスとして定式化する、新しいマルチエージェント推論フレームワークである。 このシステムでは、方策エージェントが進化学習の戦略を計画し、世界モデルエージェントが具体的なアルゴリズムのコードを生成し、さらに批判エージェントが過去の試行結果を分析して改善のためのフィードバックを動的に提供する仕組みを備えている。 巡回セールスマン問題や容量制約付き車両配送問題を用いた広範な実験の結果、PathWiseは従来手法と比較して少ない評価回数でより優れたアルゴリズムを特定し、異なる大規模言語モデルの基盤においても高い汎用性とスケーラビリティを発揮することが実証された。

なぜこの問題か

組合せ最適化問題（COP）は、物流のルート最適化やスケジューリング、製造業における設計自動化など、現実世界の複雑な意思決定タスクにおいて極めて重要な役割を果たしている。しかし、多くのCOPは計算複雑性が高いNP困難な性質を持つため、限られた時間内で高品質な解を得るためには、シミュレーテッド・アニーリングやタブー探索、反復ローカル探索といったヒューリスティック・アルゴリズムの利用が不可欠である。 効果的なヒューリスティックを構築するには、対象となる問題やソルバーの特性に合わせたアルゴリズム構成要素を設計する必要があり、これには深いドメイン専門知識を持つ人間による手動の試行錯誤が求められる。この設計プロセスは多大なコストと時間を要するだけでなく、特定の問題に特化しすぎるため、他の問題への汎用性が低いという課題を抱えている。 この課題を解決するために、遺伝的プログラミングなどを用いた自動ヒューリスティック設計（AHD）の研究が進められてきたが、従来の構文木に基づく手法は、人間が定義した算術演算子の組み合わせに制限されるなど、柔軟性と表現力に限界があった。…

核心：何を提案したのか

本研究では、ヒューリスティックの発見プロセスを、単なる統計的なサンプリングではなく「帰結グラフ（Entailment Graph）」上での逐次的な意思決定プロセスとして再定義する、PathWiseと呼ばれるマルチエージェント推論フレームワークを提案している。 帰結グラフは、生成された各ヒューリスティックをノードとし、それらがどの親からどのような論理で導出されたかを示すエッジで構成される構造であり、探索の軌跡をコンパクトかつ状態を保持したメモリとして機能させる。 このアプローチの核心は、ヒューリスティックの生成をマルコフ決定過程（MDP）として定式化した点にある。これにより、システムは現在のグラフの状態を観察し、過去の成功や失敗の履歴を踏まえた上で、次にどのような変更を加えるべきかを計画することが可能になる。…

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