基于變異和交叉的改進粒子群算法

閆元元, 高興寶, 周喜虎

(陜西師范大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院, 陜西 西安 710062)

0 引 言

1995年, 通過對鳥群捕食行為的研究, Eberhart和Kennedy[1，2]提出了粒子群優(yōu)化算法(PSO)， 它基于群體智能理論, 通過群體中粒子跟蹤自己和群體所發(fā)現(xiàn)的最優(yōu)值, 修正前進的方向和速度, 實現(xiàn)尋優(yōu). PSO算法簡單, 需調(diào)整的參數(shù)少且易于實現(xiàn), 因此廣泛應(yīng)用于函數(shù)優(yōu)化、神經(jīng)網(wǎng)絡(luò)優(yōu)化、模糊系統(tǒng)控制以及其它領(lǐng)域[3]. 但是粒子群算法同其它進化算法一樣存在早熟收斂的缺點, 其原因主要在于群體多樣性的喪失. 本文首先介紹了標準粒子群算法, 然后基于變異和交叉提出了一種新的算法, 用4個基準函數(shù)測試, 試驗結(jié)果表明新算法提高了標準粒子群算法克服早熟收斂的能力, 加快了收斂速度.

1 標準粒子群算法

標準粒子群算法首先對群體初始化, 然后通過迭代找到最優(yōu)解. 在每一次迭代中, 每個粒子考慮自身搜索到的最優(yōu)位置以及群體搜索到的最優(yōu)位置進行速度與位置的更新.在D維目標搜索空間中, 由種群數(shù)N的粒子組成群體, 其中第i個粒子的位置為xi=(xi1,xi2,…,xiD), 飛行速度為vi=(vi1,vi2,…,viD), 該粒子當前搜索到的最優(yōu)位置為pi=(pi1,pi2,…,piD), 整個粒子群的最優(yōu)位置為pg=(pg1,pg2,…,pgD). 標準粒子群算法迭代公式如下:

vid(t+1)=wvid(t)+c1r1(pid-xid(t))+c2r2(pgd-xid(t))

(1)

xid(t+1)=xid(t)+vid(t+1)

(2)

其中i=1,2,3,…,N;d=1,2,3,…,D;t是當前迭代次數(shù);學(xué)習因子c1、c2為非負常數(shù), 描述了粒子向自己搜索到的最優(yōu)位置及群體搜索到的最優(yōu)位置的靠近程度;r1和r2為[0，1]上均勻分布的偽隨機數(shù), 其隨機性使得整個粒子群表現(xiàn)出極復(fù)雜的特性;w為非負數(shù), 稱作慣性權(quán)重, 描述了上次迭代速度對當前速度的影響.w較大時算法有較強的全局搜索能力,w較小時算法有較強的局部搜索能力. 文獻[4]通過大量試驗表明, 如果w隨算法迭代的進行而線性減小, 則將顯著改善算法的收斂性能. 設(shè)TMax為最大迭代次數(shù),wEnd為迭代至最大迭代次數(shù)時的慣性權(quán)重,wIni為初始慣性權(quán)重，則有

w(t)=(wIni-wEnd)(TMax-t)/TMax+wEnd

(3)

2 改進的PSO算法(TPSO)

早熟收斂是指在算法早期, 由于群體最優(yōu)的吸引, 群體中大多數(shù)粒子聚集在群體最優(yōu)的周圍, 使得算法的尋優(yōu)停滯在局部鄰域而無法繼續(xù)搜索全局最優(yōu). 因此, 在算法迭代過程中,要克服早熟收斂問題, 就要增加種群的粒子數(shù)或者減弱粒子對當前種群搜索到的局部最優(yōu)位置的追逐[5]. 因為增加種群的粒子數(shù)量, 使得計算量大幅度提高, 因此本文的改進主要體現(xiàn)在減弱粒子對當前種群搜索到的群體最優(yōu)的追逐. 根據(jù)式(1)和式(2), 粒子下一時刻的位置由當前位置和當前速度共同決定, 速度大小決定粒子移動距離, 速度方向決定粒子前進方向. 根據(jù)式(1), 粒子當前速度由3部分決定：第一部分是粒子的原來速度,說明了粒子目前的狀態(tài); 第二部分是認知項, 表示粒子自身的思考; 第三部分是社會部分, 體現(xiàn)了粒子間的信息共享與相互合作, 它引導(dǎo)粒子飛向粒子群中的最優(yōu)位置. 因此, 如果將粒子飛向粒子群中最優(yōu)位置修改為與最優(yōu)位置反向, 即將式(1)中的(pgd-xid(t))修改為(pgd+xid(t)),就可以改變粒子的前進方向和速度, 從而使粒子進入其它區(qū)域進行搜索, 算法就可能發(fā)現(xiàn)新的個體極值pi以及全局極值pg, 我們把上述的操作稱為速度變異操作. 其次考慮到粒子追隨當前pg可能發(fā)現(xiàn)更好的位置, 因此新算法將速度變異操作設(shè)計成一個隨機算子, 即對種群中粒子按一定的概率進行速度變異. 為了使粒子在迭代搜索前期有較強的全局搜索能力, 將搜索空間充滿整個解空間, 我們在前期設(shè)計一個較大的變異概率, 后期則設(shè)計一個較小的變異概率, 以使更多粒子能在所發(fā)現(xiàn)的最優(yōu)位置附近進行搜索.通過以上分析, 我們設(shè)計變異概率如下：

pk=pk0/t

(4)

其中,t是迭代次數(shù),pk0是初始變異概率. 當群體中粒子發(fā)生速度變異時, 其速度更新公式修改為:

vid(t+1)=wvid(t)+c1r1(pid-xid(t))+c2r2(pgd+xid(t))

(5)

另一方面受黑洞原理的啟發(fā), 我們將最優(yōu)個體適應(yīng)值吸收半徑引入到算法中. 黑洞由于其密度較大, 靠近它的物體將被它的引力所約束. 類似地,對于粒子群, 由于pg點處的適應(yīng)值較大. 則接近它的粒子將受到它的約束, 使探索能力減弱, 從而將pg看做一個黑洞, 吸收一定范圍內(nèi)的粒子.特別的, 為刻畫其特性, 我們引入吸收半徑, 即適應(yīng)值吸收半徑r.pg將吸收與其適應(yīng)值之差小于半徑r的粒子, 但為了保持種群規(guī)模, 我們將被吸收的粒子重新初始化. 在本文中, 為了使算法后期收斂不受影響, 我們只將黑洞引入前期迭代中, 即k0T次迭代中(0

此外, 由于在速度更新公式中加入了變異, 速度有可能過大, 因此在算法中引入了算術(shù)交叉算子來減緩位置的變化.算術(shù)交叉算子作用在xi(t)和更新后的位置xi(t+1)上, 特別的通過上面兩個位置的線性組合產(chǎn)生新的位置, 作為下次迭代的初始位置, 即：

xi(t+1)=αxi(t+1)+(1-α)xi(t)

(6)

在本文中, 我們?nèi)ˇ?1/2.

算法流程如下:

步1 隨機初始化種群中每個粒子的位置和速度.

步2 計算每個粒子的適應(yīng)值, 初始化粒子群的當前全局最優(yōu)pg=(pg1,pg2,…,pgD)以及每個個體的當前全局最優(yōu)pi=(pi1,pi2,…,piD).

步3 用(4)式更新pk及用(3)式更新w, 針對變異概率pk, 采用輪盤賭的方式判斷粒子是否發(fā)生變異, 發(fā)生變異時利用(5)式進行速度更新, 否則用(1)式進行速度更新.

步4 用(2)式進行位置更新, 用(6)式作用于當前的位置和更新后的位置上.

步5 判斷粒子的適應(yīng)值是否在最優(yōu)個體適應(yīng)值吸收半徑內(nèi), 如果不在, 轉(zhuǎn)到步7.

步6 對粒子位置進行初始化.

步7 對每個粒子, 將其適應(yīng)值與pi點處的適應(yīng)值作比較,如果較好, 則將其作為當前的最優(yōu)位置, 并比較pi和pg點處的適應(yīng)值,進行pg更新.

步8 檢驗是否滿足結(jié)束條件, 如果當前的迭代次數(shù)達到初始的最大次數(shù), 則停止迭代, 輸出最優(yōu)解, 否則轉(zhuǎn)到步3.

3 試驗分析

下面通過4個基準函數(shù)[6，7]優(yōu)化問題(求解最小值), 來測試本文算法的性能, 4個優(yōu)化函數(shù)如下所示,其中f1(x)為單峰可分二次函數(shù);f2(x)為旋轉(zhuǎn)、不可分離的多峰函數(shù);f3(x)為具有大量局部最優(yōu)點的不可分離函數(shù);f4(x)為具有強烈振蕩的多峰函數(shù).

F1： Sphere function

F2：Griewank function

F3： Ackley function

(n=30,xi∈[-32,32]) minf6=0

F4： Schaffer′s function

在試驗中, 選取標準粒子群算法(linWPSO)作為對比算法. 試驗參數(shù)設(shè)置如下: 兩種算法的種群大小均為30, 最大迭代次數(shù)為1 000, 學(xué)習因子c1、c2均為2.0; 兩種算法中wIni=0.9,wEnd=0.4; 在TPSO算法中,pk0和k0均取為1/2;為了消除隨機干擾, 對每個優(yōu)化函數(shù)獨立運行30次. 所有試驗均在lenovo昭陽 E43A具有 windows xp操作系統(tǒng)的計算機上運行,使用MATLAB 7.6編程.

表1 函數(shù)運行30次比較表

數(shù)值試驗結(jié)果見表1. 從表中可以看出, 對于所有測試函數(shù), 本文算法的優(yōu)化結(jié)果好于對比算法, 其中對于f1(x)、f3(x), 本文算法并沒有達到理論最優(yōu)值, 但在30次平均最優(yōu)和最優(yōu)上要明顯好于標準粒子群算法; 對于f2(x), 本文算法在30次中均達到了理論最優(yōu)值,而標準粒子群算法在運行中均未達到理論最優(yōu)值; 對于f4(x), 本文算法的優(yōu)越性并不明顯, 但在30次運行中, 本文算法有6次達到了理論最優(yōu)值, 而標準粒子群算法僅有1次達到了理論最優(yōu).

圖1 Sphere 圖2 Griewank

圖3 Ackley 圖4 Schaffer

為了更加直觀的了解兩種算法的性能差異, 圖1至圖4給出了4個測試函數(shù)對于兩種算法的最優(yōu)函數(shù)值進化曲線圖. 從曲線圖中可以看出, 對于f1(x)、f2(x)、f3(x)本文算法明顯克服了早熟收斂, 并且收斂速度較標準粒子群算法加快; 對于f4(x), 本文算法在收斂速度上明顯快于標準粒子群算法, 但收斂精度同標準粒子群基本相同.

4 結(jié)束語

針對粒子群優(yōu)化算法的早熟收斂問題, 本文提出了一種改進的算法(TPSO). 在新算法中, 引入了變異和交叉操作，分別用4個基準函數(shù)進行了試驗, 并與標準粒子群算法做了比較, 結(jié)果表明新算法提高了標準粒子群算法克服早熟收斂的能力和收斂速率.

參考文獻

[1] J.Kennedy,R.Eberhart.Particle Swarm Optimization[C].Proc.IEEE International Conf.on Neural Networks.Perth. Australia,1995:1 943-1 948.

[2] Eberhart R C, Kennedy J. A New Optimizer Using Particles Warm Theory[A].Proc.of the Sixth International Symposium on Micro Machine and Human Science[C].Nagoya,1955:39-43.

[3] Eberhart R.C,Shi Y. Particle Swarm Optimizer:Developments, Applications and Resources[C].Proceeding of IEEE Congress on Evolutionary Computation,2001:81-86.

[4] Shi Y H, Eberhart R C. A Modified Particle Swarm Optimizer[A].IEEE World Congress on Computational Intelligence[C]. Anchorage,1998:69-73.

[5] 劉麗芳.粒子群算法的改進及應(yīng)用[D].太原:太原理工大學(xué)碩士學(xué)位論文,2008.

[6] 紀 震, 廖惠連,吳青華. 粒子群算法及應(yīng)用(第1版)[M]. 北京: 科學(xué)出版社, 2009.

[7] 劉 偉, 周育人.一種改進慣性權(quán)重的算法[J]. 計算機工程與應(yīng)用,2009, 22(45):46-48.