智能算法的算法分类

模拟退火算法的依据是固体物质退火过程和组合优化问题之间的相似性。物质在加热的时候，粒子间的布朗运动增强，到达一定强度后，固体物质转化为液态，这个时候再进行退火，粒子热运动减弱，并逐渐趋于有序，最后达到稳定。

模拟退火的解不再像局部搜索那样最后的结果依赖初始点。它引入了一个接受概率p。如果新的点（设为pn）的目标函数f（pn）更好，则p=1，表示选取新点；否则，接受概率p是当前点（设为pc）的目标函数f（pc），新点的目标函数f（pn）以及另一个控制参数“温度”T的函数。也就是说，模拟退火没有像局部搜索那样每次都贪婪地寻找比现在好的点，目标函数差一点的点也有可能接受进来。随着算法的执行，系统温度T逐渐降低，最后终止于某个低温，在该温度下，系统不再接受变化。

模拟退火的典型特征是除了接受目标函数的改进外，还接受一个衰减极限，当T较大时，接受较大的衰减，当T逐渐变小时，接受较小的衰减，当T为0时，就不再接受衰减。这一特征意味着模拟退火与局部搜索相反，它能避开局部极小，并且还保持了局部搜索的通用性和简单性。

在物理上，先加热，让分子间互相碰撞，变成无序状态，内能加大，然后降温，最后的分子次序反而会更有序，内能比没有加热前更小。就像那只兔子，它喝醉后，对比较近的山峰视而不见，迷迷糊糊地跳一大圈子，反而更有可能找到珠峰。

值得注意的是，当T为0时，模拟退火就成为局部搜索的一个特例。

模拟退火的伪码表达：

procedure simulated annealing

begin

t:=0;

initialize temperature T

select a current string vc at random;

evaluate vc;

repeat

repeat

select a new string vn in the neighborhood of vc; (1)

if f(vc)

鹏仔微信 15129739599 鹏仔QQ344225443 鹏仔前端 pjxi.com 共享博客 sharedbk.com