模拟退火算法(SAA)C语言与MATLAB实现

本文共987个字,预计阅读时间需要3分钟。

爬山法

在介绍模拟退火算法之前,先介绍一下爬山法。爬山法是一种贪心算法。其目标是要找到函数的最大值,若初始化时,初始点的位置在C处,则会寻找到附近的局部最大值A点处,由于A点出是一个局部最大值点,故对于爬山法来讲,该算法无法跳出局部最大值点。若初始点选择在D处,根据爬山法,则会找到全部最大值点B。这一点也说明了这样基于贪婪的爬山法是否能够取得全局最优解与初始值的选取由很大的关系。

模拟退火算法(Simulated Annealing Algorithm, SAA)的思想借鉴于固体的退火原理,当固体的温度很高的时候,内能比较大,固体的内部粒子处于快速无序运动,当温度慢慢降低的过程中,固体的内能减小,粒子的慢慢趋于有序,最终,当固体处于常温时,内能达到最小,此时,粒子最为稳定。模拟退火算法便是基于这样的原理设计而成。

模拟退火算法从某一较高的温度出发,这个温度称为初始温度,伴随着温度参数的不断下降,算法中的解趋于稳定,但是,可能这样的稳定解是一个局部最优解,此时,模拟退火算法中会以一定的概率跳出这样的局部最优解,以寻找目标函数的全局最优解。如上图中所示,若此时寻找到了A点处的解,模拟退火算法会以一定的概率跳出这个解,如跳到了D点重新寻找,这样在一定程度上增加了寻找到全局最优解的可能性。

模拟退火算法过程

(1)随机挑选一个单元k,并给它一个随机的位移,求出系统因此而产生的能量变化ΔEk
(2)若ΔEk0,该位移可采纳,而变化后的系统状态可作为下次变化的起点;
ΔEk>0,位移后的状态可采纳的概率为

 
式中T为温度,然后从(0,1)区间均匀分布的随机数中挑选一个数R,若R<Pk,则将变化后的状态作为下次的起点;否则,将变化前的状态作为下次的起点。
(3)转第(1)步继续执行,知道达到平衡状态为止。

模拟退火算法流程

模拟退火算法MATLAB实现

计算-x^2-4x+3的最大值:

主函数:

随机数生成函数:

目标函数:

模拟退火算法C语言实现

计算-x^2-4x+3的最大值:

结果

best和best_min是求出的最大值。

读者评分
[评分人数: 2 平均分: 5]

评论