Video在线视频

接下来我们讲第二种局部搜素算法，叫做模拟退
火搜索

那么模拟退火搜索的话就是从统计物理学里得来
的思想

那么也就是说为什么叫做退火呢

就是说它算法里面有一个叫温度的变量，这个温
度是慢慢降低的

那么这个温度是用来控制什么的呢

它是用来控制向不好的状态移动的一个概率

那么为什么要向不好的状态移动呢

因为我们看到爬山搜索它有一个毛病是很容易陷
于局部最值点

原因就是它任何时候只允许自己往上走，不允许
自己往下走

也就是说任何时候它发现自己怎么走都是往下走

它就不走了，就把这个局部最值点返回去了

那么如果你能够允许它向不好的状态移动

允许下山，有可能下山走到另外一个地方

会通向一个更高的山峰

所以模拟退火搜索通过允许向不好的地方移动来
避开局部最值点

但是这种向不好的状态移动的概率（频率）要由
温度来控制

也就是说这个频率要不断地降低不能老是允许它
向不好的状态移动

那么这个是模拟退火搜索的思想

那么我们来看到模拟退火搜索的伪代码

这个伪代码呢，那么大家看到这个就是模拟退火
搜索的英文单词

那么它的输入有一个就是问题的形式化

还有一个就是这个schedule

schedule就是一个时间到温度的对应表

也就是说所用来控制温度变化的一个表

那么它返回的是一个状态，一个解

这个解是一个状态

那么它也没有说这个解是局部最值点还是全局最
值点

它就是返回一个解状态给你

那么我们来看一下，它的输入是问题的形式化

然后还有一个schedule，schedule就是调度表

也就是说它存储的是什么时间对应什么温度的表

也就是说它把时间映射成温度

当我们这里的时间是用迭代来控制的

也就是说迭代第一次搜索的温度应该是多少

第二次温度应该是多少，所以是这种意义上的
schedule表

那么它还有三个局部变量，第一个局部变量就是
像前面一样的current

current这个变量就是用来储存当前结点

然后还有一个next，next和前面neighbor类似也是
用来储存下一个邻居结点

也就是说考虑要不要往前走的这么一个结点

然后还有第三个变量是一个温度变量

这个温度变量是用来控制向不好的状态移动的概
率

那么我们来看一下首先是根据问题形式化的初始
状态产生一个初始结点

放到当前结点里面，也就是说从初始结点出发

所以当前结点就是初始结点

然后开始了迭代开始了循环

那我们迭代呢就是把它定义成时间

也就是说第一次迭代我们可以看成时间是等于1的

然后for循环并没有控制迭代的次数

那么里面会有出口

那我们来看一下，首先根据时间（迭代的次数）

去schedule里面找到对应的温度，把这个温度拿
出来

那么如果发现这个温度等于零这个算法就结束了

那么就把当前结点对应的状态返回去作为问题的
解

所以它是通过这个schedule来控制迭代的次数

也就是说它慢慢退火，当温度退到零的时候就结
束了

那么就返回一个状态给你

那么我们再看，否则的话就根据当前状态去产生
后续结点

也就是说根据当前结点产生后续结点

然后产生的后续结点里面它随机的选择一个

所以这个是和爬山搜索不一样的地方

爬山搜索是选择一个最好的结点

而这里是随机的选择

所以它这里通过随机性也是为了逃开局部最值点

不要那么贪婪，你反而更有可能找到一个全局最
值点

所以他随机的选择一个后续结点放到next里面

然后来判断它随机选择的后续结点的评估函数值

和我当前结点的评估函数值的差

这里也是一样的认为这个值越大越好

所以这个差是随机选择出来的后续结点的值减去
当前结点的值

这个差放到这个△E里去存储

那怎么如果△E大于零

那么就意味着随机选择出来的这个后续结点要比
当前结点更好

那么更好的话，我们当然就毫不犹豫的走向这个
更好的这个后续结点

所以它是毫不犹豫的让更好的结点存储到当前结
点里面

也就是说当前结点就变成了更好的这个后续结点

如果△E小于零或者小于等于零

那么我们就到else这条语句来了

也就是说小于等于零的意思就是

你随机选出来的后续结点并不比我当前结点好

也就是说可能更差，也就是说比我当前结点更差

怎么办呢？更差，那么我也允许你往更差（更不
好）的状态前进

但是给你一定的概率不是让你无条件的往更差的
结点走，而是控制你

所以使得这个整体的趋势还是向好的方向发展

但是又允许你偶尔往更差的地方走

目的是将来找到一个更好的点

所以往更差的后续结点走的概率是由温度来控制
的

然后大家看到这个温度是怎么控制它的呢

这个概率用的是一个指数函数是e的△E/t次方

所以大家看到如果温度越高这个概率是更大还是
更小呢

大家看到这个else进来的话意味着这个△E是小于
零的

那么小于零的话，这是一个小于零的指数

那么t越大分子是会更大的

也就是说因为△E是小于零的所以温度越大这整个
值是越大的

也就是说一开始的时候我们的温度是很高的

所以往更差的状态移动的概率是更大的

随着迭代的进行这个温度越来越低

这个概率就越来越小

也就是慢慢这个算法觉得自己搜索的差不多了

然后就不允许它往坏的状态前进

那么另外这个概率还有一个影响它的就是这个△E

那么△E的绝对值

也就是说如果它负的越大，这个△E是小于零的

就意味着这个后续结点比当前结点差很多

那么差很多的话这个概率也小 所以△E也用来控制

如果这个状态太差了，越差的状态概率越小

那么好一点的状态概率越大

所以这个是通过这两个来控制向不好的状态移动
的概率，是这么来控制的

那么这个是一次迭代

然后再接下来就往下走就不断地走下去

也就是说这一步要看概率

有的时候是执行的，有的时候是不执行的

所以这个是我们的模拟退火搜索的伪代码

所以他的思想也并不复杂

但是由于它引入了随机性，使得它找到全局最值
点的概率就很高了

那么模拟退火搜索有一个很好的性质就是

可以证明如果温度降低的足够慢

也就是我们的for循环执行的次数足够多

也就是说这个schedule表里有很多的表目才会到
达温度为零

那么也就是我们的温度降低的足够的慢

迭代的次数足够的多

那么这个模拟退火算法是能够于趋近于1的概率

找到最优解

当然是趋近于1的概率

那么这个是一个很好的优点

它可以用来解决很多实际的问题