经典算法：模拟退⽕（SA ）算法
⼀、概念
模拟退⽕算法(SA) 来源于固体退⽕原理，是⼀种基于概率的算法。 五维空间模拟退⽕算法从某⼀较⾼初温出发，伴随温度参数的不断下降，结合概率突跳特性在解空间中随机寻⽬标函数的全局最优解，即在局部最优解能概率性地跳出并最终趋于全局最优。模拟退⽕算法是通过赋予搜索过程⼀种时变且最终趋于零的概率突跳性，从⽽可有效避免陷⼊局部极⼩并最终趋于全局最优的串⾏结构的优化算法。 模拟退⽕算法包含两个部分即Metropolis算法和退⽕过程,，分别对应内循环和外循环。
退⽕过程是外循环，将固体达到较⾼的温度（初始温度T（0）），然后按照降温系数alpha使温度按照⼀定的⽐例下降，当达到终⽌温度Tf 时，冷却结束，即退⽕过程结束。
Metropolis算法是内循环，即在每次温度下，迭代L次，寻在该温度下能量的最⼩值（即最优解）。在该温度下，整个迭代过程中温度不发⽣变化，能量发⽣变化，当前⼀个状态x(n)的能量⼤于后⼀个状态x(n+1)的能量时，则接受状态x(n+1)。但是如果下⼀状态的能量⽐前⼀个状态的能量⾼时，设置⼀个接受概率p，即如果下⼀状态的能量⽐前⼀个状态的能量⾼，则接受下⼀状态的概率为P。⼆、接受概率 p
为了避免局部最优，当f(x )≤f(x )时不是直接拒绝f(x )，⽽是以⼀定概率p∈[0,1]接受新解，且f(x )与f(x )越相近，p值越⼤：
⼜需要满⾜p∈[0,1]，最终定义为：
特点：
1、接受新解的概率p越⼤，解空间搜索范围越⼩
2、搜索范围前期⼤，后期⼩。前期避免陷⼊局部最优，后期注重局部搜索。
3、随机接受新解的概率p∈[0,1]，若为0，类似于爬⼭法，若为1，类似于蒙特卡洛
⼀般来说，p的取值还和时间t有关，因此定义p
：
电子技术应用
Ct可以看作是时间的函数，于是接受新解的概率p就可以随时间变化：随着时间增加，Ct变⼤。
由于搜索前期，我们希望范围较⼤，更倾向于接受新解，p则需要变⼤，⽽P和Ct成负相关，所以Ct较⼩。反之随着时间增长，Ct变⼤
三、启发式搜索过程
假设求最⼤值问题：
（1）随机⽣成⼀个解A，计算解A对应的⽬标函数值f(A)
（2）在A附近随机⽣成⼀个解B，计算解B对应的⽬标函数f(B)
（3）如果f(B)>f(A)，那么将解B赋值给A，然后重复上述步骤（爬⼭法）；如果f(B)≤f(A)，那么我们计算接受B的概率p ，然后⽣成⼀个
[0,1]的随机数r，如果r<p ，我们将解B赋值给解A，然后重复上⾯步骤；否则返回(2)，在原来的A附近重新⽣成⼀个解B，然后继续。
j i j j i t t t
注：⽣成随机数是在区间【0,1】产⽣⼀个均匀分布的随机数ϵ
问题：
1、优化问题有约束条件怎么办？
1. 在（2）中直接判断新解B是否满⾜约束条件，不满⾜可以直接构造新解。中华人民共和国票据法
2. 在原来⽬标函数值的基础，加⼊罚函数。效果是如果不满⾜约束，这个值要么很⼤要么很⼩。⽤这样的⽅法转换成⽆约束问题。
2、Ct 如何设置
1. 定义初始温度T0，温度下降公式为 T =αT
，α常取0.95。Ct取倒数是为了保证Ct关于t递增
安徽农业科学
2. 所以接受新解的概率 p深海异种
定义为：
① 当温度⼀定时， Δf 越⼩，p越⼤。
② Δf ⼀定时，温度越⾼，p越⼤。
3、迭代终⽌条件
1. 给定迭代次数
男性黑人2. 达到⼀定温度
3. 到的最优解连续M次⽆变化
t+1t t
4、如何在A 附近⽣成⼀个新解B 具体问题具体分析
如：matlab中内置函数产⽣新解的⽅式随机产⽣⼀组随机数(y ,y ,y …,y )，其中y 服从N(0,1)计算(z ,z ,z …,z )，其中z =四、实例应⽤
参考⽂献
1、
2、123n i 123n i (y +(12y +22y +32...+y )n 2x =n x +i T ∗z i
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议