随机化算法・模拟退火

作为曾经立志骗分过样例、暴力出奇迹的我，把在学习中的一点小小理解与感悟放上来

当不加约束的随机有了收敛，她总会在连续之中逼近我的极限。 —— 沃·兹吉硕德

爬山算法

爬山算法其实这是一个纯粹的贪心算法。

由某一个地点出发，一直往高(或低)处爬，直到最高点(或最低点)，于是就得到了最大值(或最小值)。

图解

让我放点图来解释下

大王叫小明去巡山，他从山脚开始爬。

小明上看下看左看右看，发现了右边的海拔更高，然后他开始爬了。
alt="爬">

小明爬啊爬，终于爬到了山顶A 。不过他近视了，远处更高的山顶B 没看见，然后小明就停止了爬山。

不错，爬山算法的缺陷就在于，它是近视短视的，无法看见远处更高的山峰。于是陷入了局部最优解，而想爬到全局最优解的话，就看你人品了。

伪代码

epsBig = 0.01;

while(1){
    if(f(x + epsBig) - f(x-epsBig) > eps)
        x += epsBig;         
    //如果向右走有利，则向右走
    else 
    if(f(x+epsBig) - f(x-epsBig) < -eps)
        x += epsBig;
    //如果向左走有利，则向左走
    else goto finish;
    //已经爬到极大值
}

本篇文章将$$x + epsBig$$称呼为移动。

模拟退火

模拟退火的思想就在于——

如果一个移动是对最优值有贡献的，那就一定接受移动。

如果一个移动是对最优值没有贡献的，那就以一定的概率接受移动。

图解

让我放点图来解释下

小明他今天作业做不完了，就借酒消愁，喝醉了就爬起山来了。毕竟是喝醉了，他有可能在去山顶的路上，也有可能在下山的过程中。

就这么瞎蹦乱跳着，小明竟然来到了最高的山顶。

不错，喝醉的小明和正常的小明其实就是爬山算法和模拟退火算法的区别。

如果坚决不接受一个更差的解，那么就会卡在上面的“当前位置”上了。倘若接受多几次更差的解，让小明移动到山谷那里，则可以突破局部最优解，从而在一定机率内得到全局最优解。

爬山算法不允许出现移动后的解比原来不优的情况，而模拟退火算法允许在一定的概率内出现移动后的解比原来状态不优的情况。

也正是这种随机，使得搜索从一叶障目的状态中跳出，依你人品，找到真正是全局最优的解。

数学描述

模拟退火算法来源于固体退火原理，是一种基于概率的算法，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。

听起来很玄学。根据物理的那套理论，我们定义两个东西：

• 温度$$(T)$$——它随着时间推移而逐渐降低。
• 增量$$(E)$$——它描述一次移动获得的好处。从$$x$$移动到$$x'$$的增量定义为$$f(x')-f(x)$$，增量越大，往$$x'$$移动的优势越大。

在模拟退火中，如果增量大于$$0$$，则直接接受这次移动；否则按下面的概率接受移动：

$$P = \exp(\frac{E}{T})$$

听起来十分的玄学啊。

伪代码

T = 100.0;                      //初始温度

for(int i = 0; i < 100; i++) {//控制迭代次数
    tar = getPos();             //在x的周围选一个点
    E = f(tar) - f(x);

    if(E > eps)                  //最优解
        x = tar;                //直接移动
    else
    if(exp(E/T) > random(0,1))   //看概率
        x = tar;                //接受移动

    T = T * 0.99;               //降温
}

CC0 协议

本篇文章采用CC0 协议，即放弃版权

在CC0协议的许可下，您可以以任何方式使用文档（包括商业用途），无需取得作者的同意，也无需标注来源。

To the extent possible under law,
ASC_8384
has waived all copyright and related or neighboring rights to
随机化算法・模拟退火.
This work is published from:
中国大陆.