組合せ最適化に関する一つの仮説

カテゴリ: 部門大会

論文No: TC4-1-4

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

発行日: 2023/08/23

タイトル(英語): A Hypothesis in the Combinatorial Optimization

著者名: 重弘 裕二（大阪工業大学）

著者名(英語): Yuji Shigehiro (Osaka Institute of Technology)

キーワード: 組合せ最適化|近傍操作|確率分布確率分布|combinatorial optimization|neighborhood operations|probabilistic distribution

要約(日本語): 大規模な組合せ最適化問題に対しては，Simulated Annealing のような局所探索法に基づく手法では良い解を得ることができないと考えられており，遺伝的アルゴリズムのような進化的計算手法が採用されることが多い。しかし，進化的計算手法がうまく機能する理由や，局所探索法がうまく機能しない理由については，あまり議論されていないのではないかと思われる。本稿では，任意解と近傍解を評価した結果を正規分布でモデル化し，近傍解に関する定理を導出する。さらに，計算機実験による検証を行った上で一つの仮説を提案し，組合せ最適化について考察する。