模拟退火算法（模拟退火算法的简介）

本文目录

• 模拟退火算法的简介
• 退火算法的应用领域及示例
• 什么是退火算法
• 模拟退火算法里的温度代表什么
• 模拟退火法^[1，]
• 模拟退火算法每次的解为什么不一样
• 谁能给我举一个模拟退火算法MATLAB源代码的简单例子
• 模拟退火法（SA）和遗传算法(GA)的专业解释

模拟退火算法的简介

模拟退火算法(Simulated Annealing，SA)最早的思想是由N. Metropolis 等人于1953年提出。1983 年,S. Kirkpatrick 等成功地将退火思想引入到组合优化领域。它是基于Monte-Carlo迭代求解策略的一种随机寻优算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。模拟退火算法从某一较高初温出发，伴随温度参数的不断下降,结合概率突跳特性在解空间中随机寻找目标函数的全局最优解，即在局部最优解能概率性地跳出并最终趋于全局最优。模拟退火算法是一种通用的优化算法，理论上算法具有概率的全局优化性能,目前已在工程中得到了广泛应用，诸如VLSI、生产调度、控制工程、机器学习、神经网络、信号处理等领域。
模拟退火算法是通过赋予搜索过程一种时变且最终趋于零的概率突跳性，从而可有效避免陷入局部极小并最终趋于全局最优的串行结构的优化算法。

退火算法的应用领域及示例

作为模拟退火算法应用，讨论旅行商问题(Travelling Salesman Problem,简记为TSP)：设有n个城市，用数码1,…,n代表。城市i和城市j之间的距离为d(i,j) i,j=1,…,n．TSP问题是要找遍访每个域市恰好一次的一条回路，且其路径总长度为最短.。
求解TSP的模拟退火算法模型可描述如下：
解空间 解空间S是遍访每个城市恰好一次的所有回路，是{1,……,n}的所有循环排列的集合,S中的成员记为(w1,w2,……,wn)，并记wn+1= w1。初始解可选为(1,……,n)
目标函数 此时的目标函数即为访问所有城市的路径总长度或称为代价函数：
我们要求此代价函数的最小值。
新解的产生 随机产生1和n之间的两相异数k和m,
若k《m,则将
(w1,w2,…,wk,wk+1,…,wm,…,wn)
变为：
(w1,w2,…,wm,wm-1,…,wk+1,wk,…,wn).
如果是k》m,则将
(w1,w2,…,wm,wm+1,…,wk,…,wn)
变为：
(wm,wm-1,…,w1,wm+1,…,wk-1,wn,wn-1,…,wk).
上述变换方法可简单说成是“逆转中间或者逆转两端”。
也可以采用其他的变换方法，有些变换有独特的优越性，有时也将它们交替使用，得到一种更好方法。
代价函数差 设将(w1,w2,……,wn)变换为(u1,u2,……,un)，则代价函数差为：
根据上述分析，可写出用模拟退火算法求解TSP问题的伪程序：
Procedure TSPSA:
begin
init-of-T; { T为初始温度}
S={1,……,n}; {S为初始值}
termination=false;
while termination=false
begin
for i=1 to L do
begin
generate(S′form S); { 从当前回路S产生新回路S′}
Δt:=f(S′））-f(S);{f(S)为路径总长}
IF（Δt《0) OR (EXP(-Δt/T)》Random-of-[0,1])
S=S′；
IF the-halt-condition-is-TRUE THEN
termination=true;
End;
T_lower;
End;
End
模拟退火算法的应用很广泛，可以较高的效率求解最大截问题(Max Cut Problem)、0-1背包问题(Zero One Knapsack Problem)、图着色问题(Graph Colouring Problem)、调度问题(Scheduling Problem)等等。 模拟退火算法的应用很广泛，可以求解NP完全问题，但其参数难以控制，其主要问题有以下三点：
⑴ 温度T的初始值设置问题。
温度T的初始值设置是影响模拟退火算法全局搜索性能的重要因素之一、初始温度高，则搜索到全局最优解的可能性大，但因此要花费大量的计算时间；反之，则可节约计算时间，但全局搜索性能可能受到影响。实际应用过程中，初始温度一般需要依据实验结果进行若干次调整。
⑵ 退火速度问题。
模拟退火算法的全局搜索性能也与退火速度密切相关。一般来说，同一温度下的“充分”搜索（退火）是相当必要的，但这需要计算时间。实际应用中，要针对具体问题的性质和特征设置合理的退火平衡条件。
⑶ 温度管理问题。
温度管理问题也是模拟退火算法难以处理的问题之一。实际应用中，由于必须考虑计算复杂度的切实可行性等问题，常采用如下所示的降温方式：
T(t+1)=k×T(t)
式中k为正的略小于1.00的常数,t为降温的次数 优点：计算过程简单，通用，鲁棒性强，适用于并行处理，可用于求解复杂的非线性优化问题。
缺点：收敛速度慢，执行时间长，算法性能与初始值有关及参数敏感等缺点。
经典模拟退火算法的缺点：
⑴如果降温过程足够缓慢，多得到的解的性能会比较好，但与此相对的是收敛速度太慢；
⑵如果降温过程过快，很可能得不到全局最优解。
􀂄 模拟退火算法的改进
⑴ 设计合适的状态产生函数，使其根据搜索进程的需要
表现出状态的全空间分散性或局部区域性。
⑵ 设计高效的退火策略。
⑶ 避免状态的迂回搜索。
⑷ 采用并行搜索结构。
⑸ 为避免陷入局部极小，改进对温度的控制方式
⑹ 选择合适的初始状态。
⑺ 设计合适的算法终止准则。
也可通过增加某些环节而实现对模拟退火算法的改进。
主要的改进方式包括：
⑴ 增加升温或重升温过程。在算法进程的适当时机，将温度适当提高，从而可激活各状态的接受概率，以调整搜索进程中的当前状态，避免算法在局部极小解处停滞不前。
⑵ 增加记忆功能。为避免搜索过程中由于执行概率接受环节而遗失当前遇到的最优解，可通过增加存储环节，将一些在这之前好的态记忆下来。
⑶ 增加补充搜索过程。即在退火过程结束后，以搜索到的最优解为初始状态，再次执行模拟退火过程或局部性搜索。
⑷ 对每一当前状态，采用多次搜索策略，以概率接受区域内的最优状态，而非标准SA的单次比较方式。
⑸ 结合其他搜索机制的算法，如遗传算法、混沌搜索等。
⑹上述各方法的综合应用。

什么是退火算法

模拟退火的基本思想:
　　(1) 初始化：初始温度T(充分大)，初始解状态S(是算法迭代的起点)， 每个T值的迭代次数L
　　(2) 对k=1，……，L做第(3)至第6步：
　　(3) 产生新解S′
　　(4) 计算增量Δt′=C(S′)-C(S)，其中C(S)为评价函数
　　(5) 若Δt′《0则接受S′作为新的当前解，否则以概率exp(-Δt′/T)接受S′作为新的当前解.
　　(6) 如果满足终止条件则输出当前解作为最优解，结束程序。
　　终止条件通常取为连续若干个新解都没有被接受时终止算法。
　　(7) T逐渐减少，且T-》0，然后转第2步。

模拟退火算法里的温度代表什么

模拟退火是一种优化算法，它本身是不能独立存在的，需要有一个应用场合，其中温度就是模拟退火需要优化的参数，如果它应用到了聚类分析中，那么就是说聚类分析中有某个或者某几个参数需要优化，而这个参数，或者参数集就是温度所代表的。它可以是某项指标，某项关联度，某个距离等等

模拟退火法^[1，]

模拟退火算法最早在1953年由 Metropolis等人提出。在地球物理中的最早应用是Rothman在1983年利用模拟退火算法处理地震资料的剩余静校正。模拟退火法也是类似于蒙特卡洛法的随机搜索方法。但是在产生模型的过程中引入一些规则，能有效地加快搜索速度，有时又称这类方法为启发式蒙特卡洛法。

模拟退火法概念源于统计物理学，是模拟固体熔化状态逐渐缓慢冷却最终达到能量最小的结晶状态的物理过程。对于一个熔化的金属，当处于某个温度的热平衡状态时，它的每一个分子都有它可能所处的状态，有些分子可能能量高一些，有些分子可能能量低一些，分子处于何种状态的概率由分子所具有的能量决定。设分子所有可能的能级总数为n(微观粒子的能量都是量子化的，不连续的)，则分子处于某种状态的概率满足玻尔兹曼概率分布:

地球物理反演教程

其中:Ei为第i个分子的能量;K为玻尔兹曼常数;T为绝对温度;n为分子所有可能的能级总数，分母称为配分因子;p_i为第i个分子处于能量E_i的概率。

如果把地球物理反演的模型向量看作分子，把目标函数看作分子的能量，把目标函数的极小值看成分子冷却结晶的最小能量，反演问题(最优化问题)可以模拟式(8.11)金属退火的过程，通过缓慢地减小温度进行反演，使目标函数(能量)逐渐达到极小值，这时所对应的模型(分子状态)就是反演结果。

为了改善于蒙特卡洛法的随机搜索方法，1953年 Metropolis等人在产生模型的过程中引入Metropolis接受准则，模型产生并不是完全随机，而是以前一个模型为基础随机产生。对能量减小的模型完全接受，对能量增加的模型按一定的概率接受，这样能有效地加快搜索速度，同时又有可能跳出局部极小值。具体如下:

设原来模型向量为m_i，新的模型为m_i+1(在m_i基础上随机修改产生)，各自的能量(目标函数)为E(m_i)和E(m_i+1)。如果E(m_i+1)＜E(m_i)，则目标函数在减小，新模型可以接受。如果E(m_i+1)＞E(m_i)，则目标函数在增加，按照一定概率来确定是否接受新的模型。具体规则见式(8.12):

E(m_i+1)＜E(m_i) 完全接受m_i+1为新模型

地球物理反演教程

式(8.12)就是Metropolis接受准则。它使得反演过程可以接受使目标函数增加的模型，因此也就使得模拟退火法有可能跳出局部极小，收敛于全局极小值点。由于玻尔兹曼常数K只是起到尺度因子的作用，在实际计算中K可取为1来简化公式。从式(8.12)可以看出，当温度较低时，p_i+1/p_i较小，因此接受使能量增加的新模型的可能性较小。而一般温度较低时，目标函数较小，模型比较靠近真实模型，这时基本上只接受使目标函数减小的模型，使模型尽快收敛于极小值点。

在模拟退火反演中，要求温度T随着迭代次数的增加而缓慢降温。常用的温度函数有两种。

(1)指数下降型:

T_k=T₀·exp(-ck1/N) (8.13)

式中:k为迭代次数;c为衰减因子;N为模型参数的个数;T₀为初始温度。上式也可以改写为

地球物理反演教程

通常选择0.7≤α≤1。在实际应用中可采用0.5或1代替式(8.14)的1/N。图8.4(a)为指数降温曲线。采用参数为:T₀=200℃，α=0.99，1/N=0.9。

(2)双曲线下降型:

T=T₀αk (8.15)

式中:T₀为初始温度;k为迭代次数;α为衰减因子，通常取0.99。初始温度T₀不能取得太高，否则增加计算时间浪费机时;T₀也不能太低，否则模型选取不能遍及整个模型空间，只是在初始模型附近选取，不能进行全局寻优。所以T₀的确定只有通过实验计算得到。图8.4(b)为双曲线降温曲线。采用参数为:T₀=200℃，α=0.99。从图8.4可以看出通过对不同温度曲线和相关参数进行选择，可以控制温度下降的方式和速度。

图8.4 模拟退火法降温曲线

模拟退火法主要有三种:

(1)MSA算法(Metropolis Simulated Annealing);

(2)HBSA算法(Heat Bath Simulated Annealing);

(3)VFSA算法(Very Fast Simulated Annealing)。

图8.5 模拟退火MSA算法程序流程图

前面介绍的利用 Metropolis接受准则的算法就是经典的模拟退火法。图8.5为模拟退火 MSA算法的程序流程图。从中可以看出 MSA算法有一套模型修改准则，依次改变模型参数，每次改变都是在原来模型基础上改变一个参数，因此容易保持已有搜索成果，持续不断地向目标函数最小值点接近，因此搜索效率比蒙特卡洛法高。此外，MSA算法允许接受使目标函数增加的模型，这样又易于跳出局部极小，达到全局极小。但 MSA算法在任何温度下和蒙特卡洛法一样都是在模型全空间进行搜索，不能根据当前温度和模型减小搜索空间，此外由于模型的修改全凭运气，所以不可能像前面介绍的最小二乘法那样目标函数基本上持续减小，而是呈不规则振荡在宏观上逐渐减小，因此效率较低。

HBSA算法与 MSA算法的不同之处是在模型的修改上。也是首先随机选择一个初始M维模型向量m₀(它具有M个参数);然后限制各个模型参数可能的取值范围，对取值离散化。假设每个模型参数都有N个可能的值，首先固定模型第2个参数m₀(2)直到第M个参数m₀(M)保持不变，只修改第1个参数m₀(1);计算m₀(1)的所有取值时的目标函数，然后按式(8.16)计算“概率”，它就是式(8.11)配分因子取1的公式。即

地球物理反演教程

选择“概率”最大的为模型第1个参数的修改值。照此依次对所有模型参数进行修改完成依次迭代计算。在每次迭代计算中保持温度不变。随着迭代次数增加，温度降低，最终达到稳定状态，获得最小能量解。这种方法的计算由于要计算某个参数的所有可能值，所以计算量也是很大的。

1989年Ingber提出了VFSA算法，由于速度较快，最为常用。它使得模拟退火法从理论走向了实际应用。VFSA算法在流程上与传统的模拟退火法相同，但是在模型修改、接受概率以及降温曲线上有所改进。

(1)模型修改:常规模拟退火法采用高斯随机分布修改模型，在任何温度下都是在模型全空间进行搜索。而Ingber提出采用依赖于温度的似cauchy分布产生新的模型。即

地球物理反演教程

y_i=Tsgn(u-0.5)[(1+1/T|2u-1|-1]　　(8.18)

其中:m_i为当前模型第i个参数，m’_i为修改后的模型参数;u为[0，1]的随机数;[A_i，B_i]为m_i和m’_i的取值范围;sgn( )为符号函数。

采用以上方式能在高温下进行大范围的搜索，低温时在当前模型附近搜索，而且由于似cauchy分布具有平坦的“尾巴”，使其易于迅速跳出局部极值。这一改进大大加快了模拟退火法的收敛速度。

(2)接收概率:当E(m_i+1)＞E(m_i)时，VFSA算法采用如下概率接受公式:

地球物理反演教程

上式当h→1时变为式(8.12)。h通过实验获得。

(3)降温曲线(退火计划):Ingber在1989年采用式(8.13)得出指数降温曲线。从图8.4可知，温度下降较快。

总之，VFSA算法在模型修改、接受概率以及降温曲线上的改进使得模拟退火算法收敛速度大大加快。后人在此基础上还有很多的改进，读者可以参考相关文献。

模拟退火法的优点:由于不需要计算偏导数矩阵，不需要解线性方程组(当然正演计算的除外)，结构简单，易于编程;此外，由于它搜索范围大，能接受较差模型，因此易于达到全局极小。缺点:随机搜索，计算量巨大，往往要计算成百上千次正演，这与前面的最小二乘法十几次的正演计算相比反演时间太长，因此一般应用在一维反演之中，在二维、三维等高维反演中应用较少。

模拟退火算法每次的解为什么不一样

模拟退火每次的解不同是很正常的，因为模拟退火本身是一种随机算法，转移向更差的解不是必然而是概率性的，也就是说每次执行算法时，执行过程转移到的解可能都是完全不一样的。

至于TSP问题，本身属于NP-hard问题，找不到存在多项式时间复杂度的解。

如果要求精确的解，目前可行的方法有枚举、分支限界、动态规划等，但这些方法适用的数据范围都很小，一旦数据规模变大，它们都将无能为力。

所以目前广泛使用的大都是一些随机算法，比如蚁群、遗传等，模拟退火就是其中的一种，这些算法的一大特点就是通过随机去逼近最优解，但也有可能得到错解。

只有穷举法可以保证得到最优解，但是穷举法在数据量比较大的时候运行时间通常是不能接受的，所以用了各种近似方法。

模拟退火算法新解的产生和接受可分为如下四个步骤：

第一步是由一个产生函数从当前解产生一个位于解空间的新解；为便于后续的计算和接受，减少算法耗时，通常选择由当前新解经过简单地变换即可产生新解的方法，如对构成新解的全部或部分元素进行置换、互换等，注意到产生新解的变换方法决定了当前新解的邻域结构，因而对冷却进度表的选取有一定的影响。

第二步是计算与新解所对应的目标函数差。因为目标函数差仅由变换部分产生，所以目标函数差的计算最好按增量计算。事实表明，对大多数应用而言，这是计算目标函数差的最快方法。

第三步是判断新解是否被接受,判断的依据是一个接受准则，最常用的接受准则是Metropolis准则: 若ΔT《0则接受S′作为新的当前解S，否则以概率exp(-ΔT/T)接受S′作为新的当前解S。

第四步是当新解被确定接受时，用新解代替当前解，这只需将当前解中对应于产生新解时的变换部分予以实现，同时修正目标函数值即可。此时，当前解实现了一次迭代。可在此基础上开始下一轮试验。而当新解被判定为舍弃时，则在原当前解的基础上继续下一轮试验。

谁能给我举一个模拟退火算法MATLAB源代码的简单例子

clear
clc
a = 0.95
k = [5;10;13;4;3;11;13;10;8;16;7;4];
k = -k; % 模拟退火算法是求解最小值，故取负数
d = [2;5;18;3;2;5;10;4;11;7;14;6];
restriction = 46;
num = 12;
sol_new = ones(1,num); % 生成初始解
E_current = inf;E_best = inf;
% E_current是当前解对应的目标函数值（即背包中物品总价值）；
% E_new是新解的目标函数值；
% E_best是最优解的
sol_current = sol_new; sol_best = sol_new;
t0=97; tf=3; t=t0;
p=1;

while t》=tf
for r=1:100
%产生随机扰动
tmp=ceil(rand.*num);
sol_new(1,tmp)=~sol_new(1,tmp);

%检查是否满足约束
while 1
q=(sol_new*d 《= restriction);
if ~q
p=~p; %实现交错着逆转头尾的第一个1
tmp=find(sol_new==1);
if p
sol_new(1,tmp)=0;
else
sol_new(1,tmp(end))=0;
end
else
break
end
end

% 计算背包中的物品价值
E_new=sol_new*k;
if E_new《E_current
E_current=E_new;
sol_current=sol_new;
if E_new《E_best
% 把冷却过程中最好的解保存下来
E_best=E_new;
sol_best=sol_new;
end
else
if rand《exp(-(E_new-E_current)./t)
E_current=E_new;
sol_current=sol_new;
else
sol_new=sol_current;
end
end
end
t=t.*a;
end

disp(’最优解为：’)
sol_best
disp(’物品总价值等于：’)
val=-E_best;
disp(val)
disp(’背包中物品重量是：’)
disp(sol_best * d)

模拟退火法（SA）和遗传算法(GA)的专业解释

模拟退火来自冶金学的专有名词退火,退火是将材料加热后再经特定速率冷却，目的是增大晶粒的体积，并且减少晶格中的缺陷。材料中的原子原来会停留在使内能有局部最小值的位置，加热使能量变大，原子会离开原来位置，而随机在其他位置中移动。退火冷却时速度较慢，使得原子有较多可能可以找到内能比原先更低的位置。 模拟退火的原理也和金属退火的原理近似：将热力学的理论套用到统计学上，将搜寻空间内每一点想像成空气内的分子；分子的能量，就是它本身的动能；而搜寻空间内的每一点，也像空气分子一样带有“能量”，以表示该点对命题的合适程度。演算法先以搜寻空间内一个任意点作起始：每一步先选择一个“邻居”，然后再计算从现有位置到达“邻居”的概率。

遗传算法（Genetic Algorithm）是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法。它是由美国的J.Holland教授1975年首先提出，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。