《模拟退火算法课件》由会员分享，可在线阅读，更多相关《模拟退火算法课件（39页珍藏版）》请在金锄头文库上搜索。
1、Simulated Annealing （模拟退火算法）,模拟退火算法的思想最早是由Metropo比等(1953)提出的，1983年Kirkpatrick等将其用于组合优化。SA算法是基于Mente Calro迭代求解策略的一种随机寻优算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。模拟退火算法在某一初温下，伴随温度参数的不断下降，结合概率突跳特性在解空间中随机寻找目标函数的全局最优解即在局部优解能概率性地跳出并最终趋于全局最优。模拟退火算法是一种通用的优化算法，目前己在工程中得到了广泛应用，诸如VLSI、生产调度、控制工程、机器学习、神经网络、图像处理等领域。,退
2、火工艺: 退火是将金属和合金加热到适当温度，保持一定时间，然后缓慢冷却的热处理工艺。退火后组织亚共析钢是铁素体加片状珠光体；共析钢或过共析钢则是粒状珠光体。总之退火组织是接近平衡状态的组织。 退火的目的: 降低钢的硬度，提高塑性，以利于切削加工及冷变形加工。细化晶粒，消除因铸、锻、焊引起的组织缺陷，均匀钢的组织和成分，改善钢的性能或为以后的热处理作组织准备。消除钢中的内应力，以防止变形和开裂,Simulated Annealing,相似性： 金属 问题 能量状态 成本函数 温度 控制参数 完整排列的晶体结构 问题的最优解,Global optimal solution can be achie
3、ved 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) 概率
4、Paccept = exp (C(x)-C(x)/ T N=Random(0,1) 无条件接受相邻解，如果： C(x) = C(x),即相邻解比当前解差 当 N Paccept时，接受相邻解,参数设置,T 初始温度 t 冷却温度 冷却过程的设定（The cooling schedule） L 每一特定温度下的搜索次数：,退火过程设定,Cooling Schedule:,温度T的主要作用：决定接受差的解的概率 初始温度的设定：由可忍受的解差的程度和接受的概率决定，比如以0.8的概率接受比当前解值大100，初始温度应为多少？ 一般温度设定为5001000较为合适。需要运行程序多试。,退火过程设定,
5、温度T的降低过程： 每次减少固定的值：T = T - Td 每次按固定比例减少：T= T * r，此方法比较常用 每个特定温度下的搜索次数L：根据计算耗时来确定。 搜索的收敛：温度降低到设定的最低温度，如0.5度。,Algorithm,Initialize initial solution x , highest temperature Th, and coolest temperature t T= Th When the temperature is higher than t While not in equilibrium Search for the new solution X A
6、ccept or reject X according to Metropolis Criterion End Decrease the temperature T End,T=Th,求得初始解 BS=初始解,n=0,求得新的解,新的解比 当前解好？,接受新的解,用新的解替换 当前解; n=n+1,nN？,BS=新的解,新的解比BS好？,T=rT,T=t?,End,Start,T: 温度 Th:最高温度 t: 最低温度 BS：已经找到的最好解 N:某一温度下达到平衡的搜索次数,是,否,是,否,是,否,是,否,是,否,Example,Traveling Salesman Problem (TSP
7、) 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算例,SA parameter setting,Th=2000 t=10 r=0.6 N=2 生成新的解：随机选择两个位置，交换其表示的城市,T=Th,求得初始解 BS=初始解,n=0,求得新的解,新的解比 当前解好？,接受新的解
8、,用新的解替换 当前解; n=n+1,nN？,BS=新的解,新的解比BS好？,T=rT,T=t?,End,Start,T: 温度 Th:最高温度 t: 最低温度 BS：已经找到的最好解 N:某一温度下达到平衡的搜索次数,是,否,是,否,是,否,是,否,是,否,求得初始解 BS=初始解,BS,初始解,温度T2000 n=0,新的解,T=Th,求得初始解 BS=初始解,n=0,求得新的解,新的解比 当前解好？,接受新的解,用新的解替换 当前解; n=n+1,nN？,BS=新的解,新的解比BS好？,T=rT,T=t?,End,Start,T: 温度 Th:最高温度 t: 最低温度 BS：已经找到的最
9、好解 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,当前解,温度T2000 n=1,T=Th,求得初始解 BS=初始解
10、,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=r
11、T,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:某一温度下达到平衡的搜索次数,是,否,是,否,
12、是,否,是,否,是,否,BS,当前解,温度T1200 n=2,T=Th,求得初始解 BS=初始解,n=0,求得新的解,新的解比 当前解好？,接受新的解,用新的解替换 当前解; n=n+1,nN？,BS=新的解,新的解比BS好？,T=rT,T=t?,End,Start,T: 温度 Th:最高温度 t: 最低温度 BS：已经找到的最好解 N:某一温度下达到平衡的搜索次数,是,否,是,否,是,否,是,否,是,否,当前解,新的解,接受新的解,温度T1200 n=0,T=Th,求得初始解 BS=初始解,n=0,求得新的解,新的解比 当前解好？,接受新的解,用新的解替换 当前解; n=n+1,nN？,BS
13、=新的解,新的解比BS好？,T=rT,T=t?,End,Start,T: 温度 Th:最高温度 t: 最低温度 BS：已经找到的最好解 N:某一温度下达到平衡的搜索次数,是,否,是,否,是,否,是,否,是,否,BS,当前解,温度T1200 n=1,Example,Solution representation An integer list, i.e., (1,4,2,3,6,5) Search mechanism Swap any two integers (except for the first one) (1,4,2,3,6,5) (1,4,3,2,6,5) Cost function
14、,Example,Step n: visiting sequence (1,4,2,3,6,5) -cost = 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 Proba
15、bility: 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 - Td A constant scale factor, T= T * Rd A scale factor usually can achieve better performance,
