模拟退火算法PPT

《模拟退火算法PPT》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、SimulatedAnnealing1SimulatedAnnealing（模拟退火法）报告人:陈世明SimulatedAnnealing2大纲简介攀登算法模拟退火法v.s.HillClimbing仿真退火法的检测标准与流程模拟退火法的考虑因素其他的问题提高效能与算法的修正结论SimulatedAnnealing3简介仿真退火法是仿真冷却晶体的过程。最早是由Metropolis、Rosenbluth等人在1953年提出。1983年，Kirkpatrick等人将其运用在求优化的问题、定位及图分割等问题上，它是蒙地卡罗算法的推广。Simula

2、tedAnnealing4攀登算法(HillClimbing)攀登算法（Hill-climbingAlgorithm）是一种迭代增进的算法，它利用单一解在解空间作搜寻，并在每一次迭代中，在目前解的邻近解空间选择出一个邻近解。当邻近解的目标函數值比目前解的目标函數值來的佳时，就以邻近解取代目前解；否则，就重新在目前解的邻近解空间选择一个邻近解。SimulatedAnnealing5模拟退火法v.s.HillClimbingHillClimbing是挑选邻近点中最好的点，但这样会有局部最大值的问题。仿真算法是随机数找寻邻近的点。若找到的点比立

3、足点好，则取之。否则依照机率决定是否取之。SimulatedAnnealing6模拟退火法的流程(1/2)需先设定一些參數，。接着随机产生一个初始的目前解，并计算他的目标函數值。以目前解为中心对解空间做随机扰动，产生一个扰动解，其目标函數值为。若接受，则以该扰动解取代目前解作为该次迭代的解。SimulatedAnnealing7模拟退火法的检测标准根据热力学定律，在温度为t的情况下，能量差所表现的机率如下：P(ΔE)=exp(-ΔE/kt)k是Boltzmann’sConstant转换到模拟退火法，则变成P=exp(-c/t)>rc是评估

4、函数的差r是0~1之间的随机数SimulatedAnnealing8模拟退火法的流程(2/2)假设所求解的问题是目标函數最小化问题，若，则透过机率函數接受为新解。接着判断是否满足降温条件，若是，则透过冷却机制降温，，。反之，维持目前温度。之后判断是否达到终止条件，例如达到设定的迭代次數或是連续几次迭代目前解都不再改变时。SimulatedAnnealing9模拟退火法的流程图初使化设定随机产生一个初始解扰动产生一个新解是否接受?修改目前解降温缩减温度是否达到中止条件?最佳解NoYesYesYesNoNoSimulatedAnnealing

5、10冷却排程(1/4)初始温度（StartingTemperature）温度要够高才能移动到任何的状态。温度不能太高，否则会导致在一段时间内皆用随机数在凑解答。如果可以知道检测函数的最大值就可以找到最好的初始温度。快速提高温度，然后又快速降温，直到有60%的最差解被接受。快速提高温度，但慢慢降温，并定出适当比例最差解的接受度。–––SimulatedAnnealing11冷却排程(2/4)最终温度（FinalTemperature）通常是零，但会耗掉许多模拟时间。温度趋近于零，其周遭状态几乎是一样的。所以寻找一个低到可接受的温度。Simu

6、latedAnnealing12冷却排程(3/4)温度减少（TemperatureDecrement）每次降低温度的差距以及在同一温度反复寻找最适解会导致指数般成长的搜寻空间。1.以线性降温来说Temp=Temp-x2.以几何观念来看Temp=Temp*y(y约0.8~0.99为佳)SimulatedAnnealing13冷却排程（4/4）反复次数（IterationsateachTemperature）一般会定一个常数。Lundy认为只要反复一次，但每次降低的温度差距必须非常小。Temp=Temp/(1+a*Temp)a是非常小的值低温

7、需要较多反复次数以避免找到局部最大值，但高温则可减少次数。SimulatedAnnealing14模拟退火法的流程图初使化设定随机产生一个初始解扰动产生一个新解是否接受?修改目前解降温缩减温度是否达到中止条件?最佳解NoYesYesYesNoNoSimulatedAnnealing15扰动方式(1/2)模拟退火法以扰动的机制來产生一个解，我们称此解为扰动解，在以机率函數判断是否接受此扰动解为此次迭代的新解。若不被接受，就再以扰动重新产生一个扰动解，并以机率函數重新判断。每代重复以上的步骤，直到接受为此次迭代的新解为止。SimulatedA

8、nnealing16扰动方式(2/2)扰动的作法就是以目前解为中心，对部分或整个解空间随机取样一个解。SimulatedAnnealing17模拟退火法的流程图初使化设定随机产生一个初始解扰动