模拟退火算法的弛豫模型与时间复杂性分析

A Relaxation Model and Time Complexity Analysis for Simulated Annealing Algorithm

模拟退火算法的设计思想来源于对金属高温下热运动的模拟,其理论基础是统计物理和气体运动论.本文将模拟退火算法的运行比拟为气体的运动,基于经典的气体输运理论,特别是BGK弛豫方程,提出并建立了模拟退火算法弛豫时间模型.对此模型进行整体和局部的分析,给出了退火温度和退火过程的马尔科夫链长度的理论估计.依据理论估计,提出了预退火与全退火的两阶段退火策略,以便算法运行时对马尔科夫链长度进行动态设置.随后,进一步分析了退火过程的时间复杂性,在此基础上,结合退火温度设置和前期建立的动力系统模型,分析了模拟退火算法的总体时间复杂性,所得的理论分析结果与早期基于大量实验分析的经验结果一致,并得到了一个有实用价值的算法停止准则.最后,通过测试问题的求解进行实验分析与验证,实验结果表明了马尔科夫链长度动态设置法的有效性,与通常的马尔科夫链长度固定设置法比较,动态设置法的马尔科夫链总长度比固定法少30%以上,实验结果也表明了本文提出的算法停止准则的有效性,两方面的实验分析也有效地支持了时间复杂性分析的理论结果.

Simulated annealing algorithm,which comes from the simulation of thermal motion of metal at high temperature,is of deep theoretical foundations from statistical physics and gas movement theory.Early theoretical researches for simulated annealing algorithm on convergence analysis and time complexity analysis were mainly based on the Markov chain theory in the random process,and only obtained the analysis conclusion in probability.Due to the simulated annealing algorithm has statistical physical theory foundations,which can be used to analyzing and modeling by a variety of mathematical and physical analysis methods.In this paper,the algorithm is compared to the gas movement.By comparing the searching process of the simulated annealing algorithm to the gas movement to the equilibrium state,the change of the function value during the searching of the simulated annealing algorithm can be regarded as the particles’relaxation process.Built on the classical gas transport theory,especially the BGK relaxation equation,a relaxation time model for the algorithm is proposed and established.Thus,by solving the model integrally and partially,some theoretical estimation is gained about the annealing temperature and the Markov chain length setting of the algorithm.Based on the proposed relaxation model,a two-stage annealing strategy including pre-annealing and full-annealing is raised to set the Markov chain length dynamically along the algorithm process.At the same time,a rough estimate of the initial temperature of the algorithm is obtained.Therefore,based on the proposed dynamical Markov chain length setting,we first analyze the running time complexity of a single annealing process.Then,the relaxation time model is developed to analyze the total time complexity of the algorithm by combining the set of annealing temperature and the pre-established dynamical system models.Following the approach,the theoretical total time complexity of the simulated annealing algorithm is derived,which is consistent with the early empirical conclusion summarized from a large number of experiments.The time complexity of the algorithm is a constant related to the complexity of the problem.In addition,a novel stop criterion for stopping the algorithm process is proposed.Finally,to evaluate the theoretical analysis,several experimental studies are presented on TSP-problem and CEC2014 benchmark functions.Firstly,the results show that the Markov chain length setting by the dynamic method can be lower 30%total Markov chain length than the empirical fixed setting method,and reduce the time complexity required by the algorithm and it greatly improves the efficiency of the algorithm.Secondly,the results show that the stop criterion is available for controlling the algorithm process.Under the dynamic Markov chain setting method,the simulated annealing algorithm can stop searching in the case of multiple consecutive small Markov chain length in the iterative searching process.Thirdly,the experiments also show the time complexity of the simulated annealing,which is a constant related to the problem dimension,is consistent with the empirical conclusion.In summary,theoretical and experimental analyses effectively demonstrate that the relaxation model can be used to analyze the time complexity of the simulated annealing algorithm in theory.