《基于微粒群算法与模拟退火算法的协同进化方法》由会员分享，可在线阅读，更多相关《基于微粒群算法与模拟退火算法的协同进化方法（6页珍藏版）》请在金锄头文库上搜索。
1、第? ?卷第?期?以沁年?月自 动 化学报? ? ? ? ? ? ? ? ? ? ?,? ?乳?以拓基于微粒群算法与模拟退火算法的 协同进化方法,王丽芳曾建潮?太原科技大学仿真与计算机应用研究所太原。? 。 。 ? ? ? ? ?,? ? ? ? ? ? ? ?摘典提出了一种基于模拟退火与微粒群算法的协同进化方法,利用了微粒群算法的易实现性、局部快速收敛性以及模拟退火算法的全局收敛性?通过两种算法的协同搜索,可以有效克服微粒群算法的早熟收敛?仿真结果表明,本文的协同进化方法不仅具有较好的全局收敛性能,而且具有较快的收敛速度?文章从理论上证明了该方法以概率?收敛于全局最优解?关锐词微粒群算法,模
2、拟退火,协同进化计算中圈分类号? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?一? ? ? ? ? ?。? ? ? ?,?。?。? ?帅。?即? ?亡葱。,? ?葱,、?。咖。?”?,? ?几?勺?,? ? ,”?”? ? ? ? ? ? ? ?,? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? !? ? ? ? ? ? ? ? ?,? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? !#%inr
3、evisedf ormMare h21.2006期王丽芳等:基于微粒群算法与模拟退火算法的协同进化方法631式识别、多目标优化等工程领域卜例. Ps o具有较快地收敛速度,这归功于微粒间快速的信息交互,但是与此同时也引起 了显著的早熟问题.为此,许多学者从不同的角度对算法 进行了改进,有 的从参数的控制出发! 2 ,有的从增加群体多样性出发f6一g,有的从随机优化算法的全局收敛性条件出发!1。一”,提出各种改进策略,以改善微粒群算法的全局收敛性.本文提 出了一种基于微粒群算法与模拟退火算法的协同进化方法 (SA P SO ).该方法综 合了微粒群算法的局部收敛性和模拟退火 的全局收敛性“a ,
4、借助于两种算法的协同搜索,可以有效地克服微粒群算法的早熟收敛.仿真 实验的结果表明,SAPSO是一种稳健 的全局收敛算法,相关的理论分析证明了此算法能够以概率1收敛于全局最优解.2标准微粒群算法微粒群算法描述了一群以一定速度在。维搜索空间中飞行的微粒,每个微粒的飞行速度可根据自身和群体的飞行经验进行动态调整.微粒的运动状态可以用下面的公式来描述从,(k+1)=。,(k)+e工 r :,(k) (p, (k)一xj(k)+c Z r Z,(k)( P, (k)一x,(k) )(1)x,(k+1)=二勺(k)+。灯(k+1)(2)其 中弋和K分别表示微粒i当前的位置及速度;只表示微粒葱曾经历的最好
5、位置.凡 表示群体微粒所经历的最好位置;m为惯性权重; c:,c:分别代表认知和社会加速 系数; :,:2是服从均匀分布U(0,l )的两个随机变量.3基于微粒群算法与模拟退火的协同进化方法基本微粒群算法采用多点并行搜索方式,各个微粒可根据自身所经历的最好位置与群体所经历的最好位置动态调整当前飞行速度,从而快速地逼近于两者的加权中心,然而算 法却不能保证最终收敛于间题的全局最优解.模拟退火算法是一种以概率1收敛的全局优化算法,但由于其采用单点搜索方式,因而收敛速度较慢.假设将两种算法有机结合起来,利用微粒群算法进行快速 的局部搜索,利用模拟退火的全局收敛性,使得算法以较大 的概率跳出局部极值点
6、.通过两种算法的协同搜索,一方面可以有效地克服P SO的早熟问题,另一方面也可以提高SA的收敛速度.对于极小化优化问题,协同进化方法的实现步骤如下: s t叩L初始化微粒群体.确定p及p。,并设置模拟退火算法的初始值Y=尸,k=氏s tep 2.执行SA进行一步搜索得到一个新解Y;s te P3 .执行P So进化一步得到新的全局最好位置p。;s t即4 .如果 f (Y)=f (p。 )且模拟退火算法和基本微粒群算法都满足终止条件,则 算法结束s t e P5.如果f (Y)0,则有n( l一、(A ) )一”成无 = 0 立.其中,价(A )是 由测度脚所得到的A的概率.引理1.假设目标函
7、数 f为可测函数,区域S为可测子集,并且假设1、假设2满足,设z * 驾为算法所生成的解序列,则之几尸陈凡一 成立其中,尸凤凡是第k步算法生成的解:*任R。的概率,凡为全局最优点集合.定理1.假设P SO算法求解的目标函数 f为可测函数,其解空间S为可测子集,并且 假设、假设“满足设凡,*趁为算法所生成的解序列,则 * l L m o o尸!poe凡一成立.其中,尸!p,、c凡是算法第k步生成的解pg,、ER。的概率,R。为全局最优点集合.证明.SA P SO算法的迭代函数D可以定义为。七,尸,、,一之: 之)瞬忽)( 3 )其中,k是进化代数,算法的解序列为凡, *,容易证明其满足假设L为了
8、满足假设2,规模为m的微粒群的样本空间的并必须包含S,即5gU从,、坛 = l(4)其中城,*为第k代微粒葱的样本空间的支撑集.令Y、为模拟退火算法在k代时搜索到的结果,对于所选的产生矩阵如果单独执行模拟退火算法,则Y、以概率l收敛于全局最优解集R,又因为在SA PSO中,对于有限个满 足f (Y*)f (p。,*)的Y、,令其下一状态为p, *,对产生矩阵和接受矩阵都没有影响,易证在SA P SO中有溉尸玖任R一那么 玖是服从下面分布的一个随机向量,P t *、一,卜俞e x P(一令。“N 0恤,一馨e x P一粤,(5)其中(6)也就是说,当 f(y动k,时,” (U,。 (城,、ns)
9、0,拼*(A)=艺二:拼、,、(A )=1,从而满足假设2 .由引理1可知,SAPSO算法以概率1收敛于全局最优解,故定理l成立.口期王丽芳等:基于微粒群算法与模拟退火算法的协同进化方法6335仿真实验及结果分析本文选取下面四个复杂优化函数来进 行SA PSO的性能分析.1)Seh wef e l函数f l (X )一 E(4 8.9829+xsn(了百万),其中x。 一5 0 0,500 1(8)其最优状态和最优值为m in(f 1(X)=fl(一4 2 0. 9 6 8 7,一4 2 0. 9 6 8 7,一4 2 0. 9 6 8 7)=02)sine s函数f 2 (x)= l +si
10、nZ(xl)+sinZ(xZ)一0.1exp卜x圣一x置),其中一 10蕊x l, x: (10 (9)其最优状态和最优值为 3)Ha rtman函数I而n(f 2 ( X )=f 2 (0,0)=0.9f 3(义)=一艺ee xp一艺a,(x,一p,)2 ,0簇x,、葱 = 1夕=l(10)(p,)=. 1312 . 2 3 29 . 2 3 4 8 .4 0 4 70. 1 6 9 60. 4 13 50. 14 150. 8 8 2 87171. 70. 0 50. 5 56 90. 8 3 0 70. 3 5 2 20. 8 7 3 23. 51. 70. 181017100.10.
11、012 40. 3 73 60.2 8 8 30. 5 7430. 8 2 8 30. 10 0 40. 3 0 4 70.10 910. 5 8 8 60. 9 9 9 10. 6 6 5 00 0 3 8 1!UC UUn U/犷. . . . . . 吸、.8、 夏少“,一“ ”33231 0|民口1 0 . 0 .31 7日/了. . . . . . . 、一一、 、.2 .丹a了召.、其最优状态和最优值为min(j 3(x)=f 3 (0.201, 0.15, 0.477, 0.275, 0.311, 0.657 )=一3324)Ha rtma n函数1 1具有和Ha rtma n函
12、数I相同的形式,只是下述常数不同:、 、 , . . . . . 夕 /Ula01勺nogJ3nJnn Uon,工 .人,工11了036890“7002673了3汛J,一黑黑:罚,呱,一弩0038150574308828/0l其最优状态和最优值为min(f 4(x )=f 4 (0.114,0.556,0.552 )=一3. 5 6.表1列出了主要的仿真结果.实验中两种算法的群体规模均为 2 0,惯性权重。的值均从l线性递减至0 . 001 2,。:=c :二 1.8.对于模拟退火算法,温度衰减函数取t奸:=at*,Ma rk ov链长取L,邻域结构取每维为玖,一q,妹, +司的超矩形.各参数
13、具体取值见表2.表1的仿真结果表明,SA与P SO的协同进化算法具有较好的全局收敛性.与单纯的 SA、PSO算法相比,SAPSO不仅具有较高的成功收敛率,而且具有较快的收敛速度.从表2的参数列表 中可以看到,协同算法的初始温度及M a rkov链长均小于SA的相应参数,也就是说为得到一个最优解,协同算法的计算代价要比SA的小得多.由此可见,sAPso是一种稳健的全局优化算法,收敛速度快,计算代价小.自动化学报32卷表1实例计算结果丁恤b le1ComPa ri so nofo bjec tiv ef unc tionV al u e s妙th r e em ethods函效算法 PSOSA S
14、A P SO PSOSA SA PSO PSOSASA P SO PSOSA SA P SO误差 0.001 0.001 0.001 0.001 0.0010001 0.0010.001 0.0010.001 0.0010.001收敛率 33/5022/50 50/50 43/5024/50 50/5019/5028/5039/50 39/5050/5050/50平均收敛代数 877.60 79854395 00 725.68 199.90342.00 929.342000 00501.0085610 853.60 408.00,几 1 1,勺3 3,J 4 44F F F F F F F F F F F F表2sA与sAPso的部分参数T able2Som ePa rarnetersofSAa ndSAPSO函数算法亡。LqFlS A2 000 00.9880 0 0 04 0FlS AP S O1000.9 620 00 05 0F ZS A2500 00. 92200 0 010F ZS APS O1000. 9620 00 05F3S A5 00 000.986 0 0 000.5F3S AP S O1000.9 6140 0 00.
