文献

J-GLOBAL ID：200902279738329909   整理番号：09A0022202

AR(1)モデルによる組合せ最適化問題の近傍に対する解析

PROBABILISTIC ANALYSIS OF NEIGHBORHOOD USING AR(1) MODEL FOR COMBINATORIAL OPTIMIZATION PROBLEMS

著者 (1件)： 加地太一 (小樽商大)
資料名： 日本オペレーションズ・リサーチ学会和文論文誌  (Transactions of the Operations Research Society of Japan)
巻： 51  ページ： 112-135  発行年： 2008年12月 
JST資料番号： L5172A  ISSN： 1349-8940  資料種別： 逐次刊行物 (A)
記事区分： 短報  発行国： 日本 (JPN)  言語： 日本語 (JA)

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

シソーラス用語： *組合せ最適化問題 ,  近傍探索法 ,  最適化手法 ,  探索理論 ,  *自己回帰モデル ,  仮説検定 ,  統計量 ,  Gauss則 ,  *原価管理 ,  理論

分類 (2件)： システム最適化手法  (IA02050Z) ,  数理計画法  (KA03030M)

引用文献 (10件)：

• EIKELDER, H. M. M. A probabilistic analysis of local search. Meta-Heuristics : Theory & Applications. 1996, 605-618
• GLOVER, F. Tabu Search. 1997
• KAJI, T. Probabilistic analysis of local search using AR(1) model in the graph partitioning problem. Proceedings of the Fifth Metaheuristics International Conference, 2003. 2003
• 小西貞則. 情報量基準. 2004
• PARDALOS, P. M. Handbook of Applied Optimization. 2002

タイトルに関連する用語 (5件)： Ar ,  モデル ,  組合せ最適化問題 ,  近傍 ,  解析