近似算法

一万年没更新博客了……毕竟我这么弱。
来玩一玩模拟退火算法和遗传算法。

我们的问题是,给定一个乱七八糟的函数,求它在某个区域内的最大值。

模拟退火算法

爬山

爬山算法是纯粹的贪心算法。给定一个起始点,我们能爬到一个极大值。

while(1)
{
    if(f(x+0.001) - f(x-0.001) > eps)  x+=0.001;         
    //如果向右走有利,则向右走
    else if(f(x+0.001) - f(x-0.001) < -eps) x+=0.001;
    //如果向左走有利,则向左走

    else goto finish;       //已经爬到极大值
}

爬山的缺陷在于,它会陷入局部最优解,而难以爬到全局最优解。例如下图。 爬山

我们把上面的x+0.001之类的操作称作“移动”。

经典模拟退火

模拟退火的思想在于,如果一个移动会使答案变得更优,我们就接受这个移动;否则我们以一定的概率接受这个移动。

听起来很玄学。根据物理的那套理论,我们定义两个东西:
- 温度$(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;               //降温
}

遗传算法

不妨假设有一大群兔子,它们均匀地分布在各种地方。
由于一些黑恶势力的影响,每年只有位置最高的那100只兔子能活下来。

位置最高的那些兔子们繁衍生息,它们的后代有些比它们站得高,于是这些后代活了下来;其他后代被黑恶势力搞死了。每年都只有站得最高的100只兔子能活下来。

在无尽的岁月后,这100只兔子想必都站在了世界上最高的山峰。

这个算法听起来比模拟退火靠谱。现在它的实现过程如下:

  1. 先随机产生100个点,均匀地分布在所求区间上。
  2. 取每两个点的中位数,这样我们共获得了10000个点。
  3. 取出最高的100个点,然后开始新一轮迭代。

但是这会引发一个问题。例如下图:

问题

这样的话,无论我们迭代多少次,总是找不到最高点(因为是取中位数)。这搞屁。

所以我们引入变异。每个数都有二进制表示,我们产生一个数之后,对它进行变异操作:二进制的每一位都以$p$的概率翻转。

这样的话,由于变异的存在,迭代若干次之后,最高点是找得到的。

那么问题来了。$p$到底取多少?

恭喜您打开了黑暗世界的大门——玄学调参数。由于我们很难给出一个很妙的$p$,遗传算法变得比模拟退火还不靠谱。

如何玄学调参数呢?我们造一些区间比较小的数据,暴力求出答案,然后根据这些数据来调整$p$。猜很多个$p$的值,看哪个最好。我们只需要考虑$p<0.5$的情况,因为以p的概率翻转,和以p的概率不翻转是本质相同的。


CC0协议 @ ruanxingzhi 2017. CC0是啥玩意?
Home apps close