模拟退火算法学习及试验分析

模拟退火算法学习及试验分析清华大学计算机系李军[e-mail]2007-4大纲1.介绍2.Six-humpcamelbackfunction试验3.Schwefel‘sfunction试验对比4.试验总结5.结论与未来工作6.参考1.1优化问题介绍描述:Findthevaluesofavectorθ∈ΘthatminimizeascalarvaluedlossfunctionL(θ).Θ:thedomainofallowablevaluesforavectorθ注:lossfunction也被称为:performancemeasure,costfunction,objectivefunction,fitnessfunction,orcriterionetc.1.2模拟退火算法介绍用于解决优化问题的一种启发式算法,理论上是一个全局最优算法.以一定概率跳出局部极值区域从而增大了找到全局极值的概率.伪码描述:Simulated-Annealing()CreateinitialsolutionSrepeatfori=1toiteration-lengthdoGeneratearandomtransitionfromStoSiIf(C(S)=C(Si))thenS=Sielseif(exp(C(S)-C(Si))/ktrandom[0,1))thenS=SiReduceTemperaturetuntil(nochangeinC(S))C(S):CostorLossfunctionofSolutionS.2.Six-humpcamelbackfunction试验The2-DSix-humpcamelbackfunctionisaglobaloptimizationtestfunction.globalminimum:f(x1,x2)=-1.0316;(x1,x2)=(-0.0898,0.7126),(0.0898,-0.7126).注:在简单问题上成立的结论才有可能推广到更复杂的问题上.22222121412121)44()31.24(),(xxxxxxxxxf331x221x2.1函数值分布图2.2函数值分布底部区域局部2.3与旅行商问题对比优化问题术语SixCamelfunctionproblemTSP(Travelingsalesmanproblem)损失(代价)函数值f(x1,x2)路径长度初始解(x1,x2)坐标初始城市排列邻域结构任选一维加上一个符合正态分布的随机数e.g.,2-opt(2个元素交换)或者inversion,translation,andswitching(部分反转,移动与交换的混合)等全局最优解f(x1,x2)最小路径最短局部最优解f(x1,x2)较小路径相对较短邻域大小增大或减少随机数的大小相对上一个解变动较大.(e.g.,增大部分反转的比例,减少移动和交换的比例)2.4主要试验参数设置‘CoolSched‘:(0.8*T)%温度下降速率0.8‘Generator‘:生成邻域:从x,y中随机地选择一个再加上一个随机数R,R=randn/100;(rand符合标准正态分布N(0,1)的伪随机数,意味着随机变量落入[-1,1]内的概率是68.26%,落入[-2,2]内的概率是95.44%落入[-3,3]内的概率是99.72%,除以100以后也就是大概范围在e-3量级的小数,也就是大约以95%的概率处于[-0.02,0.02])‘InitTemp‘:1%起始温度‘MaxTries‘:300%同一温度下的最大迭代次数‘StopTemp‘:1e-8%终止温度…2.5初始解的位置对最终解的影响(R=randn/100)xySixhumpcamelbackfunction-3-2-10123-1.5-1-0.500.511.5-20246810-4-3-2-101234-3-2-10123effectofinitialposition-1-0.500.511.52x1,x2分别在区间[-3,3],[-2,2]步长0.5进行grid式的初始值设置,然后用模拟退火求最小值的结果(每一点对应运行一次模拟退火算法之后得到的解)Six-humpcamelbackfunction极值分布的等高线图可以看出,在当前参数设置情况下,初始解的位置与局部极值的区域基本是一一对应的.也就是从初始解的位置出发,通过邻域搜索,往往落入最近的局部极值区域.2.6R=randn/100的3维效果图-4-2024-202-1-0.500.511.52-1-0.500.511.522.7R=randn/10与rand/1的3维效果图-4-2024-202-1-0.500.511.52-1-0.500.511.52-4-2024-202-1-0.500.511.52-1.0316-1.0315-1.0314-1.0313-1.0312-1.0311-1.031-1.0309-1.0308-1.03072.8R=randn*10与rand*40的3维效果图-4-2024-202-1-0.500.511.52-1.03-1.02-1.01-1-0.99-0.98-0.97-0.96-0.95-4-2024-202-1-0.500.511.52-1-0.9-0.8-0.7-0.6-0.5-0.42.9R=randn/100,randn/10,randn/1的数据比较最终解平均值最终解标准差sd总计迭代次数平均值总迭代次数标准差sdRandn/1000.00481.23516731.6627.6Randn/10-0.65020.5410107051082.7Randn/1-1.03150.0001114121515.3Randn*10-1.02310.012211331.71707.3Randn*40-0.96890.100111703.21422.2可见,随着邻域的范围的增大,跳出局部极小区域,最终进入全局极小区域的概率越来越大,但是代价是总的迭代次数增加.但是随着邻域范围的增大,会出现所谓的在极值附近来回”振荡”而无法落入极值点的现象.可以推测,随着邻域范围的进一步增大及其随机特性,模拟退火算法将退化到随机寻找极值并进行记录极值的算法.注:当randn*10,rand*40的时候超出我们限定的搜索范围[-3,3],[-2,2]的概率增大很多,与前3个试验在某种程度上不具备可比性,尽管如此,仍然具有启发性的意义.2.10更改降温速率后的运行结果(改为0.95)-4-2024-202-1-0.500.511.52-1-0.500.511.52-4-2024-202-1-0.500.511.52-1-0.500.511.52-4-2024-202-1-0.500.511.52-1.0316-1.0314-1.0312-1.031-1.0308-1.0306-1.0304-1.0302-1.03-1.0298Mean_fvaleStd_fvaluetotalStd_totalRandn/1000.09221.2630248432378.2Randn/10-0.82240.3579398352431.3Randn/1-1.03140.000272406373986.5可见,随着邻域的范围的增大,效果与前一个试验类似,区别在于由于速率放缓,经历了更多的迭代次数才达到最终解.而且从中间的图可以看出，进入全局极值的点的初始位置分布较散,这是因为随着迭代次数的增多,以及邻域结构的随机向外伸展性质,由初始位置导致陷入临近局部极值的可能性降低,进入全局极值区域的可能性增大.2.11其他参数尝试起始温度(提高到1000)每个温度时的最大迭代次数(提高到3000)限于时间,更多参数和变化形式没有进行尝试.得到的试验结论与前面基本相同,只是在初始解的临近位置周围略有微小的变化.所以,在一个合适的参数设置情况下,对寻找最优解起主要作用的重要因素有2个:初始解的起始位置邻域解的构造结构2.12与NativeBruteForceSearch比较Mean_fvalueMean_total_iterationRandn/1000.00486731.6Randn/10-0.650210705Rand/1-1.031511412x1,x2以s的步长在[-3,3],[-2,2]的区间内进行BruteForceSearch,判断搜索过程中的最小值并记录下来.在解的搜索空间范围较小时,暴力搜索的优势非常明显,只需很少的迭代次数就能达到与模拟退火相当的程度,但是随着解空间以几何倍数增大,需要的迭代次数也迅速增大.(本试验中达到同样的精度是模拟退火的21倍.)FvalueTotal_iterationS=1035S=0.5-0.75117S=0.01-1.0315241001降温速率0.8时模拟退火试验结果暴力搜索的试验结果3.2-dSchwefel‘sfunction试验对比Functiondefination:)||sin()(1iniixxxf500500ix50005000ix3.1初始解位置(step=40)与最终解值分布图-5000500-5000500-1200-1000-800-600-400-2000-1100-1000-900-800-700-600-500-400-300-200-100观察到了在Sixhumpcamlefunction中同样的试验效果.区别在于由于解空间的较多个极值区域的存在,迭代次数变化不像只有6个极值区域时为达到全局极值而明显地增加了总的迭代次数.注1:由于定义域范围增大,解空间增大,所以将邻域范围设大,从/1到*100.注2:由于邻域范围放大之后,处于自定义域边界的初始解生成的第一次邻域解以95%的概率落在[-700,700]范围之内,也就得到[500,500]之外函数极值,所以第3个图中的最小值明显比第1,2个图中的函数值要小,这说明在原定义域外存在更小的极值点注3:因为画图的原因,3个图的纵轴的坐标是不一致的,数值依次降低.也就是跳出了原来的局部极小区域.Randn/1,T=0.8TRandn*40,T=0.8TRandn*100,T=0.8T-5000500-5000500-3500-3000-2500-2000-1500-3200-3000-2800-2600-2400-2200-2000-1800mean_fvaluefvalue_stdmean_total_itertotal_stdRandn/1-525.49228.411444881.4Randn*40-646.67160.3121691569.5Randn*100-2330.90287.5117891760.5-5000500-5000500-1400-1200-1000-800-600-400-200-1200-1100-1000-900-800-700-600-500-4003.2与NativeBruteForceSearch比较Mean_fvalueMean_total_iterationRand/1-525.4911,444Rand*40-646.6712,169Rand*100-2330.9011,789x1,x2以s的步长在[-500,500],[-500,500]的区间内进行BruteForceSearch,判断搜索过程中的最小值并记录下来.同上一个试验结论相同,在以非常粗的粒度进行解的搜索时,暴力搜索的优势非常明显,只需很少的迭代次数就能达到与模拟退火相当的程度,但是随着解空间以几何倍数增大,需要的迭代次数也迅速增大.(本试验中达到接近的精度所需迭代次数是模拟退火的573倍.),进而计算时间也大大增加.FvalueTotal_iterationS=100-730.35121S=40-837.73