本文主要内容：
1.金属退火的原理
金属退火是将金属加热到一定温度，保持足够时间，然后以适宜速度冷却(通常是缓慢冷却，有时是控制冷却)的一种金属热处理工艺。模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。处在低温状态时，固体中分子具有的内能很低，在原本的位置上做小范围的振动。若是将固体加热到一定温度，分子内能将会增加，热运动加剧，分子排列的无序度增加。此时再将温度缓缓降低，在每个温度都达到平衡态（即准静态过程），分子具有的能量逐渐降低，最终回归到有序排列的状态，分子内能也跟着降到最低。
2.模拟退火算法机制
模拟退火算法包含两个部分即Metropolis算法和退火过程，最早的思想是由N. Metropolis等人于1953年提出。1983年,S. Kirkpatrick等成功地将退火思想引入到组合优化领域。它是基于Monte-Carlo?迭代求解策略的一种随机寻优算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。
Metropolis算法就是如何在局部最优解的情况下让其跳出来，是退火的基础。1953年Metropolis提出重要性采样方法，即以概率来接受新状态，而不是使用完全确定的规则，称为Metropolis准则，计算量较低。
假设开始状态在A，随着迭代次数更新到B的局部最优解，这时发现更新到B时，能力比A要低，则说明接近最优解了，因此百分百转移，状态到达B后，发现下一步能量上升了，如果是梯度下降则是不允许继续向前的，而这里会以一定的概率跳出这个坑，这各概率和当前的状态、能量等都有关系，下面会详细说，如果B最终跳出来了到达C，又会继续以一定的概率跳出来，可能有人会迷惑会不会跳回之前的B呢？下面会解释，直到到达D后，就会稳定下来。所以说这个概率的设计是很重要的，下面从数学方面进行解释。
假设前一个状态为x（n），,系统根据某一指标（梯度下降，上节的能量），状态变为x(n+1), 系统的能量由E(n)变为E(n+1)，定义系统由变为
的接受概率P为:
从上式我们可以看到，如果能量减小了，那么这种转移就被接受（概率为1），如果能量增大了，就说明系统偏离全局最优值位置更远了，此时算法不会立刻将其抛弃，而是进行概率操作：首先在区间【0,1】产生一个均匀分布的随机数，如果P，则此种转移接受，否则拒绝转移，进入下一步，往复循环。其中P以能量的变化量和T进行决定概率P的大小，所以这个值是动态的。
3.模拟退火的流程
算法实质分两层循环，在任一温度水平下，随机扰动产生新解，并计算目标函数值的变化，决定是否被接受。由于算法初始温度比较高，这样，使E增大的新解在初始时也可能被接受，因而能跳出局部极小值，然后通过缓慢地降低温度，算法就最终可能收敛到全局最优解，具体流程为：
- 令T=To,表示开始退火的初始温度，随机产生一个初始解
,并计算对应的目标函数值
;
- 令T=kT,其中
k取值0到1之间，为温度下降速率,通常取0.95旁边； - 对当前解施加随机扰动，在其邻域内产生一个新解
，并计算对应的目标函数值
,计算
?
- 若
,接受新解作为当前解，否则按照概率判断是否接受新解；
- 在温度
T下，重复L次扰动和接受过程，即执行步骤3和4； - 判断温度是否达到终止温度水平，若是则终止算法，否则返回步骤
2.
流程图如下
4.模拟退火的应用
模拟退火算法作为一种通用的随机搜索算法，现已广泛用于VLSI设计、图像识别和神经网计算机的研究。模拟退火算法的应用如下：
模拟退火算法在VLSI设计中的应用
利用模拟退火算法进行VLSI(Very Large Scale Integration,超大规模集成电路)的最优设计，是目前模拟退火算法最成功的应用实例之一。用模拟退火算法几乎可以很好地完成所有优化的VLSI设计工作。如全局布线、布板、布局和逻辑最小化等等。
除了上述应用外，模拟退火算法还用于其它各种组合优化问题，如TSP和Knapsack问题等。大量的模拟实验表明，模拟退火算法在求解这些问题时能产生令人满意的近似最优解，而且所用的时间也不很长。
下面举一个SA解决TSP问题的例子：
%%%%%%%%%%%%%%%%%%%%模拟退火算法求解TSP%%%%%%%%%%
%%%%%%%%%%%%初始化%%%%%%%%%%%%%%%%%%%%%%%%%
clear all;
close all;
clc;
c = [1304 2313;3639 1315;4177 2244;3712 1399;3488 1535;3326 1556;
2788 1229;4196 1044;4312 790 ;4386 570 ;3007 1970;2562 1756;
2788 1491;2381 1676;1332 695; 3715 1678;3918 2179;4061 2370;
3780 2212;3676 2578;4029 2838;4263 2931;3429 1908;3507 2376;
3394 2643;3439 3201;2935 3240;3140 3550;2545 2357;2778 2826;
2370 2975];
n = size(c,1);
T = 100*n; %%初始温度
L = 100; %马尔可夫链长度
K = 0.99; %衰退参数
%%城市坐标结构体
city = struct([]);
for i = 1:n
city(i).x = c(i,1);
city(i).y = c(i,2);
end
l = 1;
len(l) = func3(city,n);
figure(1);
while T > 0.001
for i = 1:L
%%计算原路线总距离
len1 = func3(city,n);
%%产生随机扰动%%
%%随机置换两个不同的城市的坐标
p1 = floor(1+n*rand());
p2 = floor(1+n*rand());
while p1 == p2
p1 = floor(1+n*rand());
p2 = floor(1+n*rand());
end
tmp_city = city;
tmp = tmp_city(p1);
tmp_city(p1) = tmp_city(p2);
tmp_city(p2) = tmp;
%%计算新路线总距离
len2 = func3(tmp_city,n);
%%新老路线的差值，相当于能量
delta_e = len2 - len1;
%%M准则，依概率,,,
if delta_e < 0
city = tmp_city;
else
if exp(-delta_e/T) > rand()
city = tmp_city;
end
end
end
i = i+1;
len(i) = func3(city,n);
T = T * K;
for i = 1:n-1
plot([city(i).x,city(i+1).x],[city(i).y,city(i+1).y],'bo-');
hold on;
end
plot([city(n).x,city(1).x],[city(n).y,city(1).y],'ro-');
title(['优化最短距离：',num2str(len(1))]);
hold off;
pause(0.005);
end
figure(2);
plot(len)
xlabel('迭代次数')
ylabel('目标函数值')
title('适应度函数曲线')
%%计算路线总长度
function len = func3(city,n)
len = 0 ;
for i = 1:n-1
len = len + sqrt((city(i).x-city(i+1).x)^2+(city(i).y-city(i+1).y)^2);
end
len = len + sqrt((city(n).x-city(1).x)^2+(city(n).y-city(1).y)^2);
end
?
5.小结
总之，模拟退火算法是通过赋予搜索过程一种时变且最终趋于零的概率突跳性，从而可有效避免陷入局部极小并最终趋于全局最优的串行结构的优化算法。算法从某一较高初温出发，伴随温度参数的不断下降,结合一定的概率突跳特性在解空间中随机寻找目标函数的全局最优解，即在局部最优解能概率性地跳出并最终趋于全局最优。
?