模拟退火算法

Q1：模拟退火是什么算法？

        模拟退火是模拟物理上退火方法，通过N次迭代(退火)，逼近函数的上的一个最值（最大或者最小值)。
        比如逼近这个函数的最大值C点：

 

Q2：模拟退火为什么可行？

        讨论这个问题需要理解一下物理原型是怎么样的，也就是原来是怎么“退火"的：
        模拟退火算法的思想借鉴于固体的退火原理，当固体的温度很高的时候，内能比较大，固体的内部粒子处于快速无序运动，当温度慢慢降低的过程中，固体的内能减小，粒子的慢慢趋于有序，最终，当固体处于常温时，内能达到最小，此时，粒子最为稳定。

注意标粗字体:
        1.温度高->运动速度快（温度低->运动速度慢)

        2.温度是缓慢（想象成特别慢的那种）降低的
        3.温度基本不再变化后，趋于有序(最后内能达到最小，也就是接近最优)

我们通过模拟这个操作，使得我们需要的答案"趋于有序”，也就是最靠近需要的值(最值)。

Q3：怎么做？ 

大方向：

模拟退火就是一种循环算法。
        1.我们先设定一个初始的温度T(这个温度会比较高，比如2000)；

        2.每次循环都退火一次。(具体怎么操作后面详解)；
        3.然后降低T的温度，我们通过让T和一个"降温系数“ΔT(一个接近1的小数，比如0.99)相乘，达到慢慢降低温度的效果，直到接近于0(我们用eps来代表一个接近0的数(比如0.00001)，只要T

所以总的来说，用伪代码表示退火的流程是这样的：

double T=2000;//代表开始的温度
double dT=0.99;//代表系数delTa
doubel eps=1e-14;
while(T
    //-----------------
    //这里是一堆退货操作
    //-----------------
    T=T*dT;//每次温度下降一点点
}

退火详解：

我们要求解的答案无非是两个：自变量x和对应函数的最大值f(x).       

那么模拟退火的是怎么做到的呢?【下面车速很快，请系好安全带！】

1.我们先随机找一点x0，不论是哪个点都可以，随机！(不超过定义域就行)。这个点作为我们的初始值（相当于物体里的一个粒子)； 

2.再找到一点f(x0),来代表x0对应的函数值；

3.现在正式开始退火：

        刚才我们说了zo相当于是一个粒子，所以我们会进行一个无序运动，也就是向左或者向右随机移动，是的，是随机移动，可能向左，也可能向右，但是请记住一个关键点：移动的幅度和当前的温度T有关。温度T越大，移动的幅度越大。温度T越小，移动的幅度就越小。这是在模拟粒子无序运动的状态。

4.接受(Accept)更“好”的状态：

        假设我们移动到了x1处，那么这个点对应的f(x1)很明显答案是优于(大于)当前的f(x0)的，因此我们将答案进行更新。也就是将初始值进行替换x0= x1，f(x0)= f(x1)。这是一种贪心的思想。

5.以一定概率接受(Accept)更差的状态——>这是退火最精彩的部分：
        为什么我们要接受一个更加差的状态呢?因为可能在一个较差的状态旁边会出现一个更加高的山峰。

        那么我们以多少的概率去接受它呢？我们用一个公式表示(这个公式我们只需记住，这是科学家推导出来的结论)︰

                                        

C++伪代码如下：

double T=2000;//代表开始的温度
double dT=0.99;//代表系数delTa
doubel eps=1e-14;
 
//用自变量计算函数值,这里可能存在多个自变量对应一个函数值的情况，比如f(x, y)
double func(int x,...){
    //这里是对函数值进行计算
    double ans=......
    return ans;
}
 
//原始值
double x=rand();
double f=func(x,...);//通过自变量计算出f(x0)的值
 
while(True){
    //-----------------------------------------
    //这里是一次退火的操作
    
 
    //x1可以左右随机移动，幅度和温度T有关，所以*T
    //注意这里移动可以左右移动，但是也可以单向移动
    
    double dx=(2*rand()-RAND_MAX)*T;
    
    //让x落在定义域内，如果没在里面，就重新随机。题目有要求就写，否则不写
    //======================================
    while(x>? || x
        double dx=(2*rand()-RAND_MAX)*T;
    }
    
    //======================================
    
    //求出f(x1)的值
    double df=func(dx);
 
    //这里需要具体问题具体分析，我们要接受更加优秀的情况。可能是df < f(比如求最小值)
    if(f
        f=df;x=dx;[...,y=dy;]//接受，替换值，如果多个自变量，那么都替换掉
    }
    //否则概率接受，注意这里的df-f也有具体问题具体分析
    else if(exp((df-f)/T)*RAND_MAX>rand()){
        f=df;x=dx;[...,y=dy;]//接受，替换值，如果多个自变量，那么都替换掉
    }
    //-----------------------------------------
 
    T=T*dT;//温度每次下降一点点，dT=0.99
    
}
//最后输出靠近最优的自变量x的值和函数值f(x)
cout<" "<<f(x)<