模拟退火算法详解1.

第三章模拟退火算法现代优化计算3.1模拟退火算法及模型3.1.1物理退火过程3.1.2组合优化与物理退火的相似性3.1.3模拟退火算法的基本思想和步骤3.2模拟退火算法的关键参数和操作的设计3.2.1状态产生函数3.2.2状态接受函数3.2.3初温3.2.4温度更新函数3.2.5内循环终止准则3.2.6外循环终止准则3.3模拟退火算法的改进3.3.1模拟退火算法的优缺点3.3.2改进内容现代优化计算3.1模拟退火算法及模型现代优化计算算法的提出模拟退火算法最早的思想由Metropolis等（1953）提出，1983年Kirkpatrick等将其应用于组合优化。算法的目的解决NP复杂性问题；克服优化过程陷入局部极小；克服初值依赖性。3.1.1物理退火过程3.1模拟退火算法及模型现代优化计算物理退火过程什么是退火：退火是指将固体加热到足够高的温度，使分子呈随机排列状态，然后逐步降温使之冷却，最后分子以低能状态排列，固体达到某种稳定状态。3.1.1物理退火过程3.1模拟退火算法及模型现代优化计算物理退火过程加温过程——增强粒子的热运动，消除系统原先可能存在的非均匀态；等温过程——对于与环境换热而温度不变的封闭系统，系统状态的自发变化总是朝自由能减少的方向进行，当自由能达到最小时，系统达到平衡态；冷却过程——使粒子热运动减弱并渐趋有序，系统能量逐渐下降，从而得到低能的晶体结构。3.1.1物理退火过程热力学中的退火现象指物体逐渐降温时发生的物理現象：温度越低，物体的能量状态越低，到达足够的低点时，液体开始冷凝与结晶，在结晶状态时，系统的能量状态最低。缓慢降温（退火，annealing）时，可达到最低能量状态；但如果快速降温（淬火，quenching），会导致不是最低能态的非晶形。为什么缓慢降温：缓缓降温，使得物体分子在每一温度时，能够有足够时间找到安顿位置，则逐渐地，到最后可得到最低能态，系统最稳定。3.1模拟退火算法及模型3.1.1物理退火过程现代优化计算模仿自然界退火現象而得，利用了物理中固体物质的退火过程与一般优化问题的相似性从某一初始温度开始，伴随温度的不断下降，结合概率突跳特性在解空间中随机寻找全局最优解3.1模拟退火算法及模型3.1.1物理退火过程现代优化计算3.1模拟退火算法及模型现代优化计算数学表述在温度T，分子停留在状态r满足Boltzmann概率分布3.1.1物理退火过程DsBBBTksETZTZkrrEETkrETZrEEP)(exp)()(Boltzmann0)()(exp)(1)}({子：为概率分布的标准化因常数。为的能量，表示状态机变量，表示分子能量的一个随3.1模拟退火算法及模型现代优化计算数学表述在同一个温度T，选定两个能量E1E2，有3.1.1物理退火过程TkEETkETZEEPEEPBB12121exp1exp)(1}{}{10模拟退火算法基本思想：在一定温度下，搜索从一个状态随机地变化到另一个状态；随着温度的不断下降直到最低温度，搜索过程以概率1停留在最优解3.1模拟退火算法及模型现代优化计算3.1.1物理退火过程温度对的影响①当很大时，，各状态的概率几乎相等SA开始做广域搜索，随着温度的下降差别扩大kTkT0kiTEnEPii1riEPiiEP3.1模拟退火算法及模型现代优化计算3.1.1物理退火过程②当时，与的小差别带来和的巨大差别例如：=90，=100，0kTkiTEiEjEkiTPkjTPiEjE3.1模拟退火算法及模型现代优化计算3.1.1物理退火过程I.当=100时kT367.0406.0367.0406.010010010090kkkkkjkiCCueCeCEPEP3.1模拟退火算法及模型现代优化计算3.1.1物理退火过程II.当=1时此时结论:时，以概率1趋于最小能量状态kT200001072.310194.84440kkkjkiCCEPEPkinikiEPEP10kT3.1模拟退火算法及模型3.1.1物理退火过程现代优化计算Boltzman概率分布告诉我们：（1）在同一个温度，分子停留在能量小状态的概率大于停留在能量大状态的概率（2）温度越高，不同能量状态对应的概率相差越小；温度足够高时，各状态对应概率基本相同。（3）随着温度的下降，能量最低状态对应概率越来越大；温度趋于0时，其状态趋于13.1模拟退火算法及模型现代优化计算数学表述若|D|为状态空间D中状态的个数，D0是具有最低能量的状态集合：当温度很高时，每个状态概率基本相同，接近平均值1/|D|；状态空间存在超过两个不同能量时，具有最低能量状态的概率超出平均值1/|D|；当温度趋于0时，分子停留在最低能量状态的概率趋于1。3.1.1物理退火过程能量最低状态非能量最低状态3.1模拟退火算法及模型现代优化计算相似性比较3.1.2组合优化与物理退火的相似性组合优化问题金属物体解粒子状态最优解能量最低的状态目标函数能量3.1模拟退火算法及模型现代优化计算SA的计算步骤①初始化,任选初始解,,给定初始温度，终止温度，令迭代指标。注：选择时，要足够高，使②随机产生一个邻域解，计算目标值增量3.1.3模拟退火算法的基本思想和步骤Si0TfT0,0TTkk0T0kiTE的邻域表示iiNiNj,ifjff3.1模拟退火算法及模型现代优化计算3.1.3模拟退火算法的基本思想和步骤③若转步④(j比i好无条件转移)；否则产生(j比i好，有条件转移)。注：高时，广域搜索；低时，局域搜索④若达到热平衡转步⑤(每个特定温度下的搜索次数N：根据计算耗时来确定)，否则转步②。,0jif令jiTfUk,exp,1,0则令若kTkT3.1模拟退火算法及模型现代优化计算3.1.3模拟退火算法的基本思想和步骤⑤降低，若停止，否则转步②。注：降低的方法有以下两种流程框图见下页1kkkTfkTTkTTTTrrTTkkkk112.优点：简单易行。99.095.0其中较好的方法.1T=Th求得初始解BS=初始解n=0求得新的解接受新的解用新的解替换当前解;n=n+1nN？BS=新的解新的解比BS好？T=rTT=t?EndStart是否是否是是否是否新的解比当前解好？exp[01]Trandom，T:温度Th:最高温度t:最低温度BS：已经找到的最好解N:某一温度下达到平衡的搜索次数ExampleTravelingSalesmanProblem(TSP)Given6citiesandthetravelingcostbetweenanytwocitiesAsalesmanneedtostartfromcity1andtravelallothercitiesthenbacktocity1MinimizethetotaltravelingcostTSP算例Citytocity1234561247910211213836813469556SAparametersettingTh=2000t=10r=0.6N=2生成新的解：随机选择两个位置，交换其表示的城市T:温度Th:最高温度t:最低温度BS：已经找到的最好解N:某一温度下达到平衡的搜索次数T=Th求得初始解BS=初始解n=0求得新的解新的解比当前解好？接受新的解用新的解替换当前解;n=n+1exp[01]Trandom，nN？BS=新的解新的解比BS好？T=rTT=t?EndStart是否是否是否是否是否求得初始解BS=初始解SequenceThelengthoftheroute13245628BSSequenceThelengthoftheroute13245628初始解温度T＝2000n=0SequenceThelengthoftheroute12345630新的解T=Th求得初始解BS=初始解n=0求得新的解新的解比当前解好？接受新的解用新的解替换当前解;n=n+1exp[01]Trandom，nN？BS=新的解新的解比BS好？T=rTT=t?EndStart是否是否是否是否是否T:温度Th:最高温度t:最低温度BS：已经找到的最好解N:某一温度下达到平衡的搜索次数SequenceThelengthoftheroute13245628当前解SequenceThelengthoftheroute12345630新的解Exp((新的解－当前解)/T)=exp(-2/2000)Random[0,1]=0.7T=Th求得初始解BS=初始解n=0求得新的解新的解比当前解好？接受新的解用新的解替换当前解;n=n+1exp[01]Trandom，nN？BS=新的解新的解比BS好？T=rTT=t?EndStart是否是否是否是否是否T:温度Th:最高温度t:最低温度BS：已经找到的最好解N:某一温度下达到平衡的搜索次数SequenceThelengthoftheroute12345630BSSequenceThelengthoftheroute13245628当前解温度T＝2000n=1T=Th求得初始解BS=初始解n=0求得新的解新的解比当前解好？接受新的解用新的解替换当前解;n=n+1exp[01]Trandom，nN？BS=新的解新的解比BS好？T=rTT=t?EndStart是否是否是否是否是否T:温度Th:最高温度t:最低温度BS：已经找到的最好解N:某一温度下达到平衡的搜索次数SequenceThelengthoftheroute12345630SequenceThelengthoftheroute12354636新的解当前解Exp((新的解－当前解)/T)=exp(-6/2000)Random[0,1]=0.99，拒绝新的解T=Th求得初始解BS=初始解n=0求得新的解新的解比当前解好？接受新的解用新的解替换当前解;n=n+1exp[01]Trandom，nN？BS=新的解新的解比BS好？T=rTT=t?EndStart是否是否是否是否是否T:温度Th:最高温度t:最低温度BS：已经找到的最好解N:某一温度下达到平衡的搜索次数SequenceThelengthoftheroute12345630SequenceThelengthoftheroute12346533新的解当前解Exp((新的解－当前解)/T)=exp(-3/2000)Random[0,1]=0.6T=Th求得初始解BS=初始解n=0求得新的解新的解比当前解好？接受新的解用新的解替换当前解;n=n+1exp[01]Trandom，nN？BS=新的解新的解比BS好？T=rTT=t?EndStart是否是否是否是否是否T:温度Th:最高温度t:最低温度BS：已经找到的最好解N:某一温度下达到平衡的搜索次数SequenceThelengthoftheroute12345633BSSequenceThelengthoftheroute13245628当前解温度T＝1200n=2T=Th求得初始解BS=初始解n=0求得新的解新的解比当前解好？接受新的解用新的解替换当前解;n=n+1exp[01]Trandom，nN？BS=新的解新的解比BS好？T=rTT=t?EndStart是否是否是否是是否T:温度Th:最高温度t:最低温度BS：已经找到的最好解N:某一温度下达到平衡的搜索次数SequenceThelengthoftheroute12345633当前解SequenceThelengthoftheroute21345623新的解接受新的解温度T＝1200n=0T=Th求得初始解BS=初始解n=0求得新的