PROBABILISTIC ANALYSIS OF NEIGHBORHOOD USING AR(1) MODEL FOR COMBINATORIAL OPTIMIZATION PROBLEMS
Taichi Kaji · Transactions of the Operations Research Society of Japan · 2008
組合せ最適化問題の有効な近似解法としてメタヒューリスティックスの研究,開発がなされている.メタヒューリスティックスの重要な枠組みの一つである近傍を解析することは,有効な近傍を生成するための知識獲得を可能とし,メタヒューリスティックスの改良につながる知見となりうる.また,アルゴリズムの確率的解析のための基盤となる情報をも提供するものである.そこで本論文では,近傍のコスト分布の特性を確率的に解析する.そのために,解空間における近傍点のランダムな評価値系列がAR(1)プロセスと呼ばれる特徴的な性質を有するという仮定を検証し,解空間および評価値系列の構造を統計的に明らかにする.このAR(1)プロセスから導き出した統計量を用い,さらに,解のコスト分布にガウス性が伴う仮定を利用して,近傍を確率的にモデル化し近傍の特性の解析を試みる.確率的な解析では通常モデルを構築しやすいように,特定の問題,および特定の近傍などを設定してこのような統計量を導出する.しかし,ここで提唱するAR(1)モデルを用いることにより,多くの組合せ最適化問題,あるいは各種の近傍などに対応する一般性に富んだ有効な解析方法を提案する.