模拟退火20120903 .ppt

1、模拟退火数学建模工作室2012年9月3日 加温过程加温过程增强粒子的热运动，消除系统原先可能存增强粒子的热运动，消除系统原先可能存在的非均匀态；在的非均匀态；等温过程等温过程对于与环境换热而温度不变的封闭系统，对于与环境换热而温度不变的封闭系统，系统状态的自发变化总是朝自由能减少的方向进行，当系统状态的自发变化总是朝自由能减少的方向进行，当自由能达到最小时，系统达到平衡态；自由能达到最小时，系统达到平衡态；冷却过程冷却过程使粒子热运动减弱并渐趋有序，系统能量使粒子热运动减弱并渐趋有序，系统能量逐渐下降，从而得到低能的晶体结构。逐渐下降，从而得到低能的晶体结构。物理退火过程模拟退火模仿工业退火的

2、机理，主要应用于组合优化问题，能克服优化过程中陷入局部最优解。一般步骤初始化及参数的设定：初始解 目标函数 循环终止准则 初始温度 降温函数内循环：扰动产生若干新解，根据函数接收准则得到当前最优解一般步骤外循环：根据降温函数，得到新的温度，重复内循环产生相应解，终止准则判读是否结束，否则继续降温产生新解，最终输出结果一般步骤初使化设定初使化设定随机产生一个初始解随机产生一个初始解扰动产生一个新解扰动产生一个新解是否接受是否接受?修改目前解修改目前解降温降温缩减温度缩减温度 是否达到中止条件是否达到中止条件?最佳解最佳解NoYesYesYesNoNo流程图算法的实现：n冷却进度表、邻域结构和新解

3、产生器、接受准则和随机数产生器一起构成算法的三大支柱。n从算法结构可知，新状态产生函数、新状态接受函数、退温函数、退火结束准则以及初始温度是直接影响算法优化结果的主要环节。n收敛性分析收敛性分析 通过理论分析可以得到初温的解析式，但解决实际问通过理论分析可以得到初温的解析式，但解决实际问题时难以得到精确的参数；题时难以得到精确的参数；初温应充分大；初温应充分大；n实验表明实验表明 初温越大，获得高质量解的机率越大，但花费较多的初温越大，获得高质量解的机率越大，但花费较多的计算时间；计算时间；初温初始解产生根据要求，生成出合理的初始解，可以提高算法的效率及精度for k=1:w c=randpe

4、rm(100);c1=1,c+1,102;flag=1;while flag0 flag=0;for m=1:L-3 for n=m+2:L-1 if d(c1(m),c1(n)+d(c1(m+1),c1(n+1)d(c1(m),c1(m+1)+d(c1(n),c1(n+1)flag=1;c1(m+1:n)=c1(n:-1:m+1);end end end end J(k,c1)=1:102;end改良圈算法产生初始解 （1）互换操作，随机交换两个城市的顺序；）互换操作，随机交换两个城市的顺序；（2）逆序操作，两个随机位置间的城市逆序；）逆序操作，两个随机位置间的城市逆序；（3）插入操作，随机

5、选择某点插入某随机位置。）插入操作，随机选择某点插入某随机位置。283591467281593467283591467283419567283591467235981467新解产生（扰动）逆序操作若C1C2，S0为原路径df=d(S0(c1-1),S0(c2)+d(S0(c1),S0(c2+1)-d(S0(c1-1),S0(c1)-d(S0(c2),S0(c2+1);新路径：S0=1:C1-1,C2:-1:C1,C2+1:end;n原则原则 (1)在固定温度下，接受使目标函数下降的候选解的概在固定温度下，接受使目标函数下降的候选解的概率要大于使目标函数上升的候选解概率；率要大于使目标函数上升的

6、候选解概率；(2)随温度的下降，接受使目标函数上升的解的概率要随温度的下降，接受使目标函数上升的解的概率要逐渐减小；逐渐减小；(3)当温度趋于零时，只能接受目标函数下降的解。当温度趋于零时，只能接受目标函数下降的解。状态接收函数if dfrand(1)也接收end接受准则 常用方法：常用方法：（1）设置终止温度的阈值；）设置终止温度的阈值；（2）设置外循环迭代次数；）设置外循环迭代次数；（3）算法搜索到的最优值连续若干步保持不变；）算法搜索到的最优值连续若干步保持不变；（4）概率分析方法。）概率分析方法。循环终止准则方法一：if T终止温度 break;end循环终止准则方法二：For i=1

7、:L .end方法三：if std(sa,1)设定值 break;end （1）增加升温或重升温过程，避免陷入局部极小；）增加升温或重升温过程，避免陷入局部极小；（2）增加记忆功能（记忆）增加记忆功能（记忆“Best so far”状态）；状态）；（3）增加补充搜索过程（以最优结果为初始解）；）增加补充搜索过程（以最优结果为初始解）；（4）对每一当前状态，采用多次搜索策略，以概率）对每一当前状态，采用多次搜索策略，以概率接受区域内的最优状态；接受区域内的最优状态；（5）结合其它搜索机制的算法；）结合其它搜索机制的算法；（6）上述各方法的综合。）上述各方法的综合。算法的改进记忆功能 记忆当前最优解，可以很大程度的提高算法的效率，例如用来生成终止准则、作为增补运算的初始解。回火技术 回火技术：回火技术：降温后以降温后以一定概率升温，一定概率升温，引入产生函数扰动因子，来控制搜寻全局最优值的范围。ABCDn优点优点 质量高；质量高；简单、通用、易实现。简单、通用、易实现。n缺点缺点 由于要求较高的初始温度、较慢的降温速率、较低的由于要求较高的初始温度、较慢的降温速率、较低的终止温度，以及各温度下足够多次的抽样，因此优化终止温度，以及各温度下足够多次的抽样，因此优化过程较长。过程较长。算法的优缺点