跳转至

模拟退火从精通到入土ψ(｀∇´)ψ

简介ψ(｀∇´)ψ

首先我们需要知道一种叫爬山算法的东西。

基本思路就是在当前的最优解附近找到一个新的解，如果新的解更优则转移，反之不变。

你发现这样子很容易陷入局部的最优解当中，并且只能解决单峰函数的情况。

所以我们为了解决更广泛的多峰函数的情况，需要引进模拟退火这个算法。

爬山算法在找到当前最优解的附近的一个非最优解的时候，会把它直接舍弃掉。

而模拟退火就是在随机化的一个概率下，先转移到这个非最优解以跳出局部最优找到可能的全局最优解的一个算法。

并且基于金属退火的原理，它如果跳出了全局最优解，在温度不断下降的时候，扰动的幅度越来越小，也是大概率会跳回来的。

一般我们会用于一些方案数极大的，或者是正常算法难以想到的题当中。

当然考场上不推荐使用，因为它毕竟是个随机化算法（除非你就没想过打正解）。

基本原理ψ(｀∇´)ψ

它基于一个工业上的热处理工艺——金属退火，也可以说基于热力学原理。

金属退火：将金属加热到一定温度，保持足够时间，然后以适宜速度冷却(通常是缓慢冷却，有时是控制冷却)的一种金属热处理工艺。

模拟退火的过程是在一个能量函数 \(F\) 上进行的，我们把它放到二维的坐标系下，就相当于一个自变量为系统变量，因变量是系统能量的一个函数。

我们要求的就是这个多峰（谷）函数 \(F\) 的最值。

系统变量可以是一个单独的变量 \(x\) ，也可以是题中给出的条件（比如 \(x,y\) 坐标）组成的一个多元组，在下文我们把这个多元组（或者单个变量）称作 \(X\)。

表示解的时候也依旧使用这个系统变量 \(X\)。

那么，模拟退火每次会在上一个被接受的解 \(X\) 的基础上随机生成一个新的解 \(X^\prime\)，

这个新的解和 \(X\) 以及当前解的系统能量 \(F(X)\) 有关。

如果 \(X^\prime\) 更优秀那么接受这个新最优解，记录全局答案。

反之以一个关于 \(F(X^\prime)\) 和温度 \(T\) 的概率接受这个非最优解 \(X^\prime\)，\(T\) 具体是什么下文会提到。

实现ψ(｀∇´)ψ

我们需要先定义几个变量以方便描述：

  • 当前温度 \(T\)。
  • 初始温度 \(T_0\) ，一般取一个较大的数，大概在 \([1000,5000]\) 范围内。
  • 最终温度 \(T_k\) ，一般取一个极小的正数，大概在 \([10^{-15},10^{-8}]\) 上。
  • 降温系数 \(\delta\) ，一般取一个在 \((0.985,0.997)\) 上的一个数，推荐 \(0.995\)。

计算系统能量ψ(｀∇´)ψ

写计算系统能量的函数就相当于写出 \(F(X)\) 的表达式。

我们需要根据题目所给的条件 \(X\) 计算出在解为 \(X\) 的时候的系统能量 \(F(X)\)。

举一个比较简单的例子，假设 \(X\) 就代表平面直角坐标系当中的 \(x\) 坐标。

\(F(X)\) 则是一个二次函数 \(y=Ax^2+Bx+C\) 。

那么你计算系统能量的函数 \(F(X)\) 就只需要返回 \(AX^2+BX+C\) 即可。

更多的实例会在下面的例题中提到。

降温ψ(｀∇´)ψ

最开始的时候令 \(T=T_0\)。

每次降温只需要给 \(T\) 乘上 \(\delta\) 即可（降温要在接受新解之后）。

直到 \(T \le T_k\) 的时候再停止降温并退出模拟退火的过程。

此处引用一张图（图源维基百科）：

sa.gif

你发现，随着温度的下降，解的扰动幅度也越来越小，最终接近于最优解。

这就好比分子永不停息的做无规则运动一样，而且温度越高运动的越快，幅度越大。

模拟退火实际上就是在模拟类似这个的过程。

生成一个新解ψ(｀∇´)ψ

每次，我们会在上一个被接受的解的基础上随机生成一个新的解。

一定要注意，此处使用的是上一个被接受的解而不是当前的全局最优解。

不然你就和爬山算法没有太大的差异了ovo。

之前有个朋友模拟赛的时候打了退火，本来可以拿到90pts，但是就是因为使用了全局最优解来生成下一个解而导致爆零。

（不过我寻思着，为啥在生成新解的时候会用去全局最优解啊？变量不都应该标识清楚了吗）

生成新解的方式很多，最常见的就是直接在系统变量当中包括的每一个变量的基础上加上一个随机数再搞一搞。

比如这样子：

1
2
    double nx=x+((rand()<<1)-RAND_MAX)*t;
    double ny=y+((rand()<<1)-RAND_MAX)*t;

也可以直接在定义域 \([l,r]\) 当中随机一个新解出来，不管上一个被接受的的解是什么：

1
    int nx=rand()%r+l;

一般要看题目的情况而定。

转移ψ(｀∇´)ψ

这个转移是模拟退火的精髓之一，它利用了 Metropolis 准则。

我们定义 \(\Delta E\) 表示当前新生成的解 \(X\) 的能量 \(F(X)\) 和目前的全局最优解的能量 \(F(X_0)\)的差。

也就是 \(\Delta E = F(X)-F(X_0)\) 。

考虑我们当前是在求能量函数的最小值。

那么，如果 \(\Delta E < 0\) ，我们直接接受这个新的解 \(X\)，因为它的能量更小。

反之，如果 \(\Delta E > 0\) ，证明这个解是个非最优解，我们就以 \(e^{\dfrac{\Delta E}{T}}\) 的概率接受这个非最优解。

代码大致如下：

1
2
3
4
5
    if(Delta<0){
        记录这个解被接受
        记录新的全局最优解
    }
    else if(exp(-Delta/T)*RAND_MAX>rand()) 记录这个解被接受

反过来，如果我们当前是在求能量函数的最大值的话，我们这么写即可：

1
2
3
4
5
    if(Delta>0){
        记录这个解被接受
        记录新的全局最优解
    }
    else if(exp(-Delta/T)*RAND_MAX<rand()) 记录这个解被接受

因为这个时候在 else if 当中， \(e^{\dfrac{\Delta E}{T}}\) 是 \(>1\) 的。

所以把大于号改成小于号即可。

其他ψ(｀∇´)ψ

在退火的时候，为了使答案更加接近我们要的解，一般会记录全局最优解而不是直接使用当前解。

而且在开始的时候可以直接从定义域当中的平均值开始退火。

并且，如果时间允许的话，可以在退火过程完成之后再跑一遍类似于模拟退火的过程，以求出更精确的解。

优化 & 调参ψ(｀∇´)ψ

一般一次退火是远远不够的，所以我们需要多跑几次退火。

你可以直接跑三到五次。

也可以直接卡时。

使用以下语句即可。

1
2
    while((double)clock()/CLOCK_PER_SEC<Limit) simulated_annealing();
    //limit一般比时间限制小一点，比如你时限 1s ，limit 一般取 998ms。

或者你也可以这样子：

1
2
3
4
5
6
7
int main(){
    double ti=clock();
    //...
    while(clock()-ti<Limit) simulated_annealing();
    //注意不要忽略大规模输出所花的时间！
    return 0;
}

还有，如果你交上去发现无法AC，那么就需要进入退火当中最痛苦的一个过程：调参。

一般来说，你需要调整 \(T_0,T_k\) ，然后把 \(\delta\) 调大。

这个东西是没有啥通法的，只能靠经验和感觉。

或者你也可以试一试更改随机数种子，比如改成 srand(114514),srand(20061231),srand(time(NULL)),srand(rand())。

个人推荐后两种。

例题ψ(｀∇´)ψ

咕咕咕

Referenceψ(｀∇´)ψ

最后更新: May 9, 2023