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

作     者：李元香 项正龙 夏界宁 LI Yuan-Xiang;XIANG Zheng-Long;XIA Jie -Ning

作者机构：武汉大学计算机学院 

基　　金：国家自然科学基金(61672391)资助~~ 

出 版 物：《计算机学报》 (Chinese Journal of Computers)

年 卷 期：2019年第42卷第6期

页      码：1161-1173页

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

主 题 词：模拟退火算法 动力系统 收敛性分析 弹性系数 弹性势能 演化计算 

学科分类：0810[工学-土木类] 0808[工学-自动化类] 0839[0839] 08[工学] 0835[0835] 0811[工学-水利类] 0812[工学-测绘类] 081202[081202] 

核心收录：

D　O　I：10.11897/SP.J.1016.2019.01161

馆 藏 号：203679215...