文档介绍：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- Hill- climbingAlgorithm 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 An