解空間の階層構造に基づく複数集団型組合せ最適化手法の検討

カテゴリ: 部門大会

論文No: GS7-3

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

発行日: 2024/08/28

タイトル(英語): A Study of Multi-Population Combinatorial Optimization Method Based on Hierarchical Structure in Solution Space

著者名: 渡邉 晨（東京都立大学）,仲田 圭吾（東京都立大学）,田村 健一（東京都立大学）,安田 恵一郎（東京都立大学）

著者名(英語): Shin Watanabe (Tokyo Metropolitan University),Keigo Nakata (Tokyo Metropolitan University),Kenichi Tamura (Tokyo Metropolitan University),Keiichiro Yasuda (Tokyo Metropolitan University)

キーワード: 組合せ最適化|メタヒューリスティクス|局所探索法|多様化/集中化|複数集団|combinatorial optimization|meta-heuristics|Local Search|diversification and centralization|multi population

要約(日本語): 著者らは組合せ最適化問題に関する新たな概念として「解空間の階層構造」を提案し，この概念を活用したメタヒューリスティクス「解空間の階層構造に基づく多点型組合せ最適化手法」を構築してきた。本手法は探索の集中化傾向が強く，また，利用する情報の同一化により発生する縮退という現象が探索効率の低下の要因になり得ることが確認されている。そのため本稿では，「解空間の階層構造に基づく複数集団型組合せ最適化手法」を構築し，探索の集中化緩和による性能向上を図る。本手法では探索点を複数のサブ集団に分割し，探索点間の情報共有レベルを階層化し，さらに縮退を指標としてサブ集団の要素を入れ替え，相互作用をもたらす。代表的なベンチマーク問題であるナップサック問題，巡回セールスマン問題，二次割当問題，フローショップスケジューリング問題を対象に数値実験を行い，探索への影響を検証する。