模拟退火算法课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,Simulated Annealing,（模拟退火算法）,模拟退火算法的思想最早是由,Metropo,比等,(1953),提出的，,1983,年,Kirkpatrick,等将其用于组合优化。,SA,算法是基于,Mente,Calro,迭代求解策略的一种随机寻优算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。模拟退火算法在某一初温下，伴随温度参数的不断下降，结合概率突跳特性在解空间中随机寻找目标函数的全局最优解即在局部优解能概率性地跳出并最终趋于全局最优。模拟退火算法是一种通用的优化算法，目前己在工程中得到了广泛应用，诸如,VLSI,、生产调度、控制工程、机器学习、神经网络、图像处理等领域。,退火工艺,:,退火是将金属和合金加热到适当温度，保持一定时间，然后缓慢冷却的热处理工艺。退火后组织亚共析钢是铁素体加片状珠光体；共析钢或过共析钢则是粒状珠光体。总之退火组织是接近平衡状态的组织。,退火的目的,:,降低钢的硬度，提高塑性，以利于切削加工及冷变形加工。细化晶粒，消除因铸、锻、焊引起的组织缺陷，均匀钢的组织和成分，改善钢的性能或为以后的热处理作组织准备。消除钢中的内应力，以防止变形和开裂,Simulated Annealing,相似性：,金属,问题,能量状态 成本函数,温度 控制参数,完整排列的晶体结构,问题的最优解,Global optimal solution can be achieved as long as the cooling process is slow enough.,Optimization,steepest descent and local minima,f,(x,),Global minimum,Local minimum,Local minimum,Local minimum,要从局部最优逃出，必须上行（,up-step,）,SA,的上行机制：,（当前解）,（下一个解）,T,为温度，即,SA,的控制参数,SA,接受相邻解的标准,令,X,为当前解,X,新的解（相邻解）,C,(,x,)(,C,(,x,)be the energy state(cost)of,x,(,x,),概率,P,accept,=,exp,(,C,(,x,)-,C,(,x,)/T,N=Random,(0,1),无条件接受相邻解，如果：,C(,x,)=C(,x,),即相邻解比当前解差,当,N,P,accept,时，接受相邻解,参数设置,T,初始温度,t,冷却温度,冷却过程的设定（,The cooling schedule,）,L,每一特定温度下的搜索次数：,退火过程设定,Cooling Schedule:,N,温度,T,的主要作用：,决定接受差的解的概率,初始温度的设定,：由可忍受的解差的程度和接受的概率决定，比如以,0.8,的概率接受比当前解值大,100,，初始温度应为多少？,一般温度设定为,5001000,较为合适。需要运行程序多试。,退火过程设定,N,温度,T,的降低过程：,每次减少固定的值：,T=T-Td,每次按固定比例减少：,T=T*r,，此方法比较常用,每个特定温度下的搜索次数,L,：根据计算耗时来确定。,搜索的收敛：温度降低到设定的最低温度，如,0.5,度。,Algorithm,Initialize initial solution,x,highest temperature,T,h,and coolest temperature,t,T=,T,h,When the temperature is higher than,t,While not in equilibrium,Search for the new solution,X,Accept or reject,X,according to Metropolis Criterion,End,Decrease the temperature,T,End,T=,T,h,求得初始解,BS=,初始解,n=0,求得新的解,新的解比,当前解好？,接受新的解,用新的解替换,当前解,;n=n+1,nN,？,BS=,新的解,新的解比,BS,好？,T=,rT,T=t?,End,Start,T:,温度,T,h,:,最高温度,t:,最低温度,BS,：已经找到的最好解,N:,某一温度下达到平衡的搜索次数,是,否,是,否,是,否,是,否,是,否,Example,Traveling Salesman Problem(TSP),Given 6 cities and the traveling cost between any two cities,A salesman need to start from city 1 and travel all other cities then back to city 1,Minimize the total traveling cost,TSP,算例,City to city,1,2,3,4,5,6,1,12,4,7,9,10,2,11,20,13,8,3,6,17,13,4,6,9,5,15,6,SA parameter setting,T,h,=2000,t=10,r=0.6,N=2,生成新的解：随机选择两个位置，交换其表示的城市,T=,T,h,求得初始解,BS=,初始解,n=0,求得新的解,新的解比,当前解好？,接受新的解,用新的解替换,当前解,;n=n+1,nN,？,BS=,新的解,新的解比,BS,好？,T=,rT,T=t?,End,Start,T:,温度,T,h,:,最高温度,t:,最低温度,BS,：已经找到的最好解,N:,某一温度下达到平衡的搜索次数,是,否,是,否,是,否,是,否,是,否,求得初始解,BS=,初始解,Sequence,The length of the route,132456,28,BS,Sequence,The length of the route,132456,28,初始解,温度,T,2000 n=0,Sequence,The length of the route,123456,30,新的解,T=,T,h,求得初始解,BS=,初始解,n=0,求得新的解,新的解比,当前解好？,接受新的解,用新的解替换,当前解,;n=n+1,nN,？,BS=,新的解,新的解比,BS,好？,T=,rT,T=t?,End,Start,T:,温度,T,h,:,最高温度,t:,最低温度,BS,：已经找到的最好解,N:,某一温度下达到平衡的搜索次数,是,否,是,否,是,否,是,否,是,否,Sequence,The length of the route,132456,28,当前解,Sequence,The length of the route,123456,30,新的解,Exp(,新的解当前解,)/T)=exp(-2/2000),Random0,1=0.7,T=,T,h,求得初始解,BS=,初始解,n=0,求得新的解,新的解比,当前解好？,接受新的解,用新的解替换,当前解,;n=n+1,nN,？,BS=,新的解,新的解比,BS,好？,T=,rT,T=t?,End,Start,T:,温度,T,h,:,最高温度,t:,最低温度,BS,：已经找到的最好解,N:,某一温度下达到平衡的搜索次数,是,否,是,否,是,否,是,否,是,否,Sequence,The length of the route,123456,30,BS,Sequence,The length of the route,132456,28,当前解,温度,T,2000 n=1,T=,T,h,求得初始解,BS=,初始解,n=0,求得新的解,新的解比,当前解好？,接受新的解,用新的解替换,当前解,;n=n+1,nN,？,BS=,新的解,新的解比,BS,好？,T=,rT,T=t?,End,Start,T:,温度,T,h,:,最高温度,t:,最低温度,BS,：已经找到的最好解,N:,某一温度下达到平衡的搜索次数,是,否,是,否,是,否,是,否,是,否,Sequence,The length of the route,123456,30,当前解,Sequence,The length of the route,123546,36,新的解,Exp(,新的解当前解,)/T)=exp(-5/2000),Random0,1=0.99,，拒绝新的解,T=,T,h,求得初始解,BS=,初始解,n=0,求得新的解,新的解比,当前解好？,接受新的解,用新的解替换,当前解,;n=n+1,nN,？,BS=,新的解,新的解比,BS,好？,T=,rT,T=t?,End,Start,T:,温度,T,h,:,最高温度,t:,最低温度,BS,：已经找到的最好解,N:,某一温度下达到平衡的搜索次数,是,否,是,否,是,否,是,否,是,否,Sequence,The length of the route,123456,30,当前解,Sequence,The length of the route,123465,31,新的解,Exp(,新的解当前解,)/T)=exp(-1/2000),Random0,1=0.6,T=,T,h,求得初始解,BS=,初始解,n=0,求得新的解,新的解比,当前解好？,接受新的解,用新的解替换,当前解,;n=n+1,nN,？,BS=,新的解,新的解比,BS,好？,T=,rT,T=t?,End,Start,T:,温度,T,h,:,最高温度,t:,最低温度,BS,：已经找到的最好解,N:,某一温度下达到平衡的搜索次数,是,否,是,否,是,否,是,否,是,否,Sequence,The length of the route,123456,30,BS,Sequence,The length of the route,132456,28,当前解,温度,T,1200 n=2,T=,T,h,求得初始解,BS=,初始解,n=0,求得新的解,新的解比,当前解好？,接受新的解,用新的解替换,当前解,;n=n+1,nN,？,BS=,新的解,新的解比,BS,好？,T=,rT,T=t?,End,Start,T:,温度,T,h,:,最高温度,t:,最低温度,BS,：已经找到的最好解,N:,某一温度下达到平衡的搜索次数,是,否,是,否,是,否,是,否,是,否,Sequence,The length of the route,123456,30,当前解,Sequence,The length of the route,213456,27,新的解,接受新的解,温度,T,1200 n=0,T=,T,h,求得初始解,BS=,初始解,n=0,求得新的解,新的解比,当前解好？,接受新的解,用新的解替换,当前解,;n=n+1,nN,？,BS=,新的解,新的解比,BS,好？,T=,rT,Tcost=189,Generate neighbor:obtain sequence,(1,2,4,3,6,5)-cost=180,Replace current sequence by(1,2,4,3,6,5),Step n+1:,visiting sequence,(1,2,4,3,6,5)-cost=180,Generate neighbor:obtain sequence,(1,2,4,3,5,6)-cost=190,Temperature=99,Probability:exp(180-181)/99)=0.904,Random()=0.6-accept neighbor,Replace current sequence by(1,2,4,3,5,6),Step,n+F,:,Temperature=,Temperature,*0.9,Control Parameters,Definition of equilibrium,Cannot yield any significant improvement after certain number of loops,A constant number of loops,Annealing schedule(i.e.How to reduce the temperature),A constant value,T=T-T,d,A constant scale factor,T=T*R,d,A scale factor usually can achieve better performance,Control Parameters,Temperature determination,Artificial,without physical significant,Initial temperature:,80-90%acceptance rate,For example:the inferior solution is accepted by the probability of 90%only when the difference of current solution and the neighborhood solution is within 100.,Control Parameters,Temperature determination,Artificial,without physical significant,Final temperature,A constant value,i.e.,based on the total number of solutions searched,No improvement during the entire Metropolis loop,Acceptance rate falling below a given(small)value,Problem specific and may need to be tuned,