模拟退火算法

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

模拟退火算法，通常被用在最优化问题里。在数学建模中，常见的优化的方法有很多，例如直接通过遍历求解等。但是并不是什么问题都合适用遍历求解，例如，当变量的个数有五六个，或者变量的取值范围很大，遍历通常在有效时间内不能求解出最优解。那么，我们就需要引入一种非线性方法来优化，例如模拟退火，粒子群优化、遗传算法等。在这些算法中，在我认为，模拟退火最简单或最容易理解。

算法原理介绍

统计力学表明材料中粒子的不同结构对应粒子的不同能力水平。在高温条件下，粒子的能量较高，可以自由运动和重新排列。在低温条件下，粒子能量较低。如果从高温开始，非常缓慢的降温(这个过程被称为退火)，粒子就可以在每个温度下达到热平衡。当系统完全被冷却时，最终形成处于低能状态的晶体。

如果粒子的能量定义材料的状态，Metropolis算法用一个简单的数学模型描述了退火过程。假设材料在状态 \(i\) 之下的能量为\(E(i)\)，那么材料在温度T时从温度T时状态从 \(i\) 进入状态 \(j\) 就遵循以下规律：

如果\(E(j)\leq E(i)\)，则接受该状态被转化
如果\(E(j) > E(i)\)，则状态转换以如下概率被接受：

\[e^{\frac{{E(i)-E(j)}}{KT}} \]
式中，K为物理学中玻尔兹曼常数， T为材料温度

公式推导

算法引入最优化问题

以上的公式，说明经过以上的退火后，材料会以很大的概率进入最小能量状态。如果变成最优化问题，则我们可将我们需要优化的表达式视为能量(通常我们求解最优解都是求解最小值，如需求解最大值，需要做相关的变化，或者将优化函数适当修改成\(-F(x)\))。我们不断降温，最后该表达式会以很大的概率为全局最优解

为什么模拟退火算法好用呢？因为我们有很大的机率求的全局最优解，而非局部最优解。

模拟退火算法的核心思想就是：我们如果求解出更优解，那么就更新数据。如果结果不是更优，那么，还是有可能继续前进的。但是，前进是有条件的，是以\(e^{(({E(i)-E(j)})/KT)}\)的概率前进。我们观察概率，当T越大，那么概率越大，前进的可能性就越大。如何理解呢？我们从模拟退火的物理原理来讨论，当温度越高，分子的能量越高，越不稳定，就可以自由运动和重新排列，因此有大的机率会前进。而当温度降低，前进的概率变小，粒子的能量较低。

模拟退火的好处就在这里，当温度越高，越不稳定，就越有可能跳跃，尽管当前的值不是更优的，但是，它有可能跳到另外一个低谷，意外的找到另外一个最有解。当温度降低的时候，就越趋于稳定，这就是模型退火的核心思想，能够很好的解决传统算法会陷入局部最优解的问题。

如果从高温开始，非常缓慢的降温，那么粒子可以在每个温度下达到热平衡。当温度完全冷却时，就有很大的概率找到全局最优解。

因此，关于模型退火大参数选择通常有初始温度，降火速度，以及截至温度。需要根据你求解的问题去选择相应的参数。通常来说，参数的个数越多，取值范围越大，就需要提高初始温度，减慢退火速度。如果降温足够慢，退火时间足够长，那么找到全局最优解的概率就越大，但是又面临着计算时间太长的问题。

算法步骤

初始化

由一个产生函数从当前解产生一个位于解空间的新解，并定义一个足够大的数值作为初始温度。

迭代过程

迭代过程是模拟退火算法的核心步骤，分为新解的产生和接受新解两部分：

由一个产生函数从当前解产生一个位于解空间的新解；为便于后续的计算和接受，减少算法耗时，通常选择由当前新解经过简单地变换即可产生新解的方法，如对构成新解的全部或部分元素进行置换、互换等，注意到产生新解的变换方法决定了当前新解的邻域结构，因而对冷却进度表的选取有一定的影响。
计算与新解所对应的目标函数差。因为目标函数差仅由变换部分产生，所以目标函数差的计算最好按增量计算。事实表明，对大多数应用而言，这是计算目标函数差的最快方法。
判断新解是否被接受，判断的依据是一个接受准则，最常用的接受准则是Metropolis准则：若Δt′<0则接受S′作为新的当前解S，否则以概率exp（-Δt′/T）接受S′作为新的当前解S。
当新解被确定接受时，用新解代替当前解，这只需将当前解中对应于产生新解时的变换部分予以实现，同时修正目标函数值即可。此时，当前解实现了一次迭代。可在此基础上开始下一轮试验。而当新解被判定为舍弃时，则在原当前解的基础上继续下一轮试验。

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

停止准则

迭代过程的一般停止准则：温度T降低至某阈值时，或连续若干次迭代均未接受新解时，停止迭代，接受当前寻找的最优解为最终解。

退火方案

在某个温度状态T下，当一定数量的迭代操作完成后，降低温度T，在新的温度状态下执行下一个批次的迭代操作。

模拟退火代码

e = 0.1^30;	% 截至温度
L = 20000;	% 计算次数，自定义
at = 0.000;	% 退火速度
T = 5000;	% 初始温度
rand('state', sum(clock));	% 初始化随机数发生器
for k = 1:L	% 退火过程
	x_new = x + randn();	% 新解产生器
	f_new = f(x_new);
	df = f_new - f;
	if df < 0	% 接受准则
		f = f_new;
		x = x_new;	% 参数更新
	elseif exp(-df/T) > rand
		f = f_new;
		x = x_new;	% 参数更新
	end
	T = T * at;
	if T < e
		break;
	end	
end

新解产生器没有固定的写法，通常时将当前解经过简单地变换（扰动当前解）

总结

模型退火算法是一个从物理退火过程改造而得的一个最优化算法，是一个搜索全局最优解的一个算法。

模型退火的核心思想很简单，就是随机搜索一个新解，如果此新解更优，则更新参数；如果该新解不是更优，但是也有一定的概率继续前进。此算法能够避免陷入局部最优解。如果求解空间太大，那么模型退火也能够提高搜索速度。理论证明，如果温度下降的十分缓慢，而在每个温度都优足够多次的状态转换，使之在每一个温度下达到热平衡，则全局最优解将以概率1被找到。因此，可以说模拟退火算法可以找到全局最优解。

标签：退火,新解,算法,模拟退火,最优,温度
From： https://www.cnblogs.com/chrisng/p/16709152.html