解空間の階層構造に基づく多点型組合せ最適化手法における探索点数に関する分析

カテゴリ: 部門大会

論文No: GS7-4

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

発行日: 2024/08/28

タイトル(英語): Analysis of Population Size in Multi-Point Combinatorial Optimization Method Based on Hierarchical Structure in Solution Space

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

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

キーワード: 組合せ最適化|メタヒューリスティクス|局所探索法|多点探索|探索点数|Combinatorial Optimization|Metaheuristics|Local Search|Multi-Point Search|Population Size

要約(日本語): 著者らは，メタヒューリスティクスとして解空間の階層構造に基づく多点型組合せ最適化手法を提案した。本手法では，「解空間の階層構造」という新しい概念で構築している。このような構造を用いて，現在属する引き込み領域内の集中な探索と未探索の引き込み領域への多様な探索を繰り返す。また，未探索の引き込み領域への移動において，近接最適性原理に基づく探索点間の相互作用を与える。本手法における重要なパラメータである探索点数は，探索性能に大きな影響を与える。探索点数が小さいと，多様性を弱化し，局所的最適解に陥る可能性が高くなる。探索点数が大きいと，多様性を強化できるが，探索効率が低くなり，探索資源の浪費に繋がる可能性がある。そこで本研究は，本手法における探索点数を基礎的に検討することを目的とし，その探索性能や相互作用に与える影響を分析する。