模拟退火法算法（组合优化）
需积分: 14 61 浏览量
2009-09-13
08:51:32
上传
评论 1
收藏 164KB PDF 举报
模拟退火算法及其 Matlab 实现
模拟退火算法（Simulated Annealing algorithm，简 称 SA）是柯克帕垂克（S. Kirkpatrick）
于 1982 年受热力学中的固体退火过程与组合优化问题求解之间的某种“相似性”所启发而
提出的，用于求解大规模组合优化问题的一种具有全局搜索功能的随机性近似算法。与求解
线性规划的单纯形法、Karmarkar 投影尺度法，求解非线性规划的最速下降法、Newton 法、
共轭梯度法，求解整数规划的分支定界法、割平面法等经典的优化算法相比，模拟退火算法
在很大程度上不受制于优化问题的具体形式和结构，具有很强的适应性和鲁棒性，因而也具
有广泛的应用价值。
模拟退火算法源于对固体退火过程的模拟；采用 Metropolis 接受准则；并用一组称为冷
却进度表的参数来控制算法进程，使得算法在多项式时间里给出一个近似最优解。固体退火
过程的物理现象和统计性质是模拟退火算法的物理背景；Metropolis 接受准则使算法能够跳
离局部最优的“陷阱”，是模拟退火算法能够获得整体最优解的关键；而冷却进度表的合理
选择是算法应用的关键。
1 物理退火过程
物理中的固体退火是先将固体加热至熔化，再徐徐冷却，使之凝固成规整晶体的热力
学过程。在加热固体时，固体粒子的热运动不断增加，随着温度的升高，粒子与其平衡位置
的偏离越来越大，当温度升至溶解温度后，固体的规则性被彻底破坏，固体溶解为液体，粒
子排列从较有序的结晶态转变为无序的液态，这个过程称为溶解。溶解过程的目的是消除系
统中原先可能存在的非均匀状态，使随后进行的冷却过程以某一平衡态为始点。溶解过程与
系统的熵增过程相联系，系统能量也随温度的升高而增大。
冷却时，液体粒子的热运动渐渐减弱，随着温度的徐徐降低，粒子运动渐趋有序。当
温度降至结晶温度后，粒子运动变为围绕晶体格点的微小振动，液体凝固成固体的晶态，这
个过程称为退火。退火过程之所以必须“徐徐”进行，是为了使系统在每一温度下都达到平
衡态，最终达到固体的基态（图 1-1）。退火过程中系统的熵值（衡量不能利用的热能数量）
不断减少，系统能量也随温度降低趋于最小值。冷却时，若急剧降低温度，则将引起淬火效
应，即固体只能冷凝为非均匀的亚稳态，系统能量也不会达到最小值。
退火过程中系统在每一温度下达到平衡态的过程，可以用封闭系统的等温过程来描述。
根据玻尔兹曼（Boltzmann）有序性原理，退火过程遵循应用于热平衡封闭系统的热力学定
律——自由能减少定律：
“
对于与周围环境交换热量而温度保持不变的封闭系统，系统状态的自发变化总是朝
着自由能减少的方向进行，当自由能达到最小值时，系统达到平衡态”。
系统的自由能
，其中 是系统的内能，
T
是系统温度， 是系统的熵。设
和 是恒温系统的两个状态，即
FETS=− E S
i
j
ii
FETS
i
=
−
和
jj j
FETS
=
−
，而
()()
ji ji ji
FFF EE TS S ETS∆= − = − − − =∆−∆
若系统状态由
i
自发变化到 ，则应有
j
0F
∆
<
。显然，能量减少（
0E
∆
<
）与熵增加
资源评论
