Adversarial Instance Generation and Robust Training for Neural Combinatorial Optimization with Multiple Objectives

技術要約：多目的組合せ最適化におけるニューラル・インスタンス生成と堅牢な学習

問題提起
深層強化学習（DRL）は、多目的組合せ最適化問題（MOCOP）を解くための有望なアプローチとして台頭しており、従来の厳密解法やヒューリスティックなアルゴリズムと比較して優れた効率性を提供している。しかし、これらのDRLソルバーの堅牢性は、特に多様かつ複雑な問題分布に対する性能に関して、未だ十分に探求されていない。単一目的の問題に関する既存の研究は、DRLモデルが「ショートカット学習（近道学習）」、すなわち特定の分布的特徴への過学習に陥り、分布外（OOD）のインスタンスに対して性能が低下する可能性があることを示唆している。相反する複数の目的間のバランスを取るパレートフロントを近似することを目的とするMOCOPの文脈において、ニューラルソルバーの分布シフトに対する脆弱性と、体系的な堅牢性評価の欠如は、実用的な展開における重大な課題となっている。

手法
著者らは、ソルバーの弱点を露呈させるための**選好ベース・アドバーサリアル攻撃（PAA）と、堅牢性を高めるための動的選好拡張防御（DPD）**という2つのコアコンポーネントからなる統一フレームワークを提案している。

1. 選好ベース・アドバーサリアル攻撃 (PAA):

   • 目的: 特定の選好条件下において、DRLソルバーの性能を特異的に低下させる「困難な」インスタンスを生成すること。
   • メカニズム: この手法は、問題の入力（例：TSPにおけるノード座標）を学習可能な変数として扱う。ターゲットとなるソルバーの強化学習損失 $\ell(x; \theta)$ を最大化するために、勾配上昇法を用いて入力 $x$ を反復的に更新する。
   • 損失関数: 損失は、ベースラインで正規化された部分問題損失 $L(\pi|x)$ を、対数確率に乗じたものとして定義される。これを最大化することで、攻撃はソルバーに対し、特定の選好ベクトル $\lambda$ に対して劣悪なパレートフロントの質（ハイパーボリューム、HVで測定）を持つ解を生成させる。
   • 成果: このプロセスにより、異なる選好に適合したアドバーサリアル・インスタンス・プールが生成され、結果として得られるパレートフロントの質を効果的に低下させる。

2. 動的選好拡張防御 (DPD):

   • 目的: アドバーサリアル学習を通じて、ニューラルソルバーの汎化性能と堅牢性を向上させること。
   • メカニズム: DPDは、クリーンなインスタンスと、事前に生成されたアドバーサリアル・プールの混合物を用いてファインチューニングを行う。
   • 困難度を考慮した選好選択 (Hardness-Aware Preference Selection): 学習中、各サンプルされたインスタンスと選好 $\lambda$ に対して、小さなランダム摂動を適用することで、局所的に拡張された選好集合 $\{\lambda'_i\}$ を生成する。モデルのパラメータを固定した状態で、これらの拡張された選好下で生成された解のチェビシェフ値を評価し、最も劣悪な解の質（最大のチェビシェフ値）をもたらす選好 $\lambda'_{adv}$ を選択する。
   • 学習: ソルバーは、このミニバッチ内の「最も困難な」拡張された選好に対して、スカラー化された損失を最小化するように更新される。この戦略は、限定的な選好領域への過学習を防ぎ、モデルに選好空間全体にわたる堅禄な表現を学習させることを目的としている。

主な貢献

• PAA手法: 特定の選好を標的にすることでMOCOPのための困難なインスタンスを体系的に生成する手法を導入し、ニューラルソルバーがその部分問題の弱点に合わせた分布シフトによって著しく損なわれ得ることを示した。
• DPD手法: 困難度を考慮した選好選択をアドバーサリアル学習に統合する防御戦略を提案した。このアプローチは、基礎となるモデルアーキテクチャを変更することなく、過学習を軽減し、分布外の性能を向上させる。
• 包括的な評価: 本フレームワークは、多目的巡回セールスマン問題（MOTSP）、多目的容量制車両配送問題（MOCVRP）、および多目的ナップサック問題（MOKP）の3つの古典的なMOCOPにわたって検証されている。

実験結果

• 攻撃の有効性: PAA手法は、クリーンなインスタンスや他の分布摂動（対数正規分布、ベータ分布、ガンマ分布）と比較して、競争力のあるニューラルソルバー（EMNH, PMOCO, CNH）が生成する解のハイパーボリューム（HV）を大幅に減少させるインスタンスの生成に成功した。いくつかのケースでは、PAAはROCO-RLのような既存の学習ベースの攻撃手法を上回った。
• 防御性能: DPDで訓練されたモデル（例：PMOCO-DPD, CNH-DPD, EMNH-DPD）は、一貫した堅牢性の向上を示した。
  • ガウス分布によるOODインスタンスにおいて、DPDで強化されたソルバーは、防御されていない対応モデルと比較して低い最適性ギャップを達成した。
  • 特に、Bi-CVRP100において、WE-CA-DPDモデルはWS-LKHベースラインに対してHVを2.23%向上させ、最大の利得を記録した。
  • DPDモデルは、より大規模なインスタンス（最大200ノード）や多様なベンチマークインスタンス（kroAB100など）においても強力な性能を維持し、多くの場合、厳密解法に匹敵する性能を、大幅に短い推論時間（厳密解法の数時間に対し、数秒）で実現した。
• 効率性: 防御手法は、訓練および推論時の計算オーバーヘッドを最小限に抑えており、DPD訓練済みモデルは、学習不可能な厳密解法（例：WS-DP）よりも数桁高速に動作する。

意義と主張
本論文は、提案されたフレームワークが、ニューラルMOCOPソルバーの堅牢性に関する文献における決定的なギャップに対処することを主張している。PAAを通じてソルバーの脆弱性を明示的に露呈させ、DPDを通じてそれらに体系的に対処することで、著者らは、ニューラルソルバーを分布シフトや選好の変化に対して大幅に堅牢にできることを示している。結果は、困難度を考慮した選好選択を伴うアドバーサリアル学習が、DRLベースの組合せ最適化の汎化性能を高めるための効果的な戦略であることを示唆しており、問題分布が動的で複雑な実世界のアプリケーションへの適用をより現実的なものにしている。著者らは、本研究が将来的な動的な実世界MOCOPやオンライン環境への拡張の基礎を築くものであると結論付けている。