Probabilistic analysis of neighbourhood using AR(1) model for combinatorial optimization problems

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.