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

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,模拟退火算法学习及试验分析,清华大学计算机系,李军,lijun06,2007-4,大纲,1.,介绍,2.Six-hump camel back function,试验,3.,Schwefels,function,试验对比,4.,试验总结,5.,结论与未来工作,6.,参考,1.1,优化问题介绍,描述,:,Find the values of a vector,that minimize a scalar valued loss function L(,).,:the domain of allowable values for a vector,注,:loss function,也被称为,:performance measure,cost function,objective,function,fitness,function,or criterion etc.,1.2,模拟退火算法介绍,用于解决优化问题的一种启发式算法,理论上是一个全局最优算法,.,以一定概率跳出局部极值区域从而增大了找到全局极值的概率,.,伪码描述,:,Simulated-Annealing(),Create initial solution S,repeat,for i=1 to iteration-length do,Generate a random transition from S to,Si,If(C(S)random0,1)then,S=,Si,Reduce Temperature t,until(no change in C(S),C(S):Cost or Loss function of Solution S.,2.Six-hump camel back function,试验,The 2-D Six-hump camel back function is a global optimization test function.,global minimum:,f(x,1,x,2,)=-1.0316;,(x,1,x,2,)=(-0.0898,0.7126),(0.0898,-0.7126).,注,:,在简单问题上成立的结论才有可能推广到更复杂的问题上,.,2.1,函数值分布图,2.2,函数值分布底部区域局部,2.3,与旅行商问题对比,优化问题术语,Six Camel function problem,TSP(Traveling,salesman problem),损失,(,代价,),函数值,f(x,1,x,2,),路径长度,初始解,(x,1,x,2,),坐标,初始城市排列,邻域结构,任选一维加上一个符合正态分布的随机数,e.g.,2-opt(2,个元素交换,),或者,inversion,translation,and switching(,部分反转,移动与交换的混合,),等,全局最优解,f(x,1,x,2,),最小,路径最短,局部最优解,f(x,1,x,2,),较小,路径相对较短,邻域大小,增大或减少随机数的大小,相对上一个解变动较大,.(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),x1,x2,分别在区间,-3,3,-2,2,步长,0.5,进行,grid,式的初始值设置,然后用模拟退火求最小值的结果,(,每一点对应运行一次模拟退火算法之后得到的解,),Six-hump camel back function,极值分布的等高线图,可以看出,在当前参数设置情况下,初始解的位置与局部极值的区域基本是一一对应的,.,也就是从初始解的位置出发,通过邻域搜索,往往落入最近的局部极值区域,.,2.6 R=randn/100,的,3,维效果图,2.7 R=randn/10,与,rand/1,的,3,维效果图,2.8 R=,randn,*10,与,rand*40,的,3,维效果图,2.9 R=randn/100,randn/10,randn/1,的数据比较,最终解平均值,最终解标准差,sd,总计迭代次数平均值,总迭代次数标准差,sd,Randn/100,0.0048,1.2351,6731.6,627.6,Randn/10,-0.6502,0.5410,10705,1082.7,Randn/1,-1.0315,0.0001,11412,1515.3,Randn,*10,-1.0231,0.0122,11331.7,1707.3,Randn,*40,-0.9689,0.1001,11703.2,1422.2,可见,随着邻域的范围的增大,跳出局部极小区域,最终进入全局极小区域的概率越来越大,但是代价是总的迭代次数增加,.,但是随着邻域范围的增大,会出现所谓的在极值附近来回,”,振荡,”,而无法落入极值点的现象,.,可以推测,随着邻域范围的进一步增大及其随机特性,模拟退火算法将退化到随机寻找极值并进行记录极值的算法,.,注,:,当,randn,*10,rand*40,的时候超出我们限定的搜索范围,-3,3,-2,2,的概率增大很多,与前,3,个试验在某种程度上不具备可比性,尽管如此,仍然具有启发性的意义,.,2.10,更改降温速率后的运行结果,(,改为,0.95),Mean_fvale,Std_fvalue,total,Std_total,Randn/100,0.0922,1.2630,24843,2378.2,Randn/10,-0.8224,0.3579,39835,2431.3,Randn/1,-1.0314,0.000272,40637,3986.5,可见,随着邻域的范围的增大,效果与前一个试验类似,区别在于 由于速率放缓,经历了更多的迭代次数才达到最终解,.,而且从中间的图可以看出，进入全局极值的点的初始位置分布较散,这是因为随着迭代次数的增多,以及邻域结构的随机向外伸展性质,由初始位置导致陷入临近局部极值的可能性降低,进入全局极值区域的可能性增大,.,2.11,其他参数尝试,起始温度,(,提高到,1000),每个温度时的最大迭代次数,(,提高到,3000),限于时间,更多参数和变化形式没有进行尝试,.,得到的试验结论与前面基本相同,只是在初始解的临近位置周围略有微小的变化,.,所以,在一个合适的参数设置情况下,对寻找最优解起主要作用的重要因素有,2,个,:,初始解的起始位置,邻域解的构造结构,2.12,与,Native Brute Force Search,比较,Mean_fvalue,Mean_total_iteration,Randn/100,0.0048,6731.6,Randn/10,-0.6502,10705,Rand/1,-1.0315,11412,x1,x2,以,s,的步长在,-3,3,-2,2,的区间内进行,Brute Force Search,判断搜索过程中的最小值并记录下来,.,在解的搜索空间范围较小时,暴力搜索的优势非常明显,只需很少的迭代次数就能达到与模拟退火相当的程度,但是随着解空间以几何倍数增大,需要的迭代次数也迅速增大,.(,本试验中达到同样的精度是模拟退火的,21,倍,.),Fvalue,Total_iteration,S=1,0,35,S=0.5,-0.75,117,S=0.01,-1.0315,241001,降温速率,0.8,时模拟退火试验结果 暴力搜索的试验结果,3.2-d,Schwefels,function,试验对比,Function,defination,:,3.1,初始解位置,(step=40),与最终解值分布图,观察到了在,Six hump,camle,function,中同样的试验效果,.,区别在于由于解空间的较多个极值区域的存在,迭代次数变化不像只有,6,个极值区域时为达到全局极值而明显地增加了总的迭代次数,.,注,1:,由于定义域范围增大,解空间增大,所以将邻域范围设大,从,/1,到*,100.,注,2:,由于邻域范围放大之后,处于自定义域边界的初始解生成的第一次邻域解以,95%,的概率落在,-700,700,范围之内,也就得到,500,500,之外函数极值,所以第,3,个图中的最小值明显比第,1,2,个图中的函数值要小,这说明在原定义域外存在更小的极值点,注,3:,因为画图的原因,3,个图的纵轴的坐标是不一致的,数值依次降低,.,也就是跳出了原来的局部极小区域,.,Randn/1,T=0.8T,Randn,*40,T=0.8T,Randn,*100,T=0.8T,mean_fvalue,fvalue_std,mean_total_iter,total_std,Randn/1,-525.49,228.4,11444,881.4,Randn,*40,-646.67,160.3,12169,1569.5,Randn,*100,-2330.90,287.5,11789,1760.5,3.2,与,Native Brute Force Search,比较,Mean_fvalue,Mean_total_iteration,Rand/1,-525.49,11,444,Rand*40,-646.67,12,169,Rand*100,-2330.90,11,789,x1,x2,以,s,的步长在,-500,500,-500,500,的区间内进行,Brute Force Search,判断搜索过程中的最小值并记录下来,.,同上一个试验结论相同,在以非常粗的粒度进行解的搜索时,暴力搜索的优势非常明显,只需很少的迭代次数就能达到与模拟退火相当的程度,但是随着解空间以几何倍数增大,需要的迭代次数也迅速增大,.(,本试验中达到接近的精度所需迭代次数是模拟退火的,573,倍,.),进而计算时间也大大增加,.,Fvalue,Total_iteration,S=100,-730.35,121,S=40,-837.73,676,S=1-500,500,S=1-700,700,S=1-800,800,S=1-1300,1300,-837.97,-1357.8,1430.1,-2593.1,1,002,001,1,962,801,2,563,201,6,765,201,降温速率,0.8,时模拟退火试验平均结果 暴力搜索的试验结果,3.3 3-d,Schwefels,function,x1,x2,x3,以,80,的步长在,-500,500,-500,500,-500,500,的区间内进行模拟退火求极小值,randn,*40,降温速率,0.8.,由图中可以看出,较大的解多集中在中间的球形区域,外围的值则要小一些,这是由于变量以,0,为中心的区域是相对于外围空间的局部极小值区域,所以从中间区域出发通过模拟退火找到的解也相对于外围要大一些,.,得到的结论仍同前面的试验结果相同,.,注,:,这个图同前几个图不同,Z,轴代表变量,x3,颜色的变化代表找到的解的值的大小,.,4.,试验总结,在,2,个,toy problem,上得到的结论,:,在其他参数合适的情况下,初始解的位置与邻域结构是,2,个重要因素,.,初始解的位置与邻域结构的设计之间对于找到最优解的问题而言存在依赖关系,.,随着邻域的范围的增大,跳出局部极小区域,最终进入全局极小区域的概率越来越大,同时也可能会产生振荡,无法落入极值区域,.,模拟退火本质上也是一种 暴力搜索,只不过是利用随机的性质和局部极值区域连续,(,也取决于求解问题中邻域的结构,),的特性避免了大量计算,.,进而在较短时间内从某种概率上逼近局部最优值和全局最优值,.,4.2,试验总结,问题本身解空间的性质也会影响求解,.,如果全局最优解不在连续的空间上,(isolated point),那么将非常难以找到,.,5.1,结论与未来工作,1,本试验结论能否推广到更高维空间的问题上,对于不同性质的问题是否有同样的结论还有待更多的试验及数据分析,.,例如更改邻域结构,使用,tsp,问题来分析,使用更高维的实际问题等,.,现实问题是复杂的,不同问题的解空间的性质也是仍需探索的,.,对问题本身建模,以及构造合适的邻域结构,是解决问题的关键因素,.,再加上某种程度的初始解的,grid,式的粗遍历并应用模拟退火或其他类似算法,或许可以解决很多问题,.,5.2,结论与未来工作,2,对工程实践的启发性意义,先进行粗粒度的搜索,找到一个较优的解,然后在这个解的周围,利用设计合适的邻域结构,进而找到比这个解更优的解,.,理论中通过迭代无穷次达到平稳分布,其实也就是是相当于遍历了所有的解空间,.,某种程度的”,brute,force”(less,bugs,no,human miss),是解决当前组合优化问题的一种有效途径,.,E.g.,1997,年深蓝,(,或许是当时最快的计算机,),打败世界国际象棋冠军是暴力搜索的结果,.-,许丰雄,6.,参考,1.,matlab,code,url,:,a function,url,:,Steven,Skiena,The Algorithm Design Manual,4.James C.,Spall,Introduction to Stochastic Search and Optimization,5.,刑文训 谢金星,现代优化计算方法,附录,1.TSP,的邻域的一种构造方法示例,The Inversion,translation,and switching operations are selected randomly with probabilities 0.75,0.125,and 0.125,Tour:1 2 3 4 5 6 7 8,1,5 4 3 2,6 7 8 (Inversion),1,6,2 3 4 5,7,8 (Translation),1,5,3 4,2,6 7 8 (Switching),2-opt,Select the best from neighborhood.,Neighborhood(1 2 3 4)=(1 2 3 4),(1 3 2 4),(1 4 3 2),(1 2 4 3),返回,附录,2.,遗传算法特性,由于遗传算法的交叉变异等特性,在合适的参数设置情况下,所以不存在像模拟退火那样严重依赖于初始点的位置和邻域结构,.,From,Slides for,Introduction to Stochastic Search and Optimization,(,ISSO,),by J.C.,Spall,附录,3.,优化算法笔记,(,部分转载,),局部搜索，模拟退火，遗传算法，禁忌搜索的形象比喻：为了找出地球上最高的山，一群有志气的兔子们开始想办法。,1,兔子朝着比现在高的地方跳去。他们找到了不远处的最高山峰。但是这座山不一定是珠穆朗玛峰。这就是局部搜索，它不能保证局部最优值就是全局最优值。,2,兔子喝醉了。他随机地跳了很长时间。这期间，它可能走向高处，也可能踏入平地。但是，他渐渐清醒了并朝最高方向跳去。这就是模拟退火。,3,兔子们吃了失忆药片，并被发射到太空，然后随机落到了地球上的某些地方。他们不知道自己的使命是什么。但是，如果你过几年就杀死一部分海拔低的兔子，多产的兔子们自己就会找到珠穆朗玛峰。这就是遗传算法。,4.,兔子们知道一个兔的力量是渺小的。他们互相转告着，哪里的山已经找过，并且找过的每一座山他们都留下一只兔子做记号。他们制定了下一步去哪里寻找的策略。这就是禁忌搜索。,From