模拟退火算法课件

SimulatedAnnealing

（模拟退火算法）模拟退火算法的思想最早是由Metropo比等(1953)提出的，1983年Kirkpatrick等将其用于组合优化。SA算法是基于MenteCalro迭代求解策略的一种随机寻优算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。模拟退火算法在某一初温下，伴随温度参数的不断下降，结合概率突跳特性在解空间中随机寻找目标函数的全局最优解．即在局部优解能概率性地跳出并最终趋于全局最优。模拟退火算法是一种通用的优化算法，目前己在工程中得到了广泛应用，诸如VLSI、生产调度、控制工程、机器学习、神经网络、图像处理等领域。

退火工艺:退火是将金属和合金加热到适当温度，保持一定时间，然后缓慢冷却的热处理工艺。退火后组织亚共析钢是铁素体加片状珠光体；共析钢或过共析钢则是粒状珠光体。总之退火组织是接近平衡状态的组织。退火的目的:①降低钢的硬度，提高塑性，以利于切削加工及冷变形加工。②细化晶粒，消除因铸、锻、焊引起的组织缺陷，均匀钢的组织和成分，改善钢的性能或为以后的热处理作组织准备。③消除钢中的内应力，以防止变形和开裂SimulatedAnnealing相似性：金属问题能量状态成本函数温度控制参数完整排列的晶体结构问题的最优解Globaloptimalsolutioncanbeachievedaslongasthecoolingprocessisslowenough.Optimization,steepestdescentandlocalminimaf(x)GlobalminimumLocalminimumLocalminimumLocalminimum要从局部最优逃出，必须上行（up-step）SA的上行机制：△＝（当前解）—（下一个解）T为温度，即SA的控制参数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),即相邻解比当前解差当N<Paccept时，接受相邻解参数设置T初始温度t冷却温度冷却过程的设定（Thecoolingschedule）L每一特定温度下的搜索次数：退火过程设定CoolingSchedule:N温度T的主要作用：决定接受差的解的概率初始温度的设定：由可忍受的解差的程度和接受的概率决定，比如以0.8的概率接受比当前解值大100，初始温度应为多少？一般温度设定为500——1000较为合适。需要运行程序多试。退火过程设定N温度T的降低过程： 每次减少固定的值：T’=T-Td

每次按固定比例减少：T’=T*r，此方法比较常用每个特定温度下的搜索次数L：根据计算耗时来确定。搜索的收敛：温度降低到设定的最低温度，如0.5度。AlgorithmInitializeinitialsolutionx,highesttemperatureTh,andcoolesttemperaturetT=ThWhenthetemperatureishigherthant

Whilenotinequilibrium SearchforthenewsolutionX’AcceptorrejectX’accordingtoMetropolisCriterionEndDecreasethetemperatureTEndT=Th求得初始解BS=初始解n=0求得新的解新的解比当前解好？接受新的解用新的解替换当前解;n=n+1n<N？BS=新的解新的解比BS好？T=rTT<=t?EndStartT:温度Th:最高温度t:最低温度BS：已经找到的最好解N:某一温度下达到平衡的搜索次数是否是否是否是否是否ExampleTravelingSalesmanProblem(TSP)Given6citiesandthetravelingcostbetweenanytwocitiesAsalesmanneedtostartfromcity1andtravelallothercitiesthenbacktocity1MinimizethetotaltravelingcostTSP算例Citytocity12345611247910211201383617134695156SAparametersettingTh=2000t=10r=0.6N=2生成新的解：随机选择两个位置，交换其表示的城市T=Th求得初始解BS=初始解n=0求得新的解新的解比当前解好？接受新的解用新的解替换当前解;n=n+1n<N？BS=新的解新的解比BS好？T=rTT<=t?EndStartT:温度Th:最高温度t:最低温度BS：已经找到的最好解N:某一温度下达到平衡的搜索次数是否是否是否是否是否求得初始解BS=初始解

SequenceThelengthoftheroute13245628BSSequenceThelengthoftheroute13245628初始解温度T＝2000n=0SequenceThelengthoftheroute12345630新的解T=Th求得初始解BS=初始解n=0求得新的解新的解比当前解好？接受新的解用新的解替换当前解;n=n+1n<N？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+1n<N？BS=新的解新的解比BS好？T=rTT<=t?EndStartT:温度Th:最高温度t:最低温度BS：已经找到的最好解N:某一温度下达到平衡的搜索次数是否是否是否是否是否SequenceThelengthoftheroute12345630BSSequenceThelengthoftheroute13245628当前解温度T＝2000n=1T=Th求得初始解BS=初始解n=0求得新的解新的解比当前解好？接受新的解用新的解替换当前解;n=n+1n<N？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+1n<N？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+1n<N？BS=新的解新的解比BS好？T=rTT<=t?EndStartT:温度Th:最高温度t:最低温度BS：已经找到的最好解N:某一温度下达到平衡的搜索次数是否是否是否是否是否SequenceThelengthoftheroute12345630BSSequenceThelengthoftheroute13245628当前解温度T＝1200n=2T=Th求得初始解BS=初始解n=0求得新的解新的解比当前解好？接受新的解用新的解替换当前解;n=n+1n<N？BS=新的解新的解比BS好？T=rTT<=t?EndStartT:温度Th:最高温度t:最低温度BS：已经找到的最好解N:某一温度下达到平衡的搜索次数是否是否是否是否是否SequenceThelengthoftheroute12345630当前解SequenceThelengthoftheroute21345627新的解接受新的解温度T＝1200n=0T=Th求得初始解BS=初始解n=0求得新的解新的解比当前解好？接受新的解用新的解替换当前解;n=n+1n<N？BS=新的解新的解比BS好？T=rTT<=t?EndStartT:温度Th:最高温度t:最低温度BS：已经找到的最好解N:某一温度下达到平衡的搜索次数是否是否是否是否是否SequenceThelengthoftheroute21345627BSSequenceThelengthoftheroute21345627当前解温度T＝1200n=1ExampleSolutionrepresentationAnintegerlist,i.e.,(1,4,2,3,6,5)SearchmechanismSwapanytwointegers(exceptforthefirstone)(1,4,2,3,6,5)(1,4,3,2,6,5)CostfunctionExampleStepn:visitingsequence(1,4,2,3,6,5)->cost=189Generateneighbor:obtainsequence(1,2,4,3,6,5)->cost=180Replacecurrentsequenceby(1,2,4,3,6,5)Stepn+1:visitingsequence(1,2,4,3,6,5)->cost=180Generateneighbor:obtainsequence(1,2,4,3,5,6)->cost=190Temperature=99Probability:exp((180-181)/99)=0.904Random()=0.6->acceptneighborReplacecurrentsequenceby(1,2,4,3,5,6)…Stepn+F:Temperature=Temperature*0.9ControlParametersDefinitionofequilibriumCannotyieldanysignificantimprovementaftercertainnumberofloopsAconstantnumberofloopsAnnealingschedule(i.e.Howtoreducethetemperature)Aconstantvalue,T’=T-TdAconstantscalefactor,T’=T*RdAscalefactorusuallycanachiev