組合せ最適化問題における近傍解の統計量の推定
組合せ最適化問題における近傍解の統計量の推定
カテゴリ: 部門大会
論文No: GS12-1
グループ名: 【C】2021年電気学会電子・情報・システム部門大会
発行日: 2021/09/08
タイトル(英語): The Estimation of the Statistics of Neighborhood Solutions in the Combinatorial Optimization Problem
著者名: 八木 祐介(大阪工業大学),角田 英一郎(大阪工業大学),重弘 裕二(大阪工業大学)
著者名(英語): Yusuke Yagi (Osaka Institute of Technology),Eiichiro Kakuda (Osaka Institute of Technology),Yuji Shigehiro (Osaka Institute of Technology)
キーワード: 組合せ最適化|近傍探索|combinatorial optimization|neighborhood search
要約(日本語): 多くの組合せ最適化問題は NP 困難であり, 実用上の問題においては大域最適解を求めることが難しいことが多い. そこで, より最適性の高い解を求めるためにメタヒューリスティクスと呼ばれる手法が提案されている. 筆者らはこれまでに, 複数の近傍操作を使い分けながら解探索を行う手法について考察を行っている. 具体的には, 近傍操作により得られる解の評価値について統計量を推定することで, 適切な近傍操作を選択するというものであったが, 計算機実験を行ったところ, 適切でない近傍操作を選択しているかのような挙動を示していた. 本稿では, 複数の近傍操作を使い分ける手法を構築するための準備として, 解探索の進行に伴い, 近傍操作により得られる解の評価値についての統計量がどのように変化していくのかについて, 計算機実験を用いた検討を行う.
PDFファイルサイズ: 1,372 Kバイト
受取状況を読み込めませんでした
