模拟退火算法

模拟退火算法

    模拟退火算法(Simulated Annealing,简称SA算法)是模拟加热熔化的金属的退火过程，来寻找全局最优解的有效方法之一。

    模拟退火的基本思想和步骤如下：

     设S＝{s1,s2,…,sn}为所有可能的状态所构成的集合，  f：S—R为非负代价函数，即优化问题抽象如下：

寻找s*∈S，使得f(s*)＝min f(si)      任意si∈S

（1）给定一较高初始温度T，随机产生初始状态S

（2）按一定方式，对当前状态作随机扰动，产生一个新的状态S’

S’＝S＋sign(η).δ

其中δ为给定的步长， η为

 [－1,1]的随机数

   计算Δ＝f(S’)－f(S)

（3）若Δ<0，则令S＝S’，转第(5)步

（4）若Δ≤0，则以概率exp(－Δ/T)接受S’，即S＝S’

具体操作：产生一个在[0，1]上服从均匀分布的随机数x，若x<exp(－Δ/T)，则S＝S’

          否则S保持不变

(5)按一定方式降温，使T＝

， < Ti，

     如： ＝αTi，

    习惯上取α∈(0.8，0.9999)

(6)检查退火是否结束

    是——转向第(7)步

    否——转向第(2)步

(7)以当前Si作为最优解输出

注：1、结束标志：温度是否小于某一阀值(循环次数)

f的值变化是否明显

2、初始温度的高低：下降是否充分慢对结果有影响