模拟退火算法(Simulated Annealing algorithm ，简称SA )是柯克帕垂克(S. Kirkpatrick )于1982年受热力学中的固体退火过程与组合优化问题求解之间的某种“相似性”所启发而提出的，用于求解大规模组合优化问题的一种具有全局搜索 功能的随机性近似算法。与求解线性规划的单纯形法、Karmarkar 投影尺度法，求
解非线性规划的最速下降法、Newton 法、共轭梯度法，求解整数规划的分支定界法、割平面法等经典的优化算法相比，模拟退火算法在很大程度上不受制于优化问
题的具体形式和结构，具有很强的适应性和鲁棒性，因而也具有广泛的应用价值。
模拟退火算法源于对固体退火过程的模拟；采用Metropolis 接受准则；并用
一组称为冷却进度表的参数来控制算法进程，使得算法在多项式时间里给出一个近
似最优解。固体退火过程的物理现象和统计性质是模拟退火算法的物理背
景;Metropolis 接受准则使算法能够跳离局部最优的“陷阱”，是模拟退火算法能
够获得整体最优解的关键；而冷却进度表的合理选择是算法应用的关键。
1 物理退火过程
物理中的固体退火是先将固体加热至熔化，再徐徐冷却，使之凝固成规整晶体
的热力学过程。在加热固体时，固体粒子的热运动不断增加，随着温度的升高，粒子 与其平衡位置的偏离越来越大，当温度升至溶解温度后，固体的规则性被彻底破坏,
固体溶解为液体，粒子排列从较有序的结晶态转变为无序的液态，这个过程称为溶解。溶解过程的目的是消除系统中原先可能存在的非均匀状态，使随后进行的冷却 过程以某一平衡态为始点。溶解过程与系统的熵增过程相联系，系统能量也随温度
神龙赋
的升高而增大。
冷却时，液体粒子的热运动渐渐减弱，随着温度的徐徐降低，粒子运动渐趋有
关于加强商业性房地产信贷管理的通知序。当温度降至结晶温度后，粒子运动变为围绕晶体格点的微小振动，液体凝固成固体的晶态，这个过程称为退火。退火过程之所以必须“徐徐”进行，是为了使系统在每一温度下都达到平衡态，最终达
到固体的基态(图1-1)。退火过程中系统的熵值
(衡量不能利用的热能数量)不断减少，系统能量也随温度降低趋于最小值。冷却时，若急剧降低温度，则将引起淬火效应，即固体只能冷凝为非均匀的亚稳态，系统能量也不会达到最小值。
退火过程中系统在每一温度下达到平衡态的过程，可以用封闭系统的等温过程来描述。根据玻尔兹曼(Boltzmann )有序性原理，退火过程遵循应用于热平衡封闭系统的热力学定律——自由能减少定律:
“对于与周围环境交换热量而温度保持不变的封闭系统，系统状态的自发变化总是朝着自由能减少的方向进行，当自由能达到最小值时，系统达到平衡态”。
系统的自由能F E TS =-，其中E 是系统的内能,T 是系统温度,S 是系统的熵。设 i 和j 是恒温系统的两个状态，即i i i F E TS =-和j j j F E TS =-,伊甸园信箱
而
()()j i j i j i F F F E E T S S E T S ?=-=---=?-?
若系统状态由i 自发变化到j ，则应有0F ?<。显然，能量减少(0E ?<)与熵
增加
(0S ?>)有利于自发变化。因此任一恒定温度下，系统状态从非平衡自发变化
到平衡态，都是能量和熵竞争的结果，温度决定着这两个因素的相对权重。在高温下，熵占统治地位，有利于变化的方向就是熵增加的方向，因而显出粒子的无序状态，而低温对应于低熵，低温下能量占优势，能量减少的方向有利于自发变化，因而得到有序(低熵)和低能的晶体结构。 2 Metropolis 算法
固体在恒定温度下达到热平衡的过程可以蒙特卡罗(Monte Carlo )方法进行
模拟。Monte Carlo 方法的特点是算法简单，但必须大量采样才能得到比较精确的结果，因而计算量很大。
从物理系统倾向于能量较低的状态，而热运动又妨碍它准确落入最低态的物理图像出发，采样时着重取那些有重要贡献的状态，则可以较快地得到较好的结果。
1953年,Metropolis 等提出了固体在恒定温度下达到热平衡的重要性采样法。他们用下述方法产生固体的状态序列:
先给定以粒子相对位置表征的初始状态i ，作为固体的当前状态，该状态的能量是i E 。然后用摄动装置使随机选取的某个粒子的位移随机地产生一微小变化，得到一个新状态j ，新状态的能量是j E 。如都在空城
果j i E E <，则该新状态就作为“重要”状态。如果j i E E >，则考虑到热运动的影响，该新状态是否是“重要”状态，要根据固体处于该状态的概率来判断。固体处于状态j 和状态i 的概率的比值等于相应Boltzmann 因子1的比值，即
exp()i j
E E r kT -= (1.1)
则1r <。用随机数发生器产生区间[0,1)上服从均匀分布的随机数ξ，若r ξ>，则新状态j 作为重要状态，并以j 取代i 成为当前状态；否则舍去状态j ，仍以i 为当前状态。
重复以上新状态的产生过程。在大量迁移(固体状态的变换称为迁移)后，系统趋于能量较低的平衡状态，固体状态的概率分布趋于(1.1)式的Gibbs 正则分布。
由(1.1)式可知，高温下可接受与当前状态能差较大的新状态为重要状态，而在低温下只能接受与当前状态能差较小的新状态为重要状态。这与不同温度下热运动的影响完全一致，在温度趋于零时，就不能接受任何成立j i E E >时的新状态j 了。上述接受新状态的准则称为Metropolis 准则，相应的算法被称为Metropolis 算法。
.3 模拟退火算法
对固体退火过程的研究给人们以新的启示。1982年,Kirkpatrick 等首先意识到固体退火过程与组合优化问题之间存在的类似性,Metropolis 等对固体在恒定温度下达到热平衡过程的模拟也给他们以启迪：应该把 Metropolis 准则引入到优化过程中来。最终他们得
1由统计物理的知识，温度为T 的固体处于能量为E i 的微观态i 的概率为()exp i C E kT -，其中()
exp i E -称为玻尔兹曼(Boltzmann )因子,k 为Boltzmann 常数,T 为绝对温度,C 是与E i 无关的常数，上述概率分布也称为吉布斯(Gibbs )正则分布。容易知道，当固体处于能量较低的微观态的概率较大；在温度降低时，那些能量相比最低的微观态最有可能出现；当温度趋于零时，固体只能处于能量为最小值的基态上。
到一种对Metropolis 算法进行迭代的组合优化算法，因这种算法模拟固体退火过程，故称之为“模拟退火算法”。
在模拟退火算法中，设优化问题的控制参数为t 时的一个解t i x 及其非负目标函数()t i f x 分别与固体的在某一温度下的一个微观状态i 及其能量i E 等价，设随着算法进程递减其值的控制参数t 相当固体退火过程中的温度的角，则对于控制参数t 的每一取值，算法持续进行“产生新解—判断—接受/舍弃”的迭代过程就对应着固体在某一恒定温度下趋于热平衡的过程，也就是执行了一次Metropolis 算法。与Metropolis 算法从某一初始状态出发，通过计算系统的时间演化过程，求出系统最终达到的状态相似，
模拟退火算法从某个初始解出新知岛
发，经过大量解的变换后，可以求得给定控制参数值t 时组合优化问题的相对最优解t opt x 。
然后减少控制参数t 的值，重复执行Metropolis 算法，就可以在控制参数t 趋于零时，最终求得组合优化问题的整体最优解。由于固体退火必须“徐徐”降温,
才能使固体在每一温度下都达到热平衡，最终趋于能量最小的基态，控制参数的值也必须缓慢衰减，才能确保模拟退火算法最终趋于组合优化问题的整体最优解集。
模拟退火算法用Metropolis 算法产生组合优化问题解的序列，并由与Metropolis 准则对应的转移概率P :
1,()()()()()exp(),()()
t t j i t t
t t
t i j i j t t j i f x f x P x x f x f x f x f x t ??≤?=?->?? (1.2) 确定是否接受从当前解t i x 到新解t
j x 的转移。式(1.2)中的t R +∈表示控制参数。开始让t 取
平安培训系统
较大的值(与固体的熔解温度相对应)，在进行足够多的转移后，缓慢减少t 的值(与“徐徐”降温相对应)，如此重复，直至满足某个停止准则是算法终止。因此，模拟退火算法可视为递减控制参数值时Metropolis 算法的迭代。图1.1和图1.2描述了固体退火过程与模拟退火算法之间的相似性。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议