適合度関数の自己相関関数と改善率の評価による連続k-opt近傍の検討

概要

論文の詳細を見る
最適化問題において,適合度関数のランドスケープはその最適化の困難さと関連する.離散問題においては,ランドスケープは近傍構造によって決定され,巡回セールスマン問題における近傍構造の一つに k-opt があげられる.k-opt 近傍は, k 個のエッジの組替えによって構成される解の集合である.本稿では,k-opt 近傍を用いた局所解探索における適合度関数のランドスケープを自己相関関数を用いて検討を行った.現在の探索点と k-opt 近傍における複数探索ステップ後に得られる探索点との相関が高ければ,探索が容易なランドスケープが構成されていることを意味する.その結果,エッジ数 k が大きければ相関が高いことが明らかとなり,定性的になだらかなランドスケープが形成されていた.しかしながら,エッジ数 k が大きくなると解の収束が遅くなり,その結果,計算コストが増大するという問題が生じた.そのため,エッジ数 k に対する相関とこれを繰り返し回数に対する解の改善率と共に評価し,効率的に大域的な探索が可能な,エッジ数 k を発見した.
一般社団法人情報処理学会の論文
2009-09-03