DOC《基本模拟退火算法》

基本模拟退火算法 基本模拟退火算法概述 模拟退火算法(Simulate Anneal,SA)是一种通用概率演算法,用来在一个大的搜寻空间内找寻命题的最优解.

模拟退火是S.Kirkpatrick, C.D.Gelatt和M.P.Vecchi在1983年所发明.而V.?ern?在1985年也独立发明此演算法.模拟退火算法是解决TSP问题的有效方法之一. SA来自冶金学的专有名词退火.退火是将材料加热后再经特定速率冷却,目的是增大晶粒的体积,并且减少晶格中的缺陷.材料中的原子原来会停留在使内能有局部最小值的位置,加热使能量变大,原子会离开原来位置,而随机在其他位置中移动.退火冷却时速度较慢,使得原子有较多可能可以找到内能比原先更低的位置. SA的原理也和金属退火的原理近似:将热力学的理论套用到统计学上,将搜寻空间内每一点想像成空气内的分子;

分子的能量,就是它本身的动能;

而搜寻空间内的每一点,也像空气分子一样带有"能量",以表示该点对命题的合适程度.演算法先以搜寻空间内一个任意点作起始:每一步先选择一个"邻居",然后再计算从现有位置到达"邻居"的概率.

1、算法原理 基本SA算法允许以一定的概率接受比当前解差的解,因此有助于跳出局部最优解,达到全局寻优的目的. SA算法接受新解的概率为: 其中

2、算法步骤 基本SA算法的基本步骤如下: Step

1 随机生成一个可行解,评估其适应度;

Step

2 主循环.判断是否成立,若成立,输出结果退出程序,若不成立,继续. Step

3 内循环 Step 3.1 置内循环次数Nc=0, Step 3.2 从邻域内产生一个新解,对其进行适应度评估,判断其适应度是否下降,若是,则接受该解,否则的话,再判断是否成立,若是同样接受该解,否则舍弃该解. Step3.3 Nc= Nc+1,判断Nc是否达到设定次数,若是则退出内循环,否则转Step3.1 Step

4 退温操作.置T=rT,转Step2

3、算法的matlab实现 见程序

4、算法举例 采用SA算法求取Sphere Mode函数的最小值. 1) 基本测试 在matlab命令窗口输入: >> [xm,fv] = SA(@fitness,3,1e-5,0.99,200,30) 得到如下收敛曲线 2) 参数对算法性能的影响 在matlab命令窗口输入: >> [xm,fv] = SA(@fitness,3,1e-20,0.92,50,30) >> [xm,fv] = SA(@fitness,3,1e-20,0.95,50,30) >> [xm,fv] = SA(@fitness,3,1e-20,0.98,50,30) 将上面求得的结果列表比较如下: r 0.92 0.95 0.98 x1 0.011260864 0.009003937 0.028117043 x2 -0.005346167 -0.027626111 0.00010305 x3 -0.041318254 0.010087359 0.002427612 x4 -0.033906376 0.00435169 -0.005846216 x5 -0.014277999 0.011901921 -0.012487541 x6 -0.012238848 0.008014468 -0.004671118 x7 0.014588065 -0.002626988 0.006391876 x8 0.021070439 -0.013495949 0.013660122 x9 0.017112069 0.015173136 0.013936932 x10 0.032338717 -0.012914677 -0.00395895 x11 -0.007678413 -0.016933276 0.001567727 x12 -0.031961938 0.006708972 0.002275711 x13 0.002175898 -0.009599289 -0.003983244 x14 -0.033096332 -0.003014084 0.002415027 x15 -0.02119991 0.010692107 -0.014556338 x16 0.002458716 0.002939821 0.009351971 x17 -0.006521067 0.001842347 -0.007156494 x18 -0.00144458 0.007571509 0.00899922 x19 0.000137944 0.010661192 0.005457114 x20 0.027670557 -0.013992089 0.003288303 x21 -0.042107302 -0.011208205 -0.016506858 x22 0.000705935 0.005578582 0.013875214 x23 -0.000740009 -0.003149655 -0.006707376 x24 -0.03298692 -0.001055091 0.014403569 x25 -0.016799925 0.000943898 0.001816135 x26 0.020495049 -0.000169498 0.00272825 x27 -0.011952345 0.013607803 -0.004958003 x28 -0.000547562 0.002059993 -0.01046159 x29 -0.019837098 -0.006682096 0.004621678 x30 -0.024675479 -0.020205595 -0.010194987 f(x) 0.013517707 0.003494039 0.002934766 可见r增大可以提高算法的寻优效果,主要是由于r的增大使得SA的主迭代次数增加,它会消耗更多的机时. 在matlab命令窗口输入: >> [xm,fv] = SA(@fitness,3,1e-20,0.95,50,30) >> [xm,fv] = SA(@fitness,3,1e-20,0.95,100,30) >> [xm,fv] = SA(@fitness,3,1e-20,0.95,200,30) 将上面求得的结果列表比较如下: Nc

10 100

200 x1 0.032018165 -0.01110356 5.73543E-05 x2 -0.00497793 -0.003948012 -0.00358504 x3 0.003139057 -0.007221524 0.004447694 x4 -0.015899022 0.004003558 -0.026004505 x5 0.03147126 0.009075877 0.004748912 x6 -0.008872097 0.003856766 0.007650891 x7 -0.009422063 0.000175991 0.013193471 x8 0.005951315 0.016067988 0.016498731 x9 0.006970661 0.005796971 0.003681001 x10 0.018181934 0.000756655 0.008925965 x11 -0.002149673 -0.002522776 0.005559869 x12 0.005805448 -0.000313619 -0.000988851 x13 0.016519263 0.011305466 0.013714983 x14 0.005953801 -0.001108076 0.011429515 x15 0.011912591 -0.02563726 0.00170566 x16 -0.014941994 -0.011791919 0.022232404 x17 0.005799337 0.000459946 -0.007335186 x18 0.009367682 -0.007400509 0.003920884 x19 -0.000887835 -0.008316765 -0.001161938 x20 -0.004856808 0.006729863 -0.001531872 x21 -0.022834458 -0.015918049 0.006824975 x22 0.000980481 -0.003573188 0.007245403 x23 -0.010637795 -0.009436899 0.002782808 x24 -0.000658657 -0.013301654 0.004092039 x25 0.0075931 0.001714283 0.002773532 x26 0.003332325 0.005211055 0.011939876 x27 -0.007785621 -0.028786356 -0.018108192 x28 0.007906555 -0.002344233 0.002646237 x29 -0.005719801 -0.010595359 -0.008807069 x30 -0.006247275 -0.009741217 0.010360291 f(x) 0.004642294 0.003301488 0.003043775 可见内循环迭代次数的增加有助于SA算法找到更优解,但效果不是特别明显,且需要消耗大量的计算时间,因此建议内循环次数设置不宜过大.