模拟退火算法PPT.ppt

《模拟退火算法PPT.ppt》由会员分享，可在线阅读，更多相关《模拟退火算法PPT.ppt（30页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Simulated AnnealingSimulated Annealing1 1Simulated Annealing（模拟退火法）报告人:陈世明Simulated AnnealingSimulated Annealing2 2大纲简介攀登算法模拟退火法v.s.Hill Climbing仿真退火法的检测标准与程模拟退火法的考虑因素其他的问题提高效能与算法的修正结论Simulated AnnealingSimulated Annealing3 3简介仿真退火法是仿真却晶体的过程仿真退火法是仿真却晶体的过程。最早是由最早是由MetropolisMetropolis、RosenbluthRosen

2、bluth等人等人在在19531953年提出年提出。19831983年，年，KirkpatrickKirkpatrick等人将其运用在求优化的问等人将其运用在求优化的问题题、定位、定位及图分割等问题上及图分割等问题上，它是蒙地卡罗算法的推广它是蒙地卡罗算法的推广。Simulated AnnealingSimulated Annealing4 4攀登算法(Hill Climbing)Hill Climbing)攀登算法（攀登算法（Hill-climbingAlgorithmHill-climbingAlgorithm）是一种迭代增进的）是一种迭代增进的算法，它用单一解在解空间作搜寻，并在每一次迭

3、代中，算法，它用单一解在解空间作搜寻，并在每一次迭代中，在目前解的邻近解空间选择出一个邻近解。在目前解的邻近解空间选择出一个邻近解。当邻近解的目标函值比目前解的目标函值的佳时，当邻近解的目标函值比目前解的目标函值的佳时，就以邻近解取代目前解；否则，就重新在目前解的邻近解就以邻近解取代目前解；否则，就重新在目前解的邻近解空间选择一个邻近解。空间选择一个邻近解。Simulated AnnealingSimulated Annealing5 5模拟退火法v.s.Hill ClimbingHillClimbingHillClimbing是挑选邻近点中最好的点，但这样会有局部是挑选邻近点中最好的点，但这

4、样会有局部最大值的问题。最大值的问题。仿真算法是随机数找寻邻近的点。仿真算法是随机数找寻邻近的点。找到的点比立足点好，则取之。找到的点比立足点好，则取之。否则依照机决定是否取之。否则依照机决定是否取之。Simulated AnnealingSimulated Annealing6 6模拟退火法的程(1/2)需先设定一些，。接着随机产生一个初始的目前解 ，并计算他的目标函值 。以目前解为中心对解空间做随机扰动，产生一个扰动解 ，其目标函值为。接受，则以该扰动解取代目前解作为该次迭代的解。Simulated AnnealingSimulated Annealing7 7模拟退火法的检测标准根据热力

5、学定律，在温为根据热力学定律，在温为t t的情况下，能量差所表现的的情况下，能量差所表现的机如下：机如下：P(E)=exp(-E/kt)P(E)=exp(-E/kt)k k是是BoltzmannBoltzmanns Constants Constant转换到模拟退火法，则变成转换到模拟退火法，则变成P=exp(-c/t)rP=exp(-c/t)rc c是评估函数的差是评估函数的差r r是是0101之间的随机数之间的随机数Simulated AnnealingSimulated Annealing8 8模拟退火法的程(2/2)假设所求解的问题是目标函最小化问题 ，则透过机函接受 为新解。接着判断

6、是否满足温条件，是，则透过却机制温，。反之，维持目前温。之后判断是否达到终止条件，如达到设定的迭代次或是续几次迭代目前解再改变时。Simulated AnnealingSimulated Annealing9 9模拟退火法的程图初使化设定随机产生一个初始解扰动产生一个新解是否接受?修改目前解降温缩减温度 是否达到中止条件?最佳解NoYesYesYesNoNoSimulated AnnealingSimulated Annealing1010却排程(1/4)初始温（初始温（Starting TemperatureStarting Temperature）温要够高才能移动到任何的状态温要够高才能移

7、动到任何的状态。温能太高，否则会导致在一段时间内皆用随机数温能太高，否则会导致在一段时间内皆用随机数在凑解答在凑解答。如果可以知道检测函数的最大值就可以找到最好的初如果可以知道检测函数的最大值就可以找到最好的初始温始温。快速提高温，然后又快速温，直到有快速提高温，然后又快速温，直到有60%60%的最差的最差解被接受解被接受。快速提高温，但慢慢温，并定出适当比最差解快速提高温，但慢慢温，并定出适当比最差解的接受的接受。Simulated AnnealingSimulated Annealing1111却排程(2/4)最终温（最终温（Final TemperatureFinal Temperatu

8、re）通常是零，但会耗掉许多模拟时间通常是零，但会耗掉许多模拟时间。温趋近于零，其周遭状态几乎是一样的温趋近于零，其周遭状态几乎是一样的。所以寻找一个低到可接受的温所以寻找一个低到可接受的温。Simulated AnnealingSimulated Annealing1212却排程(3/4)温减少（温减少（Temperature DecrementTemperature Decrement）每次低温的差距以及在同一温反复寻找最适解每次低温的差距以及在同一温反复寻找最适解会导致指数般成长的搜寻空间会导致指数般成长的搜寻空间。1.1.以线性温来说以线性温来说Temp=Temp-xTemp=Temp

9、-x 2.2.以几何观念来看以几何观念来看Temp=Temp*yTemp=Temp*y(y(y约约0.80.990.80.99为佳为佳)Simulated AnnealingSimulated Annealing1313却排程（4/4）反复次数（反复次数（Iterations at each TemperatureIterations at each Temperature）一般会定一个常数一般会定一个常数。LundyLundy认为只要反复一次，但每次低的温差距必须认为只要反复一次，但每次低的温差距必须非常小非常小。Temp=Temp/(1+a*Temp)Temp=Temp/(1+a*Temp

10、)a a是非常小的值是非常小的值 低温需要较多反复次数以避免找到局部最大值，但高低温需要较多反复次数以避免找到局部最大值，但高温则可减少次数温则可减少次数。Simulated AnnealingSimulated Annealing1414模拟退火法的程图初使化设定随机产生一个初始解扰动产生一个新解是否接受?修改目前解降温缩减温度 是否达到中止条件?最佳解NoYesYesYesNoNoSimulated AnnealingSimulated Annealing1515扰动方式(1/2)模拟退火法以扰动的机制产生一个解，我们称此解为扰动解，在以机函判断是否接受此扰动解为此次迭代的新解。被接受，就

11、再以扰动重新产生一个扰动解，并以机函重新判断。每代重复以上的步骤，直到接受为此次迭代的新解为止。Simulated AnnealingSimulated Annealing1616扰动方式(2/2)扰动的作法就是以目前解为中心，对部分或整个解空间随机取样一个解。Simulated AnnealingSimulated Annealing1717模拟退火法的程图初使化设定随机产生一个初始解扰动产生一个新解是否接受?修改目前解降温缩减温度 是否达到中止条件?最佳解NoYesYesYesNoNoSimulated AnnealingSimulated Annealing1818机函(1/3)模拟退火

12、法用机函有机的接受较差的扰动解为新解，使其避免传统梯搜寻法（GradientSearch）往往陷入区域解的缺点，而使模拟退火法有机会跳脱区域解，往全局最佳解收敛。Simulated AnnealingSimulated Annealing1919机函(2/3)一般的机函方程式如下:为目前温。当 ，；当会是之后随机产生一个介于0到1间的一个小于1大於0的值。随机值r与 比較，则接收扰动解；反之，则接受。Simulated AnnealingSimulated Annealing2020机函(3/3)当当 越高或越高或 越小时，则越小时，则 越大越大，相对的扰动解被接受成新解的机越高。因此因此会随

13、着迭代次的增加而逐渐下，所以较差的扰动解被接受成新解的机会也随着 的下而越越小。所以当迭代到最后因为温 已到达低点，这时系统只会接受较佳的扰动解为新解。而扰动解 小于目前解 则一定接受为新解，但是 则接受为新解的机随着 的变大而越小。Simulated AnnealingSimulated Annealing2121模拟退火法的程图初使化设定随机产生一个初始解扰动产生一个新解是否接受?修改目前解降温缩减温度 是否达到中止条件?最佳解NoYesYesYesNoNoSimulated AnnealingSimulated Annealing2222其他的问题(1/4)价值函数（价值函数（Cost

14、FunctionCost Function）用来评估解的质量用来评估解的质量。Delta EvaluationDelta Evaluation求某解与其邻近点的价值求某解与其邻近点的价值。Partial EvaluationPartial Evaluation需额外产生的计算结果就可以判断出来解的价值需额外产生的计算结果就可以判断出来解的价值。Simulated AnnealingSimulated Annealing2323其他的问题（2/4）价值函数（价值函数（Cost FunctionCost Function）Hard ConstraintsHard Constraints在违背合适解

15、的条件下，所提出的强制规定在违背合适解的条件下，所提出的强制规定。Soft ConstraintsSoft Constraints无论这种解是否违背条件，算是合适解无论这种解是否违背条件，算是合适解。HardConstraintsHardConstraints会给一个很大的会给一个很大的weightweight SoftConstraintsSoftConstraints则是情况给予同的则是情况给予同的weightweightSimulated AnnealingSimulated Annealing2424其他的问题（3/4）邻近点的结构（邻近点的结构（Neighborhood Struct

16、ureNeighborhood Structure）有些结构是对称性的，即可以从有些结构是对称性的，即可以从A A状态到状态到B B状态，也可状态，也可以从以从B B状态到状态到A A状态状态。条件较弱（结构较松散）的有稳定的收敛条件较弱（结构较松散）的有稳定的收敛。条件定的好，就可以使得在各种状态之下可以到达条件定的好，就可以使得在各种状态之下可以到达另一种状态另一种状态。Simulated AnnealingSimulated Annealing2525其他的问题（4/4）所有解的空间（所有解的空间（The Solution SpaceThe Solution Space）空间小，可以展开

17、搜寻空间小，可以展开搜寻。允许合适的解也存在的话就会加大搜寻空间允许合适的解也存在的话就会加大搜寻空间。我们想办法取一个适当值，期望能快速搜寻，又可避我们想办法取一个适当值，期望能快速搜寻，又可避免在的情况下没有好的进展免在的情况下没有好的进展。Simulated AnnealingSimulated Annealing2626提高效能初始化（初始化（InitializationInitialization）将原本用随机数取初始值的方式改为尽可能找出一有将原本用随机数取初始值的方式改为尽可能找出一有用的起始点用的起始点。结合（结合（CombineCombine）可将仿真退火法配合其他算法应用于

18、问题上。可将仿真退火法配合其他算法应用于问题上。Simulated AnnealingSimulated Annealing2727算法修正(1/2)可接受的机（可接受的机（Acceptance ProbabilityAcceptance Probability）少计算少计算exponentialexponential会加快速会加快速 建立一个可查询各种值的建立一个可查询各种值的tabletable却（却（CoolingCooling）花一些时间找寻最佳温（包括最终温、温差）花一些时间找寻最佳温（包括最终温、温差）Simulated AnnealingSimulated Annealing28

19、28算法修正（2/2）邻近点（邻近点（NeighborhoodNeighborhood）对于好的邻近点给予一个惩罚值对于好的邻近点给予一个惩罚值。价值函数（价值函数（Cost FunctionCost Function）用其他算法的价值函数来做计算用其他算法的价值函数来做计算。Simulated AnnealingSimulated Annealing2929结论模拟退火法已经证明可能收敛出最好解。模拟退火法已经证明可能收敛出最好解。要花较多的时间去搜寻各种解。要花较多的时间去搜寻各种解。可将仿真退火法配合其他算法应用于问题上。可将仿真退火法配合其他算法应用于问题上。已有学者发展出导引模拟退火法，因此可尝试使用新的算已有学者发展出导引模拟退火法，因此可尝试使用新的算法去求解。法去求解。Simulated AnnealingSimulated Annealing3030 The End Thanks for everyone listening