第九章-智能优化-2模拟退火算法

2.模拟退火算法2.1模拟退火算法及模型算法的提出模拟退火算法最早的思想由Metropolis等（1953）提出，1983年Kirkpatrick等将其应用于组合优化。算法的目的解决NP复杂性问题；克服优化过程陷入局部极小；克服初值依赖性。2.1.1物理退火过程2.1模拟退火算法及模型物理退火过程什么是退火：退火是指将固体加热到足够高的温度，使分子呈随机排列状态，然后逐步降温使之冷却，最后分子以低能状态排列，固体达到某种稳定状态。2.1.1物理退火过程2.1模拟退火算法及模型物理退火过程加温过程——增强粒子的热运动，消除系统原先可能存在的非均匀态；等温过程——对于与环境换热而温度不变的封闭系统，系统状态的自发变化总是朝自由能减少的方向进行，当自由能达到最小时，系统达到平衡态；冷却过程——使粒子热运动减弱并渐趋有序，系统能量逐渐下降，从而得到低能的晶体结构。2.1.1物理退火过程2.1模拟退火算法及模型数学表述在温度T，分子停留在状态r满足Boltzmann概率分布2.1.1物理退火过程DsBBBTksETZTZkrrEETkrETZrEEP)(exp)()(Boltzmann0)()(exp)(1)}({子：为概率分布的标准化因常数。为的能量，表示状态机变量，表示分子能量的一个随2.1模拟退火算法及模型数学表述在同一个温度T，选定两个能量E1E2，有在同一个温度，分子停留在能量小的状态的概率比停留在能量大的状态的概率要大。2.1.1物理退火过程TkEETkETZEEPEEPBB12121exp1exp)(1}{}{102.1模拟退火算法及模型Metropolis准则（1953）——以概率接受新状态固体在恒定温度下达到热平衡的过程可以用MonteCarlo方法（计算机随机模拟方法）加以模拟，虽然该方法简单，但必须大量采样才能得到比较精确的结果，计算量很大。2.1.1物理退火过程2.1模拟退火算法及模型Metropolis准则（1953）——以概率接受新状态若在温度T，当前状态i→新状态j若EjEi，则接受j为当前状态；否则，若概率p=exp[-(Ej-Ei)/kBT]大于[0,1)区间的随机数，则仍接受状态j为当前状态；若不成立则保留状态i为当前状态。2.1.1物理退火过程01-(Ej-Ei)/kTp2.1模拟退火算法及模型Metropolis准则（1953）——以概率接受新状态p=exp[-(Ej-Ei)/kBT]在高温下，可接受与当前状态能量差较大的新状态；在低温下，只接受与当前状态能量差较小的新状态。2.1.1物理退火过程2.1模拟退火算法及模型相似性比较2.1.2组合优化与物理退火的相似性组合优化问题金属物体解粒子状态最优解能量最低的状态设定初温熔解过程Metropolis抽样过程等温过程控制参数的下降冷却目标函数能量Optimization,steepestdescentandlocalminimaf(x)GlobalminimumLocalminimumLocalminimumLocalminimum要从局部最优逃出，必须上行（up-step）SA的上行机制：△＝（当前解）—（下一个解）T为温度，即SA的控制参数exp[01]Trandom，SA接受相邻解的标准令X为当前解X’新的解（相邻解）C(x)(C(x’))betheenergystate(cost)ofx(x’)概率Paccept=exp[(C(x)-C(x’))/T]N=Random(0,1)无条件接受相邻解，如果：C(x’)C(x),即相邻解比当前解好以一定的概率接受相邻解，如果C(x’)=C(x),即相邻解比当前解差当NPaccept时，接受相邻解参数设置T初始温度t冷却温度冷却过程的设定（Thecoolingschedule）L每一特定温度下的搜索次数：退火过程设定CoolingSchedule:N温度T的主要作用：决定接受差的解的概率初始温度的设定：由可忍受的解差的程度和接受的概率决定，比如以0.8的概率接受比当前解值大100，初始温度应为多少？一般温度设定为500——1000较为合适。需要运行程序多试。退火过程设定N•温度T的降低过程：•每次减少固定的值：T’=T-Td•每次按固定比例减少：T’=T*r，此方法比较常用•每个特定温度下的搜索次数L：根据计算耗时来确定。•搜索的收敛：温度降低到设定的最低温度，如0.5度。T=Th求得初始解BS=初始解n=0求得新的解新的解比当前解好？接受新的解用新的解替换当前解;n=n+1exp[01]Trandom，nN？BS=新的解新的解比BS好？T=rTT=t?EndStartT:温度Th:最高温度t:最低温度BS：已经找到的最好解N:某一温度下达到平衡的搜索次数是否是否是否是否是否ExampleTravelingSalesmanProblem(TSP)Given6citiesandthetravelingcostbetweenanytwocitiesAsalesmanneedtostartfromcity1andtravelallothercitiesthenbacktocity1MinimizethetotaltravelingcostTSP算例Citytocity12345611247910211201383617134695156SAparametersettingTh=2000t=10r=0.6N=2生成新的解：随机选择两个位置，交换其表示的城市T=Th求得初始解BS=初始解n=0求得新的解新的解比当前解好？接受新的解用新的解替换当前解;n=n+1exp[01]Trandom，nN？BS=新的解新的解比BS好？T=rTT=t?EndStartT:温度Th:最高温度t:最低温度BS：已经找到的最好解N:某一温度下达到平衡的搜索次数是否是否是否是否是否求得初始解BS=初始解SequenceThelengthoftheroute13245628BSSequenceThelengthoftheroute13245628初始解温度T＝2000n=0SequenceThelengthoftheroute12345630新的解T=Th求得初始解BS=初始解n=0求得新的解新的解比当前解好？接受新的解用新的解替换当前解;n=n+1exp[01]Trandom，nN？BS=新的解新的解比BS好？T=rTT=t?EndStartT:温度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?EndStartT:温度Th:最高温度t:最低温度BS：已经找到的最好解N:某一温度下达到平衡的搜索次数是否是否是否是否是否SequenceThelengthoftheroute12345630BSSequenceThelengthoftheroute13245628当前解温度T＝2000n=1T=Th求得初始解BS=初始解n=0求得新的解新的解比当前解好？接受新的解用新的解替换当前解;n=n+1exp[01]Trandom，nN？BS=新的解新的解比BS好？T=rTT=t?EndStartT:温度Th:最高温度t:最低温度BS：已经找到的最好解N:某一温度下达到平衡的搜索次数是否是否是否是否是否SequenceThelengthoftheroute12345630当前解SequenceThelengthoftheroute12354636新的解Exp((新的解－当前解)/T)=exp(-5/2000)Random[0,1]=0.99，拒绝新的解T=Th求得初始解BS=初始解n=0求得新的解新的解比当前解好？接受新的解用新的解替换当前解;n=n+1exp[01]Trandom，nN？BS=新的解新的解比BS好？T=rTT=t?EndStartT:温度Th:最高温度t:最低温度BS：已经找到的最好解N:某一温度下达到平衡的搜索次数是否是否是否是否是否SequenceThelengthoftheroute12345630当前解SequenceThelengthoftheroute12346531新的解Exp((新的解－当前解)/T)=exp(-1/2000)Random[0,1]=0.6T=Th求得初始解BS=初始解n=0求得新的解新的解比当前解好？接受新的解用新的解替换当前解;n=n+1exp[01]Trandom，nN？BS=新的解新的解比BS好？T=rTT=t?EndStartT:温度Th:最高温度t:最低温度BS：已经找到的最好解N:某一温度下达到平衡的搜索次数是否是否是否是否是否SequenceThelengthoftheroute12345630BSSequenceThelengthoftheroute13245628当前解温度T＝1200n=2T=Th求得初始解BS=初始解n=0求得新的解新的解比当前解好？接受新的解用新的解替换当前解;n=n+1exp[01]Trandom，nN？BS=新的解新的解比BS好？T=rTT=t?EndStartT:温度Th:最高温度t:最低温度BS：已经找到的最好解N:某一温度下达到平衡的搜索次数是否是否是否是否是否SequenceThelengthoftheroute12345630当前解SequenceThelengthoftheroute21345627新的解接受新的解温度T＝1200n=0T=Th求得初始解BS=初始解n=0求得新的解新的解比当前解好？接受新的解用新的解替换当前解;n=n+1exp[01]Trandom，nN？BS=新的解新的解比BS好？T=rTT=t?EndStartT:温度Th:最高温度t:最低温度BS：已经找到的最好解N:某一温度下达到平衡的搜索次数是否是否是否是否是否SequenceThelengthoftheroute21345627BSSequenceThelengthoftheroute21345627当前解温度T＝1200n=12.4模拟退火算法的改进模拟退火算法的优点质量高；初值鲁棒性强；简单、通用、易实现。模拟退火算法的缺点由于要求较高的初始温度、较慢的降温速率、较低的终止温度，以及各温度下足够多次的抽样，因此优化过程较长。2.4.1模拟退火算法的优缺点2.4模拟退火算法的改进改进的可行方案（1）设计合适的状态产生函数；（2）设计高效的退火历程；（3）避免状态的迂回搜索；（4）采用并行搜索结构；（5）避免陷入局部极小，改进对温度的控制方式；（6）选择合适的初始状态；（7）设计合适的算法终止准则。2.4.2改进内容2.4模拟退火算法的改进改进的方式（1）增加升温或重升温过程，避免陷入局部极小；（2）增加记忆功能（记忆“Bestsofar”状态）；（3）增加补充搜索过程（以最优结果为初始解）；（4）对每一当前状态，采用多次搜索策略，以概率接受区域内的最优状态；（5）结合其它搜索机制的算法；（6）上述各方法的综合。2.4.2改进内容2.4模拟退火算法的改进改进的思路（1）记录“Bestsofar”状态，并即时更新；（2）设置双阈值，使得在尽量保持最优性