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

作     者：李元香 项正龙 张伟艳 LI Yuan-Xiang;XIANG Zheng-Long;ZHANG Wei-Yan

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

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

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

年 卷 期：2020年第43卷第5期

页      码：796-811页

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

主 题 词：模拟退火算法 弛豫模型 时间复杂性分析 动态设置 停止准则 

学科分类：08[工学] 081202[081202] 0812[工学-测绘类] 

核心收录：

D　O　I：10.11897/SP.J.1016.2020.00796

馆 藏 号：203930332...