转自苍梧的博客：http://www.cnblogs.com/heaad/archive/2010/12/20/1911614.html  

一、模拟退火算法概念

关于爬山算法与模拟退火，有一个有趣的比喻，为了找出地球上最高的山，一群有志气的兔子们开始想办法：

方法一：兔子朝着比现在高的地方跳去。它找到了不远处的最高山峰。但是这座山不一定是珠穆朗玛峰。这就是爬山算法(或局部搜索法)，它不能保证局部最优值就是全局最优值。

方法二：兔子喝醉了，它随机地跳了很长时间。这期间，它可能走向高处，也可能踏入平地。但是，它渐渐清醒了并朝最高点跳去。这就是模拟退火。

爬山算法是一种简单的贪心搜索算法，它每次都鼠目寸光地从当前解临近的解空间中选择一个最优解作为当前解，直到得到一个局部最优解。如图1所示：假设C点为当前解，爬山算法搜索到A点这个局部最优解后就会停止搜索，因为在A点无论向那个方向小幅度移动都不能得到更优的解。因此，爬山算法只能搜索到局部最优值，而不一定能搜索到全局最优解。

图 1 示意图

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

模拟退火算法其实也是一种贪心算法，但是它的搜索过程引入了随机因素。模拟退火算法以一定的概率来接受一个比当前解要差的解，因此有可能会跳出这个局部的最优解，达到全局的最优解。以图1为例，模拟退火算法在搜索到局部最优解A后，会以一定的概率接受到E的移动。也许经过几次这样的不是局部最优的移动后会到达D点，于是就跳出了局部最大值A。模拟退火算法是一种随机算法，并不一定能找到全局的最优解，但可以比较快的找到问题的近似最优解。

二、模拟退火算法的关键步骤

模拟退火算法的基本思想是：由初始解和控制参数初值开始，对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代，并逐步衰减控制参数值，算法终止时，当前解的值即为近似最优解，这便是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。

图2 模拟退火算法流程图

冷却参数表、新解产生器、Metropolis接受准则一起构成模拟退火算法的关键部分。

1) 冷却参数表初始化：

我们称调整模拟退火法的一系列重要参数为冷却进度表。退火过程由冷却进度表(Cooling Schedule)控制，具体包括6个参数：

①初始温度T。一般要求T的初始值要充分大，即一开始处于高温状态。

②温度的衰减因子。衰减函数用于控制温度的退火速度，一个常用的函数为：T(n + 1) = K*T(n)，其中K是一个非常接近于1的常数。

③搜索步长因子。

④每个T值的迭代次数L(马可夫链长度)。在衰减参数T的衰减函数已选定的前提下，L应选得在控制参数的每一取值上都能恢复准平衡。即每一次随机游走过程，要迭代多少次，才能趋于一个准平衡分布，即一个局部收敛解位置。

⑤初始解状态i。是算法迭代的起点

⑥结束条件S。有很多种终止条件的选择，各种不同的条件对算法的性能和解的质量有很大影响，本文只介绍一个常用的终止条件。即上一个最优解与最新的一个最优解的之差小于某个容差，即可停止此次马尔可夫链的迭代。

2) 对k=1，…，L做第3至第5步

3) 产生新解S′的新解产生器。

首先由一个新解产生函数从当前解产生一个位于解空间的新解。为了便于后续的计算和接受，减少算法耗时，通常选择由当前解经过简单地变换即可产生新解的方法。

4) Metropolis准则

判断新解是否被接受,判断的依据是一个接受准则，最常用的接受准则是Metropo1is准则，这也是模拟退火算法的精髓所在。根据Metropolis准则，系统从一个能量状态变化到另一个状态时，相应的能量从E1变化到E2，在温度T时趋于平衡的概率，其中E为温度T时的内能，dE为内能的变化量，k为Boltzmann常数，exp表示自然指数。用固体退火模拟组合优化问题，将内能E模拟为目标函数值f，温度T演化成控制参数t，即得到解组合优化问题的模拟退火算法，计算当前解与新解所对应的目标函数差：

(1) 若Δt′= f(X(i+1)) - f(X(i)) < 0 (即移动后得到更优解)，则总是接受该移动，将新解S′作为当前解S。

(2) 若Δt′= f(X(i+1)) - J(X(i)) > 0 (即移动后的解比当前解要差)，则以一定的概率接受移动，而且这个概率随着时间推移逐渐降低（逐渐降低才能趋向稳定）。

此公式表明：温度越高，出现一次能量差为dE的降温的概率就越大；温度越低，则出现降温的概率就越小。随着温度T的降低，P(dE)会逐渐降低。又由于-dE/kT < 0，所以P(dE)的函数取值范围是(0,1)。在无限高温时，系统立即均匀分布，接受所有提出的变换。T的衰减越小，T到达终点的时间越长；但可使马可夫链越小，到达准平衡分布的时间越短

5) 如果满足终止条件则输出当前解作为最优解，结束程序。

终止条件通常取为连续若干个新解都没有被接受时终止算法。当新解被确定接受时，用新解代替当前解，这只需将当前解中对应于产生新解时的变换部分予以实现，同时修正目标函数值即可。此时，当前解实现了一次迭代。可在此基础上开始下一轮试验。而当新解被判定为舍弃时，则在原当前解的基础上继续下一轮试验。

6) T逐渐减少，且T->0，然后转第2步。

补充：模拟退火算法与初始值无关，算法求得的解与初始解状态S(是算法迭代的起点)无关；模拟退火算法具有渐近收敛性，已在理论上被证明是一种以概率l 收敛于全局最优解的全局优化算法；模拟退火算法具有并行性。

三、模拟退火算法的代码实现

1) 伪代码：

while(T > T_min)

{

dE = f(Y(i+1)) - f(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; //降温退火

i++;

}

2) C#代码：

 详细代码见 Program.cs