退火算法应用

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

作为模拟退火算法应用，讨论旅行商问题(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问题的伪程序：
Procere 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)、调度问题(Scheling Problem)等等。 模拟退火算法的应用很广泛，可以求解NP完全问题，但其参数难以控制，其主要问题有以下三点：
⑴ 温度T的初始值设置问题。
温度T的初始值设置是影响模拟退火算法全局搜索性能的重要因素之一、初始温度高，则搜索到全局最优解的可能性大，但因此要花费大量的计算时间；反之，则可节约计算时间，但全局搜索性能可能受到影响。实际应用过程中，初始温度一般需要依据实验结果进行若干次调整。
⑵ 退火速度问题。
模拟退火算法的全局搜索性能也与退火速度密切相关。一般来说，同一温度下的“充分”搜索（退火）是相当必要的，但这需要计算时间。实际应用中，要针对具体问题的性质和特征设置合理的退火平衡条件。
⑶ 温度管理问题。
温度管理问题也是模拟退火算法难以处理的问题之一。实际应用中，由于必须考虑计算复杂度的切实可行性等问题，常采用如下所示的降温方式：
T(t+1)=k×T(t)
式中k为正的略小于1.00的常数,t为降温的次数 优点：计算过程简单，通用，鲁棒性强，适用于并行处理，可用于求解复杂的非线性优化问题。
缺点：收敛速度慢，执行时间长，算法性能与初始值有关及参数敏感等缺点。
经典模拟退火算法的缺点：
⑴如果降温过程足够缓慢，多得到的解的性能会比较好，但与此相对的是收敛速度太慢；
⑵如果降温过程过快，很可能得不到全局最优解。
􀂄 模拟退火算法的改进
⑴ 设计合适的状态产生函数，使其根据搜索进程的需要
表现出状态的全空间分散性或局部区域性。
⑵ 设计高效的退火策略。
⑶ 避免状态的迂回搜索。
⑷ 采用并行搜索结构。
⑸ 为避免陷入局部极小，改进对温度的控制方式
⑹ 选择合适的初始状态。
⑺ 设计合适的算法终止准则。
也可通过增加某些环节而实现对模拟退火算法的改进。
主要的改进方式包括：
⑴ 增加升温或重升温过程。在算法进程的适当时机，将温度适当提高，从而可激活各状态的接受概率，以调整搜索进程中的当前状态，避免算法在局部极小解处停滞不前。
⑵ 增加记忆功能。为避免搜索过程中由于执行概率接受环节而遗失当前遇到的最优解，可通过增加存储环节，将一些在这之前好的态记忆下来。
⑶ 增加补充搜索过程。即在退火过程结束后，以搜索到的最优解为初始状态，再次执行模拟退火过程或局部性搜索。
⑷ 对每一当前状态，采用多次搜索策略，以概率接受区域内的最优状态，而非标准SA的单次比较方式。
⑸ 结合其他搜索机制的算法，如遗传算法、混沌搜索等。
⑹上述各方法的综合应用。

㈡ 退火算法的定义

Simulate Anneal Arithmetic (SAA,模拟退火算法)
根据Metropolis准则，粒子在温度T时趋于平衡的概率为e-ΔE/(kT)，其中e为温度T时的内能，ΔE为其改变量,k为Boltzmann常数。用固体退火模拟组合优化问题，将内能E模拟为目标函数值f,温度T演化成控制参数t,即得到解组合优化问题的模拟退火算法：由初始解i和控制参数初值t开始，对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代，并逐步衰减t值，算法终止时的当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。退火过程由冷却进度表(Cooling Schele)控制，包括控制参数的初值t及其衰减因子Δt、每个t值时的迭代次数L和停止条件S。 模拟退火算法起源于物理退火。
􀂄物理退火过程：
⑴ 加温过程
⑵ 等温过程
⑶ 冷却过程 模拟退火算法可以分解为解空间、目标函数和初始解三部分。
模拟退火的基本思想：
⑴ 初始化：初始温度T（充分大），初始解状态S（是算法迭代的起点）， 每个T值的迭代次数L
⑵ 对k=1,……,L做第⑶至第6步：
⑶ 产生新解S′
⑷ 计算增量Δt′=C(S′）-C(S)，其中C(S)为评价函数
⑸ 若Δt′<0则接受S′作为新的当前解，否则以概率exp(-Δt′/T)接受S′作为新的当前解.
⑹ 如果满足终止条件则输出当前解作为最优解，结束程序。
终止条件通常取为连续若干个新解都没有被接受时终止算法。
⑺ T逐渐减少，且T->0,然后转第2步。 模拟退火算法新解的产生和接受可分为如下四个步骤：
第一步是由一个产生函数从当前解产生一个位于解空间的新解；为便于后续的计算和接受，减少算法耗时，通常选择由当前新解经过简单地变换即可产生新解的方法，如对构成新解的全部或部分元素进行置换、互换等，注意到产生新解的变换方法决定了当前新解的邻域结构，因而对冷却进度表的选取有一定的影响。
第二步是计算与新解所对应的目标函数差。因为目标函数差仅由变换部分产生，所以目标函数差的计算最好按增量计算。事实表明，对大多数应用而言，这是计算目标函数差的最快方法。
第三步是判断新解是否被接受,判断的依据是一个接受准则，最常用的接受准则是Metropo1is准则： 若Δt′<0则接受S′作为新的当前解S,否则以概率exp(-Δt′/T)接受S′作为新的当前解S。
第四步是当新解被确定接受时，用新解代替当前解，这只需将当前解中对应于产生新解时的变换部分予以实现，同时修正目标函数值即可。此时，当前解实现了一次迭代。可在此基础上开始下一轮试验。而当新解被判定为舍弃时，则在原当前解的基础上继续下一轮试验。 模拟退火算法与初始值无关，算法求得的解与初始解状态S（是算法迭代的起点）无关；模拟退火算法具有渐近收敛性，已在理论上被证明是一种以概率l 收敛于全局最优解的全局优化算法；模拟退火算法具有并行性。

㈢ 模拟退火算法在钢筋混凝土结构与构件设计中的应用方式主要有哪些

有以下应用。
基于模拟退火算法理论,建立某悬臂浇筑拱桥参数化有限元模型,使用Matlab与Ansys联合求解施工阶段全局最优索力数值解。计算结果表明:修正后的索力较原设计索力普遍。
结合我国现行的结构设计规范,对承受多工况荷载下的钢筋混凝土框架(RC)结构离散变量的优化设计问题,提出了一种基于模拟退火算法的优化算法。通过建立配筋模板数据库,将梁柱的计算配筋面积转换成最优的且满足规范和施工要求的实际配筋形式。在模拟退火算法中提出了自适应设计域技术,提高了算法的效率。将上述优化算法在大型有限元软件ANSYS和建筑结构设计专用软件SATWE软件上进行了程序实现。对一个15层的结构进行了优化设计,结果表明本文提出的方法是有效的和可操作的。

㈣ 模拟退火法^[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(-ck^1/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算法在模型修改、接受概率以及降温曲线上的改进使得模拟退火算法收敛速度大大加快。后人在此基础上还有很多的改进，读者可以参考相关文献。

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

㈤ 模拟退火算法的意义

退火算法具有计算过程简单、通用、鲁棒性强、适合并行处理等优点，可用于求解复杂的非线性优化问题。缺点: 收敛速度慢，执行时间长，算法性能与初值有关，参数敏感。Pso: 进化支持计算的优点在于它能处理一些传统方法无法处理的例子，如不可微节点传递函数或其固有的梯度信息缺失。缺点是: 它在某些问题上表现不是特别好。图2。网络权重容量的编码和遗传算子的选择有时比较麻烦

㈥ 模拟退火算法 Simulated Annealing

模拟退火算法的思想受启发于自然界中固体由高温到低温的过程中其内部分子状态及内部能量的变化规律。

退火 指物体 逐渐降温冷却 的物理现象。温度越低，物体的能量越低，在结晶状态是系统的能量状态到达最低。在自然中，缓慢降温（退火）可以导致结晶，而与之相对的快速降温（淬火）会导致不是最低能态的非晶体形态。

退火的过程可以表示为下图，左边为最初的非晶态状态；经过升温，系统能量增大后到达中间的状态；再缓慢降温到达晶体态，此时能量最小

我们用一个搜索函数最优解来直观表示：C为函数的全局最优解，在只采用贪心策略的情况下，如果从A点开始搜索，最终得到的解为B点，然而这只是一个局部的较好解。

为了避免陷入局部的最优解，模拟退火算法在搜索过程中加入了一个随机因素，会以一定的概率接收一个比当前解较差的解，因此就有可能没渗越过B与C之间的高峰，到达旁郑全局最优解

在这里，可以将解（横坐标的值）理解为固体的状态，函数值理解为系统的内能。算法以固体所处的温度T为控制参数，随着T的下降使固体内能（目标函数值）也逐渐下降，直至趋于全局最小。

根据Metropolis准则，在温度为T时， 接受 能量从 的概率为P:

在特定温度下，经过充分转换，材料达到热平衡。这时材料处于状态 的概率为

其中 表示材料当前的状态， 表示材料的状态集合， 为玻尔兹曼常数。根据上式可以得到以下结论

因此，如果我们运用退火思想放在优化问题上，在降温过程中问题的解进行充分地“热交换”，即进行充分地重新排运察颂列，同样可以帮助我们寻找最优解，理论上也会具有达到全局最优解的性能！

可以看出，算法实际上是两层循环嵌套，外层循环控制温度，内层循环来进行扰动产生新解。

随着温度逐渐降低，算法最终由可能收敛到全局最优，这里说有可能的原因是因为，在温度很低时，虽然从地内能状态跳到高内能状态的可能性不大，但是也有可能发生。

在已知的某个定义域内求函数最优值的问题通常有以下三种情况，以求最小值问题为例（求最大值可以转换为求最小值）

模拟退火算法就是为了应对第三种情况而提出的

参考资料：
https://www.cnblogs.com/ranjiewen/p/6084052.html
https://blog.csdn.net/weixin_40562999/article/details/80853418