解空間の階層構造に基づく組合せ最適化手法における縮退対処の分析

カテゴリ: 部門大会

論文No: GS11-2

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

発行日: 2023/08/23

タイトル(英語): Analysis of Degeneracy-handling in Combinatorial Optimization Method Based on Hierarchical Structure in Solution Space

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

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

キーワード: 組合せ最適化|メタヒューリスティクス|多点探索|集中化|局所探索法|Combinational Optimization|Metaheuristics|Multi-point Search|Intensification|Local Search

要約(日本語): 実社会のシステムにおける運営などで生じる問題の多くは組合せ最適化問題として定式化可能である。こうした問題は離散的構造を有しており，解表現や評価方法が多様である。メタヒューリスティクスは汎用性が高く，これらに有効である。本研究室では，メタヒューリスティクスとして解空間の階層構造に基づく組合せ最適化手法を提案している。本手法は数値実験により，その有効性が検証されている。本手法には複数の探索点が同一経路を探索してしまう課題が確認されている。本研究室ではこれを縮退と定義づけた。縮退は計算資源の浪費や探索点間の相互作用の弱化といった悪影響を引き起こす。本稿では縮退に着目し，本研究室から提案されている対処をまとめ，またその分析と考察を行う。