基于MATLAB的退火算法的模拟

1、模拟退火算法（MATLAB实现） xx目录目录模拟退火算法及模型1.1 物理退火过程 退火是指将固体加热到足够高的温度，使分子呈随机排列状态，然后逐步降温使之冷却，最后分子以低能状态排列，固体达到某种稳定状态。 模仿自然界退火現象而得，利用了物理中固体物质的退火过程与一般优化问题的相似性 从某一初始温度开始，伴随温度的不断下降，结合概率突跳特性在解空间中随机寻找全局最优解模拟退火算法及模型1.2 数学表述在温度T，分子停留在状态r满足Boltzmann概率分布模拟退火算法及模型在在同一个温度同一个温度T，选定两个能量，选定两个能量E1E2，有，有模拟退火算法基本思想模拟退火算法基本思想：在一定

2、温度下，搜索从一个状态：在一定温度下，搜索从一个状态随机地变化到另一个状态；随着温度的不断下降直到最低随机地变化到另一个状态；随着温度的不断下降直到最低温度，搜索过程以概率温度，搜索过程以概率1停留在最优解停留在最优解TkEETkETZEEPEEPBB12121exp1exp)(1模拟退火算法及模型BoltzmanBoltzman概率分布概率分布告诉我们：告诉我们： （1）在同一个温度，分子停留在能量小状态的概率大于停）在同一个温度，分子停留在能量小状态的概率大于停留在能量大状态的概率留在能量大状态的概率 （2）温度越高，不同能量状态对应的概率相差越小；温度）温度越高，不同能量状态对应的概率相

3、差越小；温度足够高时，各状态对应概率基本相同。足够高时，各状态对应概率基本相同。 （3）随着温度的下降，能量最低状态对应概率越来越大；）随着温度的下降，能量最低状态对应概率越来越大；温度趋于温度趋于0时，其状态趋于时，其状态趋于1模拟退火算法及模型Metropolis准则（准则（1953）以概率接受新状态以概率接受新状态 若在温度若在温度T，当前状态，当前状态i 新状态新状态j 若若EjEi，则接受，则接受 j 为当前状态；为当前状态； 否则，若概率否则，若概率 p=exp-(Ej-Ei)/kBT 大于大于0,1)区间的随机数，区间的随机数，则仍接受状态则仍接受状态 j 为当前状态；若不成立则

4、保留状态为当前状态；若不成立则保留状态 i 为当为当前状态。前状态。模拟退火算法及模型相似性比较相似性比较应用举例用模拟退火算法解决如下10个城市的TSP问题模拟退火算法关键参数和操作的设计模拟退火算法关键参数和操作的设计状态产生函数的设计状态产生函数的设计（1）互换操作，随机交换两个城市的顺序；）互换操作，随机交换两个城市的顺序；（2）逆序操作，两个随机位置间的城市逆序；）逆序操作，两个随机位置间的城市逆序；（3）插入操作，随机选择某点插入某随机位置。）插入操作，随机选择某点插入某随机位置。283591467281593467模拟退火算法关键参数和操作的设计参数设定参数设定 截止温度截止温度 tf=0.01; 退温系数退温系数 lam=0.95; 内循环次数内循环次数 iLk=20运行过程模拟退火算法的优缺点模拟退火算法的优点模拟退火算法的优点 质量高；质量高； 初值鲁棒性强；初值鲁棒性强； 简单、通用、易实现。简单、通用、易实现。模拟退火算法的缺点模拟退火算法的缺点 由于要求较高的初始温度、较慢的降温速率、较低的终由于要求较高