模拟退火算法

说模拟退火算法之前，先介绍爬山算法。爬山算法是优化算法的一种，它的思想是：对于复杂的问题，先给出一个随机的解s1，然后在这个解s1的“周围”搜索更好的解s2（周围指的是改变影响最终方案的其中一个因素的取值），如果发现更好的解s2，那么继续寻找s2周围有没有更好的解sx，直到周围没有更好的解了，那么sx就是这个问题的局部最优解。
算法的思想可以用下山的过程来描述：为了能尽快下山，我们在山顶的一个点，要环顾四周，找到坡度最大的一个方向走一步；然后在环顾四周，再找到一个坡度最大的方向走一步，直到发现周围没有坡度了，那就到达山脚下了。
如下图所示，很显然得到爬山算法得到的是局部最优解，而并非全局最优解。

爬上算法是完全的贪心法，每次都选择一个当前的最优解，因此只能搜索到局部的最优值。模拟退火算法也是一种贪心算法，但是它的搜索过程引入了随机因素。模拟退火算法以一定的概率来接受一个比当期要差的解，因此有可能会跳出这个局部的最优解，达到全局的最优解。用数学表达式表示就是：
若J(Y(i+1))>=J(Y(i))，表示移动后得到更优解，则总是接受该移动；
若J(Y(i+1))<J(Y(i))，表示移动后的解差于当前解，则以一定的概率接受移动，而且这个概率随着时间推移逐渐降低，这样才能趋向稳定。
这里的“一定的概率”的计算参考了金属冶炼的退火过程，这也是退火算法名称的由来。
根据热力学的原理，在温度为T时，出现能量差为dE的降温的概率为P(dE)，表示为：
P(dE)= exp(dE/(kT))
其中，k是一个常数，exp表示自然对数，且dE<0
这个公式说明：温度越高，出现一次能量差为dE的降温的概率就越大；温度越低，出现降温的概率就越小。又由于，dE总是小于0（退火能量差），因此dE/kT<0，所以P(dE)的函数的取值范围是0~1.随着温度的下降，P(dE)会逐渐降低。
我们将一次向较差解的移动看作一次温度跳变过程，我们以概率P(dE)来接受这样的移动。
具体来讲，我们在初始时给定一个温度函数，然后让这个温度函数随着时间慢慢降低。我们也从当前状态的子状态中随机抽取一个，如果这个子状态把我们引向更高处，则它取代当前状态，继续迭代；如果子状态是个下坡，有一定几率我们仍然用它取代当前状态。下坡越小，温度越高，几率越大。
模拟退火算法伪代码：

/** J(y)：在状态y时的评价函数值
* Y(i)：表示当前状态* Y(i+1)：表示新的状态
* r： 用于控制降温的快慢
* T： 系统的温度，系统初始应该要处于一个高温的状态
* T_min ：温度的下限，若温度T达到T_min，则停止搜索
*/
while( T > T_min )
{　　
    dE = J( Y(i+1) ) - J( Y(i) ) ; 
        if ( dE >=0 ) //表达移动后得到更优解，则总是接受移动
            Y(i+1) = Y(i) ; //接受从Y(i)到Y(i+1)的移动
        else　　
        {
            // 函数exp( dE/T )的取值范围是(0,1) ，dE/T越大，则exp( dE/T )也
            if ( exp( dE/T ) > random( 0 , 1 ) )
                Y(i+1) = Y(i) ; //接受从Y(i)到Y(i+1)的移动　　
         }　　
    T = r * T ; //降温退火 ，0<r<1 。r越大，降温越慢；r越小，降温越快　　
   /*　　
    * 若r过大，则搜索到全局最优解的可能会较高，但搜索的过程也就较长
    * 若r过小，则搜索的过程会很快，但最终可能会达到一个局部最优值　　
   */　　
    i ++ ;
}