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

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

摘要：粒子群算法对所有粒子采用相同的惯性权重,忽视了单个粒子的特性,导致收敛精度偏低且易陷入局部最优。结合RMSprop算法中对每一个维度进行自适应设置的策略,提出一种自适应惯性权重粒子群优化算法RMSPSO。考虑粒子每一个维度的速度变化及动量,进行自适应动态惯性权重设置,使算法在全局寻优和局部寻优之间达到良好平衡。选取10个典型测试函数,将改进后的粒子群算法(RMSPSO)与4个主流粒子群算法进行实验对比分析,实验结果表明,在单峰、多峰和组合函数上,RMSPSO算法在收敛速度和收敛精度上取得了明显进步。