パイナリー二次計画問題に対するk-opt局所探索法のパラメータについて

概要

論文の詳細を見る
バイナリー二次計画問題(Binary Quadratic Programming Problem, BQP)に対する,k-opt局所探索法(k-opt法)は現在のところ,BQPに対して最も有効とされている局所探索法である.現在までに,二つのk-opt法が知られており,そのいずれも一つのパラメータを有している.そのパラメータによって,効率的に近傍解生成の打切りを行うことができ,k-opt法自体の計算時間を大幅に短縮できる.しかしながら,そのパラメータに関しては十分な検討がなされていない.本論文では,k-opt法で設定されるパラメータに焦点をあてる.ランダムに生成された初期解を用いた両k-opt法,貧欲解法により生成された初期解からスタートする両k-opt法の実験から,適切なパラメータ値の設定は,局所探索法により最良の結果を得る場合には難しく,最良のパラメータ設定は,扱う問題例に依存することを示す.さらに,より効率的なパラメータ値の設定方法を考えるために,パラメータ値をk-opt法の中で変動させる方法についての検討も行う.
社団法人電子情報通信学会の論文
2001-03-09