技術的概要：学習済み最適化方策からのヒューリスティックプログラムの教師認識進化

1. 問題定義

組み合わせ最適化問題（スケジューリング、経路探索、グラフ最適化など）は、しばしばコンパクトで解釈可能なヒューリスティック規則に依存しています。これらの規則は高速で展開が容易ですが、設計には通常、大幅なドメイン専門知識と経験的な調整が必要です。最近の大規模言語モデル（LLM）に基づく自動ヒューリスティック設計（AHD）手法は、進化探索を通じて実行可能なヒューリスティックを生成する可能性を示しています。しかし、既存のアプローチは、進化を導くために主に遅延型のエンドポイント性能（完全なロールアウト後の最終目的値）または内部の LLM フィードバック（テキストによる反省、集団統計）に依存しています。

このエンドポイントフィードバックへの依存は、探索信号の粒度を制限します。本論文は、学習済み最適化方策（深層強化学習またはニューラル組み合わせ最適化を通じて訓練されたもの）が、現在十分に活用されていない豊富なアクションレベルの行動情報を含んでいると仮定しています。これらのニューラル方策は通常ソルバーとして使用されますが、特定の状態における候補決定に対する選好を提供する「行動の教師」として機能し得ます。課題は、これらの学習済み方策を活用して、最終的なプログラムが教師を模倣したり、展開時にニューラル推論を行ったりすることなく、静的で実行可能なヒューリスティックプログラムの進化を導くことです。

2. 手法

著者は、独立して訓練されたブラックボックス最適化方策を外部の行動教師として、LLM ベースのヒューリスティック探索ループに統合する教師認識進化フレームワークを提案します。

中核メカニズム：オンポリシー教師診断

教師を展開したり、直接模倣に使用したりするのではなく、このフレームワークは、候補ヒューリスティックプログラムが実行中に訪れる状態に対して教師をクエリします。

• 状態サンプリング: 候補ヒューリスティック $h$ に対して、システムをロールアウトして状態の軌道 $S_h$ を生成します。
• 教師クエリ: 教師方策 $T$ をこれらの特定の状態に対してクエリし、その選好するアクション $a_T(s)$ またはアクションスコア $Q_T(s, a)$ を決定します。
• 整合シグナル: システムは以下を計算します：
  • トップ 1 一致率: 候補のアクションが教師の選好するアクションと一致する頻度。
  • 正規化教師値: スコアが利用可能な場合、実行可能なアクション集合に対する候補が選択したアクションの正規化された値。
  • パーセンタイル順位: 教師による順序付けにおける候補のアクションの順位。

教師誘導による反省と修正

これらの診断シグナルは、LLM アナライザーに対する実行可能なフィードバックに変換されます。軽量なタスクインターフェースアダプターにより、フィードバックが文脈的に適切であることが保証されます。アナライザー LLM は、3 つの特定の教師誘導オペレーターに基づいて修正要約を生成します：

1. 構造的書き換え: 不一致が構造的な失敗の反復を示す場合、高レベルの決定コンポーネントを変更します。
2. パラメータ較正: プログラムが妥当なアクションを選択しているが、教師に対して局所的に較正がずれている場合、重み、しきい値、またはゲートを調整します。
3. メカニズムレベルの融合: 目的が強いメカニズムと整合性が強いメカニズムを組み合わせ、教師由来の行動バイアスを組み込みつつ性能を維持します。

集団管理

このフレームワークは、パレート支配ソートを用いた多目的選択戦略を採用します。各候補は、ベクトル $z(h) = (F(h), -Align(h))$上で評価されます。ここで、$F(h)$はタスク目的（最小化）、$Align(h)$ は教師との整合（最小化）です。

• 選択: 最終的なヒューリスティックは、教師への忠実度ではなくタスク性能に基づいて選択されます。これにより、出力は教師の圧縮版ではなく、特定のタスクに対して最適化された静的で効率的なプログラムとして維持されます。

3. 主要な貢献

本論文は、4 つの主要な貢献を主張します：

1. 定式化: 独立して訓練されたブラックボックス最適化方策を、LLM ベースのヒューリスティック進化のための外部行動教師として使用する概念を導入します。
2. サンプリングオンポリシー教師整合: 候補によって誘発された状態に対して教師をクエリし、その選好を局所的な行動探索シグナルに変換する手法を提案します。これは標準的な模倣学習とは異なります。
3. 教師認識反射進化: 教師との整合要約と不一致事例を活用して、ヒューリスティックプログラムの構造的およびパラメトリックな修正を導くフレームワークです。
4. 実証的検証: 4 つの逐次組み合わせ最適化ドメイン（JSSP、TSP、CVRP、MaxCut）における実証により、学習済み方策が静的で解釈可能かつ効率的なヒューリスティックの発見を効果的に導くことを示しました。

4. 実験結果

この手法は、4 つのベンチマーク：ジョブショップスケジューリング（JSSP）、巡回セールスマン問題（TSP）、容量制約付き車両経路問題（CVRP）、および MaxCut において評価されました。

• 性能: 提案手法は、分布内および分布外（OOD）の設定において、性能駆動型の LLM ベースライン（EoH、ReEvo）および古典的なディスパッチング規則を一貫して上回りました。
  • JSSP: 10x10、15x15、および 20x20 のインスタンスにおいて最良のメイクスパンを達成し、より大規模なランダムインスタンスおよび Taillard ベンチマークへの優れた汎化性を示しました。
  • 経路探索（TSP/CVRP）: LLM 進化ヒューリスティックの中で最良の解の質を生み出し、静的プログラムの速度を維持しながら、専用ソルバー（LKH など）とのギャップを縮小しました。
  • MaxCut: 訓練分布において競争力のある性能を示し、異なるグラフ分布（例：Barabási–Albert から Erdős–Rényi へ）およびスケールへの強力な転移性を示しました。
• 効率性: 生成されたヒューリスティックは、展開時にニューラル推論を必要としない静的な実行可能プログラムです。これらは、ガイダンスに使用された学習済みニューラル方策（教師）よりも実質的に高速です。
• アブレーション研究: 教師由来のフィードバックを除去すること（「性能のみ」）は、結果を一貫して劣化させ、行動シグナルの価値を確認しました。特定のコンポーネント（アナライザーガイダンス、教師誘導オペレーター、またはパレート更新）を除去することも、特に OOD 汎化において性能低下をもたらしました。

5. 意義と主張

本論文は、学習済み最適化方策を、自動ヒューリスティック発見のための行動フィードバック源として転用できると論じています。その意義は、ニューラル方策の役割を、最終的なソルバーから局所的な決定レベルのフィードバックの源へとシフトさせる点にあります。

• 相補性: 教師の選好は、エンドポイントの適合性に対する補完的なシグナルを提供し、有用な学習バイアスを維持しつつ特定の弱点を修正するヒューリスティックへの探索を導きます。
• 静的対ニューラル: このフレームワークは、学習済みニューラル方策の高い性能と、静的ヒューリスティックの解釈性・効率性の間のギャップを成功裡に橋渡しします。
• 謙虚さ: 著者は限界を認め、この手法は整合可能な学習済み教師、タスク固有のインターフェースアダプター、およびアナライザー呼び出しを必要とすることを指摘しています。すべてのソルバーを置き換えることを主張するのではなく、静的ヒューリスティックの発見プロセスを改善するものとしています。

要約すると、この研究は、学習済み方策を「模倣すべきソルバー」ではなく「行動の教師」として扱うことで、深層学習の豊富な局所的決定シグナルを活用しつつその計算オーバーヘッドを継承することなく、高性能かつ効率的な静的ヒューリスティックを進化させることができることを示しています。