大規模かつ高コストな順列組合せ最適化問題に対する分割統治法を用いたサロゲート進化計算

カテゴリ: 部門大会

論文No: TC2-2-2

グループ名: 【C】2024年電気学会電子・情報・システム部門大会

発行日: 2024/08/28

タイトル(英語): A Surrogate-Assisted Evolutionary Algorithm with Divide-and-Conquer Strategy for Large-scale and Expensive Permutation-based Combinatorial Optimization Problems

著者名: 池口 尭（横浜国立大学）,小熊 裕司（IHI）,中田 雅也（横浜国立大学）

著者名(英語): Takashi Ikeguchi (Yokohama National University),Yuji Koguma (IHI Corporation),Masaya Nakata (Yokohama National University)

キーワード: サロゲート進化計算|順列組合せ最適化問題|分割統治法分割統治法|surrogate-assisted evolutionary algorithm|permutation-based combinatorial optimization problems|divide-and-conquer

要約(日本語): 在庫配置最適化など、実社会における最適化問題は、解表現が順列となる組合せ最適化問題(PCOPs)として帰着され、問題のサイズが大規模となり、加えて一回の解評価が高計算コストとなる場合が存在する。本論文では、このような大規模かつ高コストなPCOPsに対し、新たなサロゲート支援型進化計算を提案する。提案法では、大規模な問題を分割し、部分問題ごとに勾配ブースティング決定木を構築する。これによりサロゲートモデルを比較的高精度に構築し、効率的な解探索を期待する。また、サロゲートモデル上では母集団ベースの局所探索法による最適化を行う。解評価回数を制限し、大規模なサイズを持つQAPをベンチマークとした実験では、提案法が既存手法よりも優れた性能を導出したことを示す。