解空間の階層構造に基づく組合せ最適化手法における近傍の生成・受理機構に関する基礎検討

カテゴリ: 部門大会

論文No: PS6-7

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

発行日: 2023/08/23

タイトル(英語): Basic Study on Neighborhood Generation and Acceptance Mechanisms in Combinatorial  Optimization Method Based on Hierarchical Structure in Solution Space

著者名: 敦賀 優斗（東京都立大学）,仲田 圭吾（東京都立大学）,田村 健一（東京都立大学）,安田 恵一郎（東京都立大学）

著者名(英語): Yuto Tsuruga (Tokyo Metropolitan University),Keigo Nakada (Tokyo Metropolitan University),Kenichi Tamura (Tokyo Metropolitan University),Keiichiro Yasuda (Tokyo Metropolitan University)

キーワード: 組合せ最適化|メタヒューリスティクス|局所探索法|近傍|Combinatorial Optimization|Metaheuristics|Local Search|Neighborhood

要約(日本語): システムの大規模・複雑化，計算機能力の大幅な向上に伴い，直接探索に基づく発見的近似解法の枠組みであるメタヒューリスティクスが実用的な組合せ最適化手法として注目されている。
著者らが提案した「解空間の階層構造に基づく組合せ最適化手法」は，上位空間と下位空間における探索から構成されており，上位空間では引き込み領域間の移動による未探索領域の探索を行い，下位空間ではLocal Searchによる引き込み領域内の局所的最適解の探索を行っている。
これらの上位空間と下位空間における探索の振る舞いは，近傍生成機構と近傍受理機構に強く依存する。
上述のことを踏まえ，本研究では，「解空間の階層構造に基づく組合せ最適化手法」の探索性能向上を目的として，上位空間と下位空間の探索における近傍の生成・受理機構に関する基礎検討を行う。