技術要約：二成分結合型組合せ最適化のための CoEvo-AHD

1. 問題定義

本論文は、解決策が意味的に異なるが相互に依存する2つの決定コンポーネントで構成される**二成分結合型組合せ最適化（CO）問題を取り扱う。核心となる課題は、一方のコンポーネントの変更による実現可能性や目的関数値が、もう一方のコンポーネントの状態に完全に依存することである。その結果、オペレーターの有用性は固有のものではなく関係的（relational）**なものとなる。つまり、単独では優れた性能を発揮するオペレーターであっても、第二のコンポーネントが最適でない状態にある場合、グローバルな解を劣化させる可能性がある。

著者らは、このフレームワークを以下の2つの代表的な問題に適用している：

• Traveling Thief Problem (TTP): ルーティング（巡回セールスマン問題）とパッキング（0–1 ナップサック問題）を結合させたもの。積載量に基づいた移動速度がルート順序に影響し、パッキング計画が各ステップでの重量を決定する。
• Traveling Purchaser Problem (TPP): 市場選択/ルーティングと調達決定を結合させたもの。訪問順序と市場選択が、実行可能な購入オプションとコストを決定し、購入決定が特定の市場を訪問する価値に影響を与える。

既存の大規模言語モデル（LLM）駆動型自動ヒューリスティック設計（AHD）手法は、通常、ヒューリスティックを孤立したアルゴリズム単位または探索戦略（例：構築 vs 修復）として進化させる。これらの手法は、二成分結合型問題において必要とされる**問題構造に起因する相補性（problem-structure-induced complementarity）**を捉えることができない。この問題では、異種な解決策コンポーネント間で相乗的に機能するように、オペレーターを共同進化させる必要がある。

2. 手法：CoEvo-AHD

著者らは、ペアとなるコンポーネント・オペレーターを自動的に発見・洗練するために設計された、LLM駆動のデュアル・ポピュレーション共同進化フレームワークであるCoEvo-AHDを提案している。このフレームワークは、以下の4つのステージで動作する。

2.1 デュアル・ポピュレーション初期化

コンポーネントA（例：ルート・オペレーター）のための $P_A$ と、コンポーネントB（例：パッキング・オペレーター）のための $P_B$ という、2つの独立したオペレーター集団を維持する。

• 初期化: 集団は、手動で指定されたシード・オペレーターとLLM生成オペレーターの混合から始まる。
• 検証: 生成されたすべてのオペレーターは、集団に投入される前に、構文、インターフェース、境界実行、およびコンポーネント実現可能性の検証を受ける。
• インターフェース: オペレーターは、共有情報メモリと外部ツールを用いてグローバルなコンテキストを利用するが、自身の特定のコンポーネントに対する候補更新のみを返す。

2.2 協調的評価

従来の、オペレーターを単独でスコアリングする手法とは異なり、CoEvo-AHDは完全な解に対するペア実行を通じてオペレーターを評価する。

• 選択: 各探索リスタートにおいて、Thompson Sampling戦略を用いて、$P_A$ から1つ、$P_B$ から1つのオペレーターを選択する。
• 交互最適化: 選択されたペアは、探索軌道内で交互に呼び出される。例えば、ルート・オペレーターが都市の置換を提案し、それがパッキング・オペレーターに渡される（またはその逆）。
• 修復と再構成: コンポーネントが結合しているため、中間候補が実行不可能になる場合がある。フレームワークは、ツール拡張型問題環境を利用して、実現可能性の修復、再構成、および完全な目的関数の評価を行う。
• 共有情報: 可変の辞書（shared_info）により、オペレーターは、もう一方のコンポーネントのロジックを直接上書きすることなく、ソフトな探索信号（例：ロードプロファイル、候補挿入キュー）を交換できる。

2.3 集団管理と進化

フレームワークは、集団を洗練させるための共同進化ループを採用している。

• スコアリング: 報酬は、完全な結合解の改善に基づいて計算される。これらの報酬は、個別のスコア（$o_A$ および $o_B$）と、特定のオペレーター・ペアに対するペアワイズ相乗スコア（$S_{ij}$）の3つの統計量を更新する。
• 間引き（Pruning）: パフォーマンスの低いオペレーターは、それぞれの集団から削除される。
• LLM駆動の進化: 空いた枠は、以下の3つの進化的操作によって埋められる：
  1. コンポーネント内変異（Intra-component Mutation）: 単一の親オペレーターを洗練させる。
  2. コンポーネント内同種交差（Intra-component Homogeneous Crossover）: 同一の集団内の2つのオペレーターを再結合する。
  3. コンポーネント間共同交差（Cross-Component Joint Crossover）: 相乗スコアに基づいて最良のペア $(o_A^*, o_B^*)$ を選択し、LLMに対してそれらを統一された調整済みエンティティとして書き直すよう促す。これにより、互換性のある通信プロトコルと相補的な探索仮定を持つオペレーターの生成を促進する。

2.4 ツール拡張型環境

LLMが非効率またはエラーの多い低レベルコードを生成することを防ぐため、フレームワークはコア操作（例：ローカルサーチのデルタ計算、貪欲な再構成、実現可能性チェック）を標準化された呼び出し可能ツールとしてカプセル化している。これにより、LLM生成のオペレーターは、高レベルな近傍設計とコンポーネント間の調整に集中できる。

3. 主な貢献

1. 問題定式化: 二成分結合型COに特化したLLM駆動型AHDを定式化し、オペレーターの有用性を関係的なものとし、異種な決定サブ構造にわたる共同評価が必要であることを定義した。
2. CoEvo-AHDフレームワーク: 以下の特徴を持つ新しい共同進化アーキテクチャを提案した：
   • コンポーネント固有のオペレーター集団。
   • クロスコンポーネントの相互作用を捉えるためのペア実行ベースの評価。
   • 相補的なオペレーター・ペアの選択を導くためのペアワイズ相乗スコアリング。
   • 互いに適合するオペレーターを進化させるためのコンポーネント間共同交差。
3. 構造化された通信とツール: 構造化されたコンポーネント間通信プロトコルと、問題固有の操作を標準化するツール拡張型環境を導入し、LLMが高レベルで堅牢なヒューリスティック・ロジックを生成できるようにした。

4. 実験結果

フレームワークは、TTPおよびTPPベンチマークにおいて、従来の最先端のヒューリスティックおよび最新のLLMベースのベースラインと比較して評価された。

• Traveling Thief Problem (TTP):

  • CoEvo-AHDは、小規模から中規模のインスタンス（TTP20, TTP50）において、MATLS、S5、CoCoなどのベースラインを上回り、最良の結果を達成した。
  • 大規模なインスタンス（TTP100, TTP200）では、CoCoに次ぐ全体平均で2番目の結果を達成したが、MATLSやS5を大幅に上回った。
  • これは、フレームワークが小さな探索空間では結合を効果的に捉えられるが、非常に大きなインスタンスにおける探索の深さには課題があることを示唆している。

• Traveling Purchaser Problem (TPP):

  • CoEvo-AHDは顕著な全体的優位性を示し、5つのインスタンス・スケール（150×100や150×150などの大規模スケールを含む）で最良の結果を達成し、他の3つのスケールでも2番目の結果を達成した。
  • 2番目に優れたベースライン（TA）と比較して平均目的関数値を約2.76%、ALNSと比較して最大**11.42%**削減した。
  • これらの結果は、フレームワークがTPPにおけるルーティングと調達決定の間の相乗効果を活用することに特に効果的であることを示している。

• アブレーション研究:

  • デュアル・ポピュレーション共同進化（片方のコンポーネントのみを進化させる）を削除すると、大幅な性能低下（例：TPPで約11%の低下）を招き、コンポーネントを単独で最適化することは不十分であることを裏付けた。
  • ツール拡張型環境を削除した場合も性能低下（TTPで約5.5%）が見られ、信頼性と効率性のための標準化されたインターフェースの重要性が浮き彫りになった。

5. 意義と主張

本論文は、CoEvo-AHDが、孤立したアルゴリズム・ロールを生成することから、問題構造に起因するオペレーターの相補性をモデリングすることへの、LLM駆動型AHDの転換を象徴していると主張している。異種なオペレーター集団を明示的に共同進化させ、それらを共同実行を通じて評価することで、このフレームワークは、決定サブ構造間の強い結合を処理できない既存手法の限界に対処している。

著者らは、本研究を、決定要素が深く相互依存している複雑な実世界の最適化問題に対する、より汎用的な自動ヒューリスティック設計への一歩として位置づけている。彼らは、フレームワークが非常に競争力がある一方で、非常に大規模なインスタンスに対する探索の深さと堅牢性には改善の余地があることを謙虚に述べており、今後の課題として、より多くの結合コンポーネントを持つ問題へのフレームワークの拡張を目指すと述べている。