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

• 加地 太一

  小樽商科大学商学部社会情報学科

書誌事項

タイトル別名

• PROBABILISTIC ANALYSIS OF NEIGHBORHOOD USING AR(1) MODEL FOR COMBINATORIAL OPTIMIZATION PROBLEMS
• AR 1 モデル ニ ヨル クミアワセ サイテキカ モンダイ ノ キンボウ ニ タイスル カイセキ

抄録

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

収録刊行物

• 日本オペレーションズ・リサーチ学会和文論文誌

  日本オペレーションズ・リサーチ学会和文論文誌 51 (0), 112-135, 2008

  公益社団法人 日本オペレーションズ・リサーチ学会

キーワード

• 組合せ最適化
• メタヒューリスティックス
• 近傍
• AR(1)プロセス
• 確率的解析

詳細情報

• CRID: 1390001205756167168
• NII論文ID: 110007007981
• NII書誌ID: AA11998080
• DOI: 10.15807/torsj.51.112
• ISSN: 21888280
• ISSN: 13498940
• NDL書誌ID: 9751784
• Web Site: http://id.ndl.go.jp/bib/9751784
• Web Site: https://ndlsearch.ndl.go.jp/books/R000000004-I9751784
• Web Site: https://www.jstage.jst.go.jp/article/torsj/51/0/51_KJ00005105414/_pdf
• 本文言語コード: ja
• データソース種別:
  • JaLC
  • NDL
  • Crossref
  • CiNii Articles
  • KAKEN
• 抄録ライセンスフラグ: 使用不可