Markov chain modelling of the solution surface in local search
研究局部搜索方法中解曲面的特性，提出马尔可夫链模型来估计局部最优吸引盆的形状和大小，并通过加权流水时间最小化问题验证该方法。
AbstractWhen local search methods are applied to combinatorial optimisation problems it is the characteristics of the solution surface that determine the effectiveness of the method. This paper aims to advance our understanding of solution surface characteristics. The focus is on the basin of attraction associated with each local minimum; that is the set of solutions from which a particular local minimum is reached by following downhill local search. A Markov chain model is proposed for the behaviour of the function values occurring in a random walk on the solution surface. The probability transition matrix can be estimated and this is used to estimate both the shape and the size of the basins of attraction. In order to test this approach a study is made of the problem of minimising weighted flowtime on unrelated parallel machines.Keywords: local search heuristicslandscapesoptimisationscheduling