解空間の階層構造に基づく組合せ最適化手法におけるサイクリングの対処

カテゴリ: 部門大会

論文No: GS7-2

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

発行日: 2024/08/28

タイトル(英語): To handle Cycling in Combinatorial Optimization Methods Based on Hierarchical Structure of Solution Space

著者名: 熊坂 司希（東京都立大学）,李 琦（東京都立大学）,田村 健一（東京都立大学）,安田 恵一郎（東京都立大学）

著者名(英語): Motoki Kumasaka (Tokyo Metoropolitan University),qi Li (Tokyo Metoropolitan University),Kenichi Tamura (Tokyo Metoropolitan University),Keiichiro Yasuda (Tokyo Metoropolitan University)

キーワード: 組合せ最適化|メタヒューリスティクス|近接最適性原理|局所探索法|サイクリング|Combinatorial optimization|meta-heuristics|proximity optimality principle|local search methods|cycling

要約(日本語): 著者らは組合せ最適化問題における新概念「解空間の階層構造」を提案し，それに基づくメタヒューリスティクス「解空間の階層構造に基づく組合せ最適化手法」を開発した。本手法は決定論的探索を行う手法であるため，同じく決定論的探索を行うTabu Searchと同様に探索点のサイクリングが発生し，探索性能低下の一因となっていることが確認されている。
そこで本論文ではサイクリングの発生に応じてパラメータを調整し，サイクリングに対処する機能を有する改良手法を提案する。具体的には，本手法において探索済みとして扱う領域である「脱出領域」が，サイクリングが発生した領域と一致するようにパラメータを調整することでこれを実現する。提案手法の性能を、巡回セールスマン問題、ナップサック問題、フローショップスケジューリング問題、二次割当問題の代表的なベンチマーク問題を用いた数値実験により検証する。