精品文档
模拟退火算法
一 定义
1 概念
什么是退火？在热力学上，退火现象指物体逐渐降温的物理现象，温度愈低，物体的能量状态会低；够低后，液体开始冷凝与结晶，在结晶状态时，系统的能量状态最低。大自然在缓慢降温（亦即，退火）时，可“找到”最低能量状态：结晶。但是，如果过程过急过快，快速降温（亦称「淬炼」）时，会导致不是最低能态的非晶形。如下图所示，首先（左图）物
体处于非晶体状态。我们将固体加温至充分高（中图），再让其徐徐冷却，也就退火（右图）。加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小（此时物体以晶体形态呈现）。
似乎，大自然知道慢工出细活：缓缓降温，使得物体分子在每一温度时，能够有足够时间找到安顿位置，则逐渐地，到最后可得到最低能态，系统最安稳。
模拟退火算法(SA)最早的思想是由N. Metropolis 等人于1953年提出。1983 年,S. Kirkpatrick 等成功地将退火思想引入到组合优化领域。它是基于Monte-Carlo迭代求解策略的一种随机寻优算
随意编辑
精品文档
法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。模拟退火算法从某一较高初温出发，伴随温度参数的不断下降,结合概率突跳特性在解空间中随机寻找目标函数的全局最优解，即在局部最优解能概率性地跳出并最终趋于全局最优。
模拟退火其实也是一种贪心算法，但是它的搜索过程引入了随机因素。在迭代更新可行解时，以一定的概率来接受一个比当前解要差的解，因此有可能会跳出这个局部的最优解，达到全局的最优解。以下图为例，假定初始解为左边蓝色点A，模拟退火算法会快速搜索到局部最优解B，但在搜索到局部最优解后，不是就此结束，而是会以一定的概率接受到左边的移动。也许经过几次这样的不是局部最优的移动后会到达全局最优点D，于是就跳出了局部最小值。
根据热力学的原理，在温度为T时，出现能量差dE的降温的概率为P(dE)，
?dE?10-23，表示为: P?dE??exp?其中k是波尔兹曼常数，值为k=1.3806488(13)×?。
?kT?exp表示自然指数，且dE<0。因此dE/kT<0，所以P(dE)函数的取值范围是(0,1)。满足概率密度函数的定义。其实这条公式更直观意思就是：温度越高，出现一次能量差为P(dE)的降温的概率就越大；温度越低，则出现降温的概率就越小。
随意编辑
精品文档
在实际问题中，这里的“一定的概率”的计算参考了金属冶炼的退火过程。假定当前可行解为x，迭代更新后的解为x_new，那么对应的“能量差”定义为：
?f?f?x_new??f?x?，其对应的一定概率为：
P??f??{
??f?exp???，最小值优化问题?kT???f?exp??，最大值优化问题
?kT?2 SA算法基本要素
(1) 状态空间与状态产生函数
1）搜索空间也称为状态空间，它由经过编码的可行解的集合组成。 2）状态产生函数（邻域函数）应尽可能保证产生的候选解遍布全部解空间。通常由两部分组成，即产生候选解的方式和候选解产生的概率分布。
3）候选解一般采用按照某一概率密度函数对解空间进行随机采样来获得。 4）概率分布可以是均匀分布、正态分布、指数分布等。 (2) 状态转移概率
1）状态转移概率是指从一个状态向另一个状态的转移概率。 2）通俗的理解是接受一个新解为当前解的概率。 3）它与当前的温度参数T有关，随温度下降而减小。 4）一般采用Metropolis准则。
随意编辑
精品文档
(3) 内循环终止准则
也称Metropolis抽样稳定准则，用于决定在各温度下产生候选解的数目。常用的抽样稳定准则包括：
1）检验目标函数的均值是否稳定。 2）连续若干步的目标值变化较小。 3）按一定的步数抽样。 (4) 外循环终止准则
即算法终止准则，常用的包括： 1）设置终止温度的阈值。 2）设置外循环迭代次数。
3）算法搜索到的最优值连续若干步保持不变。 4）检验系统熵是否稳定。
3 算法步骤
(1) 初始化：初始温度T（充分大），温度下限Tmin（充分小），初始解状态x(是算法迭
代的起点)，每个T值的迭代次数L；
(2) 对l=1,2,...,L做第(3)至第(6)步；
随意编辑
精品文档
(3) 产生新解x_new: ( x_new = x + Δx )；
(4) 利计算增量Δf=f(x_new)?f(x)，其中f(x)为优化目标；
(5) 若Δf < 0 (若寻找最小值，Δf > 0)则接受x_new作为新的当前解，否则以概率
??f?exp???接受x_new作为新的当前解；
kT??(6) 如果满足终止条件则输出当前解作为最优解，结束程序。(终止条件通常取为连续若干
个新解都没有被接受时终止算法。)；
(7) T逐渐减少，且T>Tmin，然后转第(2)步。
随意编辑
模拟退火算法报告
