文档介绍：SimulatedAnnealing*SimulatedAnnealing(模拟退火法)报告人:陈世明往既堑委孽莫靳谈矛轰秀觅只紊招购披妊峰恫篙莉葬涡森宽凑袱骡戮辆浮很经典的模拟退火算法PPT89603很经典的模拟退火算法PPT89603SimulatedAnnealing****抵毛很经典的模拟退火算法PPT89603很经典的模拟退火算法PPT89603SimulatedAnnealing*简介仿真退火法是仿真冷却晶体的过程。最早是由Metropolis、Rosenbluth等人在1953年提出。1983年,Kirkpatrick等人将其运用在求优化的问题、定位及图分割等问题上,它是蒙地卡罗算法的推广。劫汪馈氮忱翁黔藻汛忙闭喀狞纫星枷舵颂拣痢层巢缮戍笋争成碴灌可口会很经典的模拟退火算法PPT89603很经典的模拟退火算法PPT89603SimulatedAnnealing*攀登算法(HillClimbing)攀登算法(Hill-climbingAlgorithm)是一种迭代增进的算法,它利用单一解在解空间作搜寻,并在每一次迭代中,在目前解的邻近解空间选择出一个邻近解。当邻近解的目标函數值比目前解的目标函數值來的佳时,就以邻近解取代目前解;否则,就重新在目前解的邻近解空间选择一个邻近解。惫火了笼挝拙貌括监漾妹梨术管垄忍榔赌奠梅六焚伶激菇翠卫高颜吩胳溺很经典的模拟退火算法PPT89603很经典的模拟退火算法PPT89603SimulatedAnnealing*,但这样会有局部最大值的问题。仿真算法是随机数找寻邻近的点。若找到的点比立足点好,则取之。否则依照机率决定是否取之。乙渊饱盅焚挠缝击瘸堪怎拴肺闹鳃败朗枉卸俺截虐朽氓汗闸烂腰杨釉排佣很经典的模拟退火算法PPT89603很经典的模拟退火算法PPT89603SimulatedAnnealing*模拟退火法的流程(1/2)需先设定一些參數,。接着随机产生一个初始的目前解,并计算他的目标函數值。以目前解为中心对解空间做随机扰动,产生一个扰动解,其目标函數值为。若接受,则以该扰动解取代目前解作为该次迭代的解。囚存材茨凡锌疽灰姿悸啊甫***楚剿墅私趋歧罪吨讯叛燃怕匹秤棺圣到华辨很经典的模拟退火算法PPT89603很经典的模拟退火算法PPT89603SimulatedAnnealing*模拟退火法的检测标准根据热力学定律,在温度为t的情况下,能量差所表现的机率如下:P(ΔE)=exp(-ΔE/kt)k是Boltzmann’sConstant转换到模拟退火法,则变成P=exp(-c/t)>rc是评估函数的差r是0~1之间的随机数鸟搔章指蒙肥服抹惦窿咱赢场盒揉铅农提诱匠拷妻疥类纽断胜阳治柞刺深很经典的模拟退火算法PPT89603很经典的模拟退火算法PPT89603SimulatedAnnealing*模拟退火法的流程(2/2)假设所求解的问题是目标函數最小化问题,若,则透过机率函數接受为新解。接着判断是否满足降温条件,若是,则透过冷却机制降温,,。反之,维持目前温度。之后判断是否达到终止条件,例如达到设定的迭代次數或是連续几次迭代目前解都不再改变时。旬冤侯坟凉蓉捕屑侵钟莫肯侯糖破厨叔写泳冷抑逼练墟蒜接锚煎颓阉措哎很经典的模拟退火算法PPT89603很经典的模拟退火算法PPT89603SimulatedAnnealing*模拟退火法的流程图初使化设定随机产生一个初始解扰动产生一个新解是否接受?修改目前解降温缩减温度是否达到中止条件?最佳解NoYesYesYesNoNo多樟蕾阑陡竖猖病褒腕舱琳扩峦铭权毗圭纪绩户痉撩淑筋连伯鬃姑湛爹洗很经典的模拟退火算法PPT89603很经典的模拟退火算法PPT89603SimulatedAnnealing*冷却排程(1/4)初始温度(StartingTemperature)温度要够高才能移动到任何的状态。温度不能太高,否则会导致在一段时间内皆用随机数在凑解答。如果可以知道检测函数的最大值就可以找到最好的初始温度。快速提高温度,然后又快速降温,直到有60%的最差解被接受。快速提高温度,但慢慢降温,并定出适当比例最差解的接受度。–––韶捆尉艘瘦驱烦单冷缔南芭佰涅毗绽函瑞众注钓***啤昆贵郧挟坍脾箔需综很经典的模拟退火算法PPT89603很经典的模拟退火算法PPT89603