模拟退火算法的动力系统模型及收敛性分析

Dynamical System Models and Convergence Analysis for Simulated Annealing Algorithm

模拟退火算法是经典的拟物类自然计算方法,其算法设计及应用研究取得了丰硕的成果,模拟退火策略也广泛地融入到现代群智能演化算法的研究之中.早期的性能分析和收敛性分析等理论研究主要是基于随机过程中的马尔科夫链理论,获得了依概率意义的收敛性定理.由于物理和数学已经积淀了深厚的理论基础和丰富的分析工具,可以用来进行随机启发式算法的理论分析和设计.该文试图运用动力系统理论分析模拟退火算法的运行机理和收敛性,将算法搜索最优解的过程比拟为质点作弹性运动,算法运行过程中函数值的变化就是质点在作简谐振动或阻尼振动,建立其常微分方程动力系统模型.运用常微分方程的定性理论对该动力系统模型进行求解和分析,证明了模拟退火算法前、中期的局部收敛性和后期的全局收敛性,对其运行机理给出了合理的理论解释.同时,基于建立的动力系统模型,分析了算法衰减因子与收敛速度的关系,得到了模拟退火算法收敛速度的估计.在此基础之上,提出了一个模拟退火回火算法的改进策略,一个简单易行的回火时刻判据,当弹性系数趋于很小的值时,即可以当作回火时刻.选取几个典型的测试问题,运用基本的模拟退火算法进行实验验证.首先,实验表明数值收敛曲线与理论分析的收敛性结论相吻合;其次,实验验证了收敛速度随退火温度变化的理论分析与数值实验相吻合;同时实验也验证了提出的回火时刻判据的有效性.最后,理论与实验分析表明该文建立的动力系统模型适合描述模拟退火算法.

Simulated annealing algorithm is a classical nature-inspired computational method of imitating physics, which has achieved tremendous results in algorithm design and application researches. Simulated annealing strategy is also widely integrated into researches of modern swarm intelligence evolutionary algorithms. Early theoretical researches for the algorithm on performance analysis and convergence analysis were mainly based on the Markov chain theory in the random process, and obtained the convergence theorem in probability. However, it is difficult to analyze the actual searching behaviors of the algorithm using the Markov chain theory. Also, it’s hard to get some improvement strategies that are useful for the algorithm. The main attempt is to analyze the operating mechanism and the convergence of the simulated annealing algorithm by using dynamical system theory in this paper. Due to mathematics and physics have a solid theoretical foundations and a variety of analytical methods, they can be used to analyzing and modeling this class of random heuristic algorithms theoretically, so that directing designation and improvement of algorithms based on problem characteristics. Therefore, by comparing the searching process of the algorithm to the elastic motion of a particle, the change of the function value during the running of the simulated annealing algorithm can be regarded as the particle doing simple harmonic vibration or damping vibration. So, the dynamical system models of the ordinary differential equation are established for the algorithm according to the principle of elastic mechanics and the algorithm running mechanism. And then, the models are solved and analyzed by using the stability theory of ordinary differential equations. The local convergence of the simulated annealing algorithm in the early-and-mid stage and the global convergence in the late stage are proved, and a rational theoretical explanation of its operating mechanism is stated. Hereafter, based on the dynamical system models, the relationship between the damping coefficient of the model equation and the convergence speed of the algorithm is derived. Furthermore, the convergence speed of the algorithm is inferred, which is associated with the annealing temperature. Based on the theoretical analyses, in response to the drawbacks of the tempering mechanism which usually relied on the experience before, a simple and easy tempering time criterion is proposed in order to improve global searching performance of the simulated annealing algorithm. That is, when the elastic coefficient tends to a small value, it can be used as a tempering point for tempering strategy. Experiments applying the primitive simulated annealing algorithm are implemented in order to verify the theoretical results on several typical test problems. Firstly, these experiments show that the numerical convergence lines coincide with the convergence results of theoretical analysis. Secondly, experiments verify the changing tendency of the convergence speed along with annealing temperature in theory is consistent with the actual numerical experiment. As the annealing temperature decreases, the damping coefficient increases and the attenuation factor decreases, and then the convergence speed increases. Thirdly, the experiments also show the validity of the proposed tempering moment criterion on the benchmark problem. In the end, theoretical and experimental analysis demonstrates that the dynamical system models established in this paper are suitable for describing the simulated annealing algorithm.