解空間の階層構造に基づく組合せ最適化手法における縮退の解消と探索点制御の基礎検討

カテゴリ: 部門大会

論文No: GS10-5

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

発行日: 2022/08/24

タイトル(英語): Basic Study on Degeneracy Resolution and Search Point Control in a Combinatorial
Optimization Method Based on a Hierarchical Structure in Solution Space

著者名: 仲田 圭吾（東京都立大学）,関井 大輔（東京都立大学）,田村 健一（東京都立大学）,安田 恵一郎（東京都立大学）

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

キーワード: 組合せ最適化|メタヒューリスティクス|近接最適性原理|多点探索|局所探索法|Combinational Optimization|Meta-heuristics|Proximate Optimality Principle|Multi-point Search|Local Search

要約(日本語): 社会における諸問題の多くは組合せ最適化問題として定式化できる。これらは離散的構造を有しており，問題ごとに解表現などの形態が異なる。メタヒューリスティクスは多様な問題に対応できるためこれらに有効であり，その中でも著者らの提案した解空間の階層構造に基づく組合せ最適化手法は従来手法のTabu Searchより優れた探索性能であることが知られている。事前研究より，多点化した当該手法では探索点が重複しその後の経路が同一化する「縮退」という課題が存在し，探索点間の相互作用を弱化させることがわかっている。これにより探索性能が悪化するほか，当該手法に加えた改良の効果にも影響を与える。本研究では，当該手法の利点である汎用性を損なわない形で縮退を解消しつつ改良を加え，その性能を向上させることを目的とする。当該手法の探索方針を阻害しないことに留意しつつ，多点探索における探索点制御に軸を置いた改良を検討する。