近傍解の2つ統計量の推定に基づく組合せ最適化手法

カテゴリ: 部門大会

論文No: GS10-6

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

発行日: 2022/08/24

タイトル(英語): A Combinatorial Optimization Method Based on the Estimation of the Two Statistics of Neighborhood Solutions

著者名: 角田 英一郎（大阪工業大学）,重弘 裕二（大阪工業大学）

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

キーワード: 組合せ最適化|近傍探索|combinatorial optimization|neighborhood search

要約(日本語): 著者らはこれまでに、複数の近傍操作を使い分けながら効率良く解の探索を行う手法について考察を行っている。具体的には、近傍操作により得られる解の評価値の統計量を推定することで適切な近傍操作を選択するというものである。しかし、従来の手法で計算機実験を行ったところ適切でない近傍操作を選択していることがあった。
 そこで本稿では、組合せ最適化問題の近傍解を「解改善確率」と「改善時の改善量の期待値」と名付けた2つの統計量で表し、それぞれを推定することで、複数の近傍操作を使い分け効率よく解探索を行う手法について考察する。また、近傍解の統計量については、ベイズ推定と忘却係数付き逐次最小二乗法によって推定を行う。この手法を組合せ最適化問題である巡回セールスマン問題に対して適用し計算機実験を行った。