解空間の階層構造に基づく多点型組合せ最適化手法における探索点の置換による縮退の対処

カテゴリ：部門大会

論文No：GS8-4

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

発行日：2025/8/20

タイトル(英語)：Handling Degeneracy by Search Points Replacement in Multi-Point Combinatorial Optimization Method Based on Hierarchical Structure in Solution Space

著者名：大澤 希仁（東京都立大学）,田村 健一（東京都立大学）,安田 恵一郎（東京都立大学）

著者名(英語)： Kihito Osawa (Tokyo Metropolitan University),Kenichi Tamura (Tokyo Metropolitan University),Keiichiro Yasuda (Tokyo Metropolitan University)

キーワード：組合せ最適化,メタヒューリスティクス,局所探索法,多様化・集中化,置換,combinatorial optimization,meta-heuristics,local search,diversification and intensification,replacement

要約(日本語)：本研究グループにより開発されたメタヒューリスティクス「解空間の階層構造に基づく多点型組合せ最適化手法」には複数の探索点の探索が同一化してしまう縮退という現象が発生する。本研究ではその探索点の縮退に着目し，縮退対処の戦略を組み込んだ組合せ最適化手法についての検証を行う。
提案手法では縮退の発生が確認された際，その解を別の解と置き換えることによって縮退の対処を行う。また，有効な置き換えを行うために，過去に得られた局所的最適解の中から評価値によって制限をかけ，縮退した点から最も構造が異なる点を置き換え先とする。
提案手法の性能を代表的なベンチマーク問題を用いて検証を行い，数値実験によって性能の向上を確認した。

本誌掲載ページ：1456-1461p

原稿種別：日本語

PDFファイルサイズ：419Kバイト