文档介绍：Simulated Annealing Simulated Annealing 1 1 Simulated Annealing Simulated Annealing (模拟退火法) (模拟退火法) 报告人:陈世明 Simulated Annealing Simulated Annealing 2 2 大纲大纲简介简介攀登算法模拟退火法模拟退火法 . Hill Climbing . Hill Climbing 仿真退火法的检测标准与流程仿真退火法的检测标准与流程模拟退火法的考虑因素其他的问题其他的问题提高效能与算法的修正提高效能与算法的修正结论结论 Simulated Annealing Simulated Annealing 3 3 简介简介仿真退火法是仿真冷却晶体的过程仿真退火法是仿真冷却晶体的过程。。最早是由最早是由 Metropolis Metropolis 、、Rosenbluth Rosenbluth 等人等人在在1953 1953 年提出年提出。。 1983 1983 年, 年, Kirkpatrick Kirkpatrick 等人将其运用在求优化的问等人将其运用在求优化的问题题、定位、定位及图分割等问题上及图分割等问题上, ,它是蒙地卡罗算法的推广它是蒙地卡罗算法的推广。。 Simulated Annealing Simulated Annealing 4 4 攀登算法( Hill Climbing) Hill Climbing) 攀登算法( 攀登算法( Hill-climbingAlgorithm Hill-climbingAlgorithm )是一种迭代增进的)是一种迭代增进的算法,它利用单一解在解空间作搜寻,并在每一次迭代中, 算法,它利用单一解在解空间作搜寻,并在每一次迭代中, 在目前解的邻近解空间选择出一个邻近解。在目前解的邻近解空间选择出一个邻近解。当邻近解的目标函數值比目前解的目标函數值來的佳时, 当邻近解的目标函數值比目前解的目标函數值來的佳时, 就以邻近解取代目前解;否则,就重新在目前解的邻近解就以邻近解取代目前解;否则,就重新在目前解的邻近解空间选择一个邻近解。空间选择一个邻近解。 Simulated Annealing Simulated Annealing 5 5 模拟退火法模拟退火法 . Hill Climbing . Hill Climbing HillClimbing HillClimbing 是挑选邻近点中最好的点,但这样会有局部是挑选邻近点中最好的点,但这样会有局部最大值的问题。最大值的问题。仿真算法是随机数找寻邻近的点。仿真算法是随机数找寻邻近的点。––若找到的点比立足点好,则取之。若找到的点比立足点好,则取之。––否则依照机率决定是否取之。否则依照机率决定是否取之。 Simulated Annealing Simulated Annealing 6 6 模拟退火法的流程(1/2) 需先设定一些參數,。接着随机产生一个初始的目前解, 并计算他的目标函數值。以目前解为中心对解空间做随机扰动,产生一个扰动解, 其目标函數值为。若接受,则以该扰动解取代目前解作为该次迭代的解。 X)'(Xf 'X )(Xf Simulated Annealing Simulated Annealing 7 7 模拟退火法的检测标准模拟退火法的检测标准根据热力学定律,在温度为根据热力学定律,在温度为 t t的情况下,能量差所表现的的情况下,能量差所表现的机率如下: 机率如下: P( P(ΔΔE)=exp(- E)=exp(- ΔΔE / kt) E / kt) ––k k是是Boltzmann Boltzmann ’’s Constant s Constant 转换到模拟退火法,则变成转换到模拟退火法,则变成 P=exp(-c / t)>r P=exp(-c / t)>r ––c c是评估函数的差是评估函数的差––r r是是0~1 0~1 之间的随机数之间的随机数 Simulated Annealing Simulated Annealing 8 8 模拟退火法的流程(2/2) 假设所求解的问题是目标函數最小化问题, 若,则透过机率函數接受为新解。接着判断是否满足降温条件,若是,则透过冷却机制降温, ,。反之,维持目前温度。之后判断是否达到终止条件, 例如达到设定的迭代次數或是連续几次迭代目前解都不再改变时。)'(Xf )()'(xfXff??? 0??fTT???]1,0[?? Simulated Annealing Simulated Annealing 9 9 模拟退火法的流程图初使化设定随机产生一个初始解扰动产生一个新解是否接受?修改目前解降温缩减温度是否达到中止条件?