近傍解の評価値の改善量の期待値に基づく近傍探索法

スポンサーリンク

概要

論文の詳細を見る
本稿では,遺伝的アルゴリズムおける交叉のような操作を用いず,近傍操作のみを用いて,大規模な組合せ最適化問題に対して効率良く解探索を行う方法を,確率論的観点から考察する.その元となる発想は以下の通り.1) 単位近傍操作の反復からなる多数の近傍操作を解に適用する.2) 近傍操作により得られる解の評価値の確率分布を推定する.3) 最良解の評価値の改善量の期待値を最大化する近傍操作を選択する.これらの発想と確率論の基礎から,解探索のための手法が導かれる.また,巡回セールスマン問題に対する計算機実験により,提案する手法の正当性が確認される.
2012-02-23

著者

関連論文

もっと見る

スポンサーリンク