Evaluating Real-World Generalizability of Algorithm Selection Models

技術要約：アルゴリズム選択モデルの実世界における汎用性の評価

問題提起
アルゴリズム選択（AS）は、測定可能な問題特性（ランドスケープ特徴量）と過去のパフォーマンスデータを利用して、特定の問題インスタンスに対して最も適切な最適化アルゴリズムを自動的に特定することを目的としている。ASモデルは、制御された合成ベンチマーク・スイート（BBOBやCECなど）を用いて広範に開発・評価されてきたが、実世界の最適化ランドスケープに対する汎用性はほとんど検証されていない。既存の文献は、合成ベンチマークが、実用的な問題に固有の構造的複雑性、ノイズパターン、およびドメイン固有の制約を欠いていることが多いことを示唆している。その結果、合成データで学習されたモデルは、特定のランドスケープ分布に過学習し、現実的かつドメイン固有のタスクに適用した際に失敗する可能性がある。本研究は、ASモデルが合成的なアカデミック・ベンチマークから実世界の問題セットへとどの程度転移できるかという、重要なギャップに対処するものである。

手法
本研究では、以下の4つの異なる問題ソースを含む、体系的なクロスベンチマーク評価フレームワークを採用している。

1. 合成ベンチマーク： Black-Box Optimization Benchmarking (BBOB) スイート、および IEEE CEC 実パラメータ単一目的ベンチマークシリーズ。
2. 実世界ベンチマーク： ロボティクス軌道最適化問題（ROB）および無人航空機（UAV）経路計画問題のセット。

実験設定には、8つの集団ベース単一目的最適化手法（AGSK、DE、PSO、LSHADEなどを含む）からなるアルゴリズム・ポートフォリオが含まれる。著者らは、次元数6、12、18、24、30においてパフォーマンスを評価している。

特徴量抽出と前処理：
本研究では、flacco パッケージから派生した探索的ランドスケープ解析（ELA）特徴量（インスタンスあたり62個の特徴量）を利用している。データの表現が汎用性に与える影響を調査するため、著者らは以下の様々な前処理戦略をテストしている。

• スケーリング： なし、yスケーリング（目的関数のみ）、およびx-yスケーリング（決定変数と目的関数の両方）。
• サンプリング： フルサンプル（10,000点）対 ダウンサンプリング（50d点）。

モデリングと評価：
ランダムフォレスト（RF）回帰器を用いて、与えられた問題インスタンスに対する各アルゴリズムの正規化された精度スコアを予測する。ASの性能は、予測された最良アルゴリズムのスコアと真の最良アルゴリズムのスコアの差として測定され、これは訓練セットで観察された最良ソルバーの平均パフォーマンスを予測する「ダミー」ベースラインと比較される。評価は厳格なクロスベンチマーク・プロトコルに従う。すなわち、モデルを一つのベンチマークで学習させ、残り4つのベンチマークおよびマージド・ベンチマーク設定ですべてテストする。さらに、ベンチマークペア間のELA特徴量分布の統計的な類似性を定量化するために、クロスマッチテストが採用されている。

主要な結果

• 限定的な汎用性： ほとんどのクロスベンチマーク・シナリオ、特に低次元（6d）において、合成ベンチマーク（BBOB/CEC）で学習されたASモデルは、実世界の問題（ROB/UAV）に対してテストされた際、ダミーベースラインを上回ることができない。その逆も同様である。
• 次元数の影響： 一部の散発的なポジティブな転移（例：6dにおけるスケーリングなしでのCECからUAVへの転移、または12dにおけるCECからUAVへの転移）が観察されたものの、汎用性は一貫性を欠いていた。高次元（24d、30d）においては、ベースラインに対する改善はわずか（0.1–0.2）であり、ソースとターゲットの組み合わせや前処理の選択に強く依存していた。
• 「単一最良ソルバー」への過学習現象： 予測頻度の分析により、汎用性が低い大きな原因が明らかになった。学習ベンチマークが単一の最良パフォーマンスを示すアルゴリズム（例：BBOBにおけるEBOwithCMAR、またはUAVにおけるAPGSK_IMODE）によって支配されている場合、ASモデルはその同じアルゴリズムを一貫して予測することで過学習する傾向がある。この挙動は実質的にダミーベースラインを模倣しており、選択精度における測定可能な利得をもたらさない。
• 特徴空間の乖離： クロスマッチテストの統計量は、合成ベンチマークと実世界ベンチマークが、ELA特徴空間において大部分が異なる領域を占めていることを裏付けた。BBOBとCECの間にはかなりの重複が見られたが、ロボティクスおよびUAV問題を含むベンチマークは、特に高次元において、合成スイートとの類似性が極めて低かった。スケーリングやダウンサンプリングといった前処理ステップは、特徴空間の重複を増加させたが、それが必ずしもAS性能の向上に直結するわけではなかった。

意義と主張
本論文は、標準的な合成ベンチマークにおける強力なパフォーマンスは、実世界の最適化問題に対する堅牢性や転移性を保証するものではないと主張している。本研究は、構造的な違いが、合成的なランドスケープと実世界のランドスケープの間で、クロスベンチマークの汎用性を根本的に制限していることを強調している。

著者らは、現在のASアプローチは、訓練ドメインとターゲットドメインの間の分布シフトに対処しない限り、実用的な展開には不十分であると結論付けている。彼らは、今後の発展において以下へのシフトが必要であると示唆している。

1. 多様な、より現実的な問題インスタンスを含むベンチマーク・コレクションの拡充。
2. より転移可能な問題特性を捉えることができる特徴表現の開発。
3. 特定のベンチマーク・パフォーマンスの最適化ではなく、クロスドメインの汎用性を明確に目的としたASモデルの設計。

本研究は、現実世界の最適化タスクの不均一性と複雑さを扱うことができるASシステムを開発・評価するために、制御された合成設定を超えていく必要性を強調している。