第九章-智能优化-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物理退火过程,2.1模拟退火算法及模型,数学表述在同一个温度T，选定两个能量E1E2，有在同一个温度，分子停留在能量小的状态的概率比停留在能量大的状态的概率要大。,2.1.1物理退火过程,0,2.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物理退火过程,2.1模拟退火算法及模型,Metropolis准则（1953）以概率接受新状态p=exp-(Ej-Ei)/kBT在高温下，可接受与当前状态能量差较大的新状态；在低温下，只接受与当前状态能量差较小的新状态。,2.1.1物理退火过程,2.1模拟退火算法及模型,相似性比较,2.1.2组合优化与物理退火的相似性,Optimization,steepestdescentandlocalminima,f(x),Globalminimum,Localminimum,Localminimum,Localminimum,要从局部最优逃出，必须上行（up-step）,SA的上行机制：（当前解）（下一个解）T为温度，即SA的控制参数,SA接受相邻解的标准,令X为当前解X新的解（相邻解）C(x)(C(x)betheenergystate(cost)ofx(x)概率Paccept=exp(C(x)-C(x)/TN=Random(0,1)无条件接受相邻解，如果：C(x)=C(x),即相邻解比当前解差当NPaccept时，接受相邻解,参数设置,T初始温度t冷却温度冷却过程的设定（Thecoolingschedule）L每一特定温度下的搜索次数：,退火过程设定,CoolingSchedule:,温度T的主要作用：决定接受差的解的概率初始温度的设定：由可忍受的解差的程度和接受的概率决定，比如以0.8的概率接受比当前解值大100，初始温度应为多少？一般温度设定为5001000较为合适。需要运行程序多试。,退火过程设定,温度T的降低过程：每次减少固定的值：T=T-Td每次按固定比例减少：T=T*r，此方法比较常用每个特定温度下的搜索次数L：根据计算耗时来确定。搜索的收敛：温度降低到设定的最低温度，如0.5度。,T=Th,求得初始解BS=初始解,n=0,求得新的解,新的解比当前解好？,接受新的解,用新的解替换当前解;n=n+1,nN？,BS=新的解,新的解比BS好？,T=rT,T=t?,End,Start,T:温度Th:最高温度t:最低温度BS：已经找到的最好解N:某一温度下达到平衡的搜索次数,是,否,是,否,是,否,是,否,是,否,Example,TravelingSalesmanProblem(TSP)Given6citiesandthetravelingcostbetweenanytwocitiesAsalesmanneedtostartfromcity1andtravelallothercitiesthenbacktocity1Minimizethetotaltravelingcost,TSP算例,SAparametersetting,Th=2000t=10r=0.6N=2生成新的解：随机选择两个位置，交换其表示的城市,T=Th,求得初始解BS=初始解,n=0,求得新的解,新的解比当前解好？,接受新的解,用新的解替换当前解;n=n+1,nN？,BS=新的解,新的解比BS好？,T=rT,T=t?,End,Start,T:温度Th:最高温度t:最低温度BS：已经找到的最好解N:某一温度下达到平衡的搜索次数,是,否,是,否,是,否,是,否,是,否,求得初始解BS=初始解,BS,初始解,温度T2000n=0,新的解,T=Th,求得初始解BS=初始解,n=0,求得新的解,新的解比当前解好？,接受新的解,用新的解替换当前解;n=n+1,nN？,BS=新的解,新的解比BS好？,T=rT,T=t?,End,Start,T:温度Th:最高温度t:最低温度BS：已经找到的最好解N:某一温度下达到平衡的搜索次数,是,否,是,否,是,否,是,否,是,否,当前解,新的解,Exp(新的解当前解)/T)=exp(-2/2000)Random0,1=0.7,T=Th,求得初始解BS=初始解,n=0,求得新的解,新的解比当前解好？,接受新的解,用新的解替换当前解;n=n+1,nN？,BS=新的解,新的解比BS好？,T=rT,T=t?,End,Start,T:温度Th:最高温度t:最低温度BS：已经找到的最好解N:某一温度下达到平衡的搜索次数,是,否,是,否,是,否,是,否,是,否,BS,当前解,温度T2000n=1,T=Th,求得初始解BS=初始解,n=0,求得新的解,新的解比当前解好？,接受新的解,用新的解替换当前解;n=n+1,nN？,BS=新的解,新的解比BS好？,T=rT,T=t?,End,Start,T:温度Th:最高温度t:最低温度BS：已经找到的最好解N:某一温度下达到平衡的搜索次数,是,否,是,否,是,否,是,否,是,否,当前解,新的解,Exp(新的解当前解)/T)=exp(-5/2000)Random0,1=0.99，拒绝新的解,T=Th,求得初始解BS=初始解,n=0,求得新的解,新的解比当前解好？,接受新的解,用新的解替换当前解;n=n+1,nN？,BS=新的解,新的解比BS好？,T=rT,T=t?,End,Start,T:温度Th:最高温度t:最低温度BS：已经找到的最好解N:某一温度下达到平衡的搜索次数,是,否,是,否,是,否,是,否,是,否,当前解,新的解,Exp(新的解当前解)/T)=exp(-1/2000)Random0,1=0.6,T=Th,求得初始解BS=初始解,n=0,求得新的解,新的解比当前解好？,接受新的解,用新的解替换当前解;n=n+1,nN？,BS=新的解,新的解比BS好？,T=rT,T=t?,End,Start,T:温度Th:最高温度t:最低温度BS：已经找到的最好解N:某一温度下达到平衡的搜索次数,是,否,是,否,是,否,是,否,是,否,BS,当前解,温度T1200n=2,T=Th,求得初始解BS=初始解,n=0,求得新的解,新的解比当前解好？,接受新的解,用新的解替换当前解;n=n+1,nN？,BS=新的解,新的解比BS好？,T=rT,T=t?,End,Start,T:温度Th:最高温度t:最低温度BS：已经找到的最好解N:某一温度下达到平衡的搜索次数,是,否,是,否,是,否,是,否,是,否,当前解,新的解,接受新的解,温度T1200n=0,T=Th,求得初始解BS=初始解,n=0,求得新的解,新的解比当前解好？,接受新的解,用新的解替换当前解;n=n+1,nm1?若是，则转第(5)步；否则，返回第(2)步；（5）将当前最优解s*和当前状态s(k)返回改进退火过程。,2.4.3一种改进的模拟退火算法,2.5模拟退火算法的实现与应用,2.5.130城市TSP问题（d*=423.741byDBFogel）,TSPBenchmark问题4194;3784;5467;2562;764;299;6858;7144;5462;8369;6460;1854;2260;8346;9138;2538;2442;5869;7171;7478;8776;1840;1340;827;6232;5835;4521;4126;4435;450,2.5模拟退火算法的实现与应用,算法流程,2.5.130城市TSP问题（d*=423.741byDBFogel）,2.5模拟退火算法的实现与应用,初始温度的计算fori=1:100route=randperm(CityNum);fval0(i)=CalDist(dislist,route);endt0=-(max(fval0)-min(fval0)/log(0.9);,2.5.130城市TSP问题（d*=423.741byDBFogel）,2.5模拟退火算法的实现与应用,状态产生函数的设计（1）互换操作，随机交换两个城市的顺序；（2）逆序操作，两个随机位置间的城市逆序；（3）插入操作，随机选择某点插入某随机位置。,2.5.130城市TSP问题（d*=423.741byDBFogel）,2,8,3,5,9,1,4,6,7,2,8,3,5,9,1,4,6,7,2,8,3,5,9,1,4,6,7,2.5模拟退火算法的实现与应用,参数设定截止温度tf=0.01;退温系数alpha=0.90;内循环次数L=200*CityNum;,2.5.130城市TSP问题（d*=423.741byDBFogel）,2.5模拟退火算法的实现与应用,运行过程,2.5.130城市TSP问题（d*=423.741byDBFogel）,2.5模拟退火算法的实现与应用,运行过程,2.5.130城市TSP问题（d*=423.741byDBFogel）,2.5模拟退火算法的实现与应用,运行过程,2.5.130城市TSP问题（d*=423.741byDBFogel）,2.5模拟退火算法的实现与应用,运行过程,2.5.130城市TSP问题（d*=423.741byDBFogel）,2.5模拟退火算法的实现与应用,运行过程,2.5.130城市TSP问题（d*=423.741byDBFogel）,2.5模拟退火算法的实现与应用,运行结果,2.5.130城市TSP问题（d*=423.741byDBFogel）,2.5模拟退火算法的实现与应用,换热器模型两级管壳式换热器组成的换热器系统，数学模型高度非线性，其目标函数通常是多峰(谷)的，具有很多局部最优解。,2.5.2模拟退火算法在管壳式换热器优化设计中的应用,2.5模拟退火算法的实现与应用,优化目标以换热器系统的总费用年值最小作为优化设计的目标。其中，f1(X)是两级换热器的初始投资，f2(X)是两级换热器年维护费(包括除垢、保养、维修等)，f3(X)是冷却水资源费以及管程压降能耗费，f4(X)是壳程压降能耗费。,2.5.2模拟退火算法在管壳式换热器优化设计中的应用,2.5模拟退火算法的实现与应用,优化目标经过分析，优化问题的独立变量共12个，分别是一级换热器煤油出口温度t2、冷却水流量G1、两个换热器的管内径d1，d2和管间距S1，S2、折流板间距B1，B2、折流板开口角1，2、单