AR(1)モデルによる組合せ最適化問題の近傍に対する解析  [in Japanese] PROBABILISTIC ANALYSIS OF NEIGHBORHOOD USING AR(1) MODEL FOR COMBINATORIAL OPTIMIZATION PROBLEMS  [in Japanese]

Access this Article

Search this Article

Author(s)

Abstract

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

Metaheuristics are powerful methods used to find approximate solutions for hard combinatorial optimization problems. Successful designs of the neighborhood are required in order to construct better metaheuristics algorithms. Analysis of the neighborhood is useful for enhancing the ability of metaheuristics and will allow us to compute the probabilistic average-case analysis for the algorithm of metaheuristics. In the present paper, we attempt to construct a model that enables theoretical probabilistic analysis of the neighborhood. Therefore, we confirm the hypothesis whereby the AR(1) process captures the statistics of walks on the solution spaces of the combinatorial optimization problem and estimate the characteristic quantity on the solution spaces. In addition, we formulate a probabilistic model that captures the feature of the neighborhood using the statistics from the AR(1) process under the hypothesis that the solution variables are jointly Gaussian. However, in the common approach, the probabilistic analysis model is constructed for the restricted version of the neighborhood. Therefore, we introduce an AR(1) model that enables a probabilistic model to be formulated for various types of neighborhood. The theoretical results obtained using the concept of the AR(1) model fit the empirically observed behavior well.

Journal

  • Transactions of the Operations Research Society of Japan

    Transactions of the Operations Research Society of Japan 51(0), 112-135, 2008

    The Operations Research Society of Japan

References:  10

Cited by:  1

Codes

  • NII Article ID (NAID)
    110007007981
  • NII NACSIS-CAT ID (NCID)
    AA11998080
  • Text Lang
    JPN
  • Article Type
    Journal Article
  • ISSN
    1349-8940
  • NDL Article ID
    9751784
  • NDL Source Classification
    ZM31(科学技術--数学) // ZD25(経済--企業・経営--経営管理)
  • NDL Call No.
    Z74-E331
  • Data Source
    CJP  CJPref  NDL  NII-ELS  J-STAGE 
Page Top