模拟退火学习笔记

1.简介

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

简而言之，模拟退火是一种随机化算法，常用于信息学竞赛中骗取高分，但因为其为随机化算法，所以不是很稳定，少则10分，多则AC，这取决于你的RP了（doge）。 它与爬山算法最大的不同是，在寻找到一个局部最优解时，赋予了它一个跳出去的概率，也就有更大的机会能找到全局最优解。

2.原理

原理在这里就不过多说了，因为可能对于程序的编写没有多大的影响，下面直接给出百度百科的原理介绍：

模拟退火的原理也和金属退火的原理近似：将热力学的理论套用到统计学上，将搜寻空间内每一点想像成空气内的分子；分子的能量，就是它本身的动能；而搜寻空间内的每一点，也像空气分子一样带有“能量”，以表示该点对命题的合适程度。演算法先以搜寻空间内一个任意点作起始：每一步先选择一个“邻居”，然后再计算从现有位置到达“邻居”的概率。

 简单来说就是，随机生成一个新的解，然后将其与先前的最优解进行比较，若生成的新解更优，则更新最优解，否则以exp（-ΔT/T）的概率接受它，exp是计算以自然底数为底的指数的函数，而这里的接受并不是指将新解作为最优解，而是更新步骤。

3.过程

　　1）降温

　　　　模拟退火有三个重要的参数，分别为初温t、降温系数ΔT和终温Tk，这三个参数关系到你的程序结果的准确性，当然，如何选择恰当的参数需要你的经验和RP了。

　　　　其中，t 是一个比较大的数，ΔT 是一个略小于 11 的正数，Tk​ 是一个略大于 00 的正数。我们先设当前温度T为初温，然后每次降温时 T 乘上 ΔT，直到 T≤Tk​ 为止。

　　　　大致过程如下：

　　　　

　　　　可以看出，随着温度的降低，解逐渐稳定下来，并逐渐集中在最优解附近。

　　2）生成新解

　　　　生成新解的基本思想就是使用rand随机生成一个值，并带入对应的计算函数就可以得出一个新解了，而计算函数是根据对应题目来决定的，往往都不相同。

　　3）调参

　　　　这可能是模拟退火中最重要的一步了，一个好的参数可一让你AC你所作的题，而一个坏的参数，可能让你的分数比暴力还低，一般来讲，如果答案不是最优，有以下几种调法：调大ΔT，调整t和Tk或多跑即便退火，如果太非的话，这边还是建议您直接打正解吧（

　　4）调整

　　　　如果新解更优，接受这个解。否则我们以一定概率接受这个解。设 ΔW 为新解和当前解的差（ΔW>0）。我们希望的是：T 越大时概率越大，ΔW 越小时概率越小。我们选择 e^{-\frac{\Delta W}{rT}}e−rTΔW​ 作为概率，这里的 r 是一个随机数。当然，如　　　　　　　　       果  ΔW 很大或很小的话这样子就可能会出问题。我们可以通过合理选择 r 的范围来解决问题。

　　5）其他

　　　　模拟退火中，还有一件重要的事就是选好随机数种子，和调参一样，种子选好了收益整个比赛，种子太臭，像11451419就会出事，下面是我的惨痛教训

　　　　

 

　　　　

　　　　程序开始时，我们要先srand(一个常数)。这个常数可以决定分数。你可以使用 233333，2147483647，甚至某个八位质数。

　　　　可以用一个全局变量记录所有跑过的模拟退火的最优解，每次从那个最优解开始继续模拟退火，可以减小误差。

4.实际应用

　　这里以洛谷1337 [JSOI2004]平衡点 / 吊打XXX为例，讲解模拟退火的实际应用。

　　题目要使整个系统的能量最小。那么我们只要用模拟退火跑出这个最小值即可。

　　代码如下：

#include <bits/stdc++.h>
#define re register 
using namespace std;
inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}
int n,sx,sy;
double ansx,ansy; //全局最优解坐标 
double ans = 1e18,t; //全局最优解，温度t
const double delta = 0.9913;
struct node{
    int x,y,w;
}a[1010];
inline double calc_energy(double x,double y){
    double rt=0;
    for (re int i=1;i<=n;i++) {
        double deltax=x-a[i].x,deltay=y-a[i].y;
        rt+=sqrt(deltax*deltax+deltay*deltay)*a[i].w;
    }
    return rt;
}
inline void simulate_anneal(){
    double x = ansx,y = ansy;
    t = 2000; //设初温
    while (t>1e-14){
        double X = x+((rand()<<1)-RAND_MAX)*t;
        double Y = y+((rand()<<1)-RAND_MAX)*t;
        double now = calc_energy(X,Y);
        double Delta = now-ans; //当前最优解与新解的差
        if (Delta<0){
            x = X;
            y = Y;
            ansx = x,ansy = y,ans = now;
        } 
        else if (exp(-Delta/t)*RAND_MAX>rand()){ //若不是当前最优，则有一定概率接受它 
            x = X;
            y = Y;
        }
        t*=delta;
    }
}
inline void Solve() { //多跑几遍模拟退火，减小误差
    ansx=(double)sx/n,ansy=(double)sy/n; //从平均值开始更容易接近最优解
    simulate_anneal();
    simulate_anneal();
    simulate_anneal();
}
int main(){
    srand(11451411919); srand(rand()); srand(rand());
    n = read();
    for (re int i=1;i<=n;i++){
        a[i].x = read(),a[i].y = read(),a[i].w = read();
        sx+=a[i].x,sy+=a[i].y;
    }
    Solve();
    printf("%.3f %.3f\n",ansx,ansy);
    return 0;
}

Over~

Tags:

VirMach 便宜 VPS

QNews

QNews