采用多搜索模式的粒子群算法

張呈志, 王　勇, 李海濱

(廣西民族大學 a.信息科學與工程學院;b.廣西高校復雜系統與智能計算重點實驗室，南寧　530006)

?

采用多搜索模式的粒子群算法

張呈志, 王勇, 李海濱

(廣西民族大學 a.信息科學與工程學院;b.廣西高校復雜系統與智能計算重點實驗室，南寧530006)

摘要：從現實中鳥的搜索方式中得到靈感, 提出一種新的變異粒子群算法, 稱之為采用多搜索模式的粒子群優化算法(MMPSO)。該算法中的每個粒子使用3種搜索模式在搜索空間中搜索食物, 可隨時調整其搜索方式。在數值仿真實驗中選擇了幾個比較典型的高維復雜優化問題用來測試算法的性能。結果表明:算法的全局搜索能力和避免粒子陷入局部最優的能力都得到了明顯提高, 在一定程度上避免了早收斂現象的發生, 可用于求解高維復雜函數的優化問題。

關鍵詞：粒子群算法;多搜索模式;MMPSO

0引言

粒子群優化算法(particle swarm optimization, PSO)[1]是Kennedy和Eberhart于1995年共同提出的一種基于群體智能的并行優化算法。由于PSO算法具有理論方法簡單、設置參數少、易于編碼實現等特點, 且在復雜優化問題、工程等方面也得到了廣泛應用, 因而自PSO算法提出以來, 越來越受到學者們的關注；但與其他隨機搜索算法相似, PSO算法也存在早熟收斂的不足。 針對標準PSO存在的不足, 不少學者對PSO開展了較為深入的研究, 提出了多種PSO改進策略[2-30], 取得了不少研究成果。例如： 呂振肅等[8]提出一種基于群體適應度方差自適應變異的粒子群優化算法(AMPSO); 赫然等[9]提出一種改進的自適應逃逸微粒群算法; Liang等[16]提出一種全面學習的粒子群優化算法(CLPSO); 呂強等[17]將蟻群優化算法的信息素共享機制引入到粒子群優化算法中, 提出一種基于信息素機制的粒子群優化算法(PSO-PM)， 以及一種信息充分交流的粒子群優化算法(PSO-FCI)[18]; 吳曉軍等[19]提出一種均勻搜索粒子群算法(UPSO); 魏波等[20]提出基于穩定策略的粒子群優化算法(SSPSO); 高哲等[22]提出一種基于平均速度的混合自適應粒子群算法; 杜繼永等[23]提出一種具有初始化功能的自適應慣性權重粒子群算法(IAW-PSO); 喻飛等[24]提出一種去個性化理論的粒子群算法(DTPSO); 朱慶保等[25]提出一種求解動態連續優化的分層粒子群算法(LDPSO); 文獻[26-27]提出了將差分進化與PSO相結合的混合優化方法; 文獻[28-29]提出了將遺傳算法(GA)與PSO相結合的混合優化方法; 文獻[30]提出了將蟻群算法(ACO)與PSO相結合的混合優化方法等等。

以上改進策略歸納起來主要有:1)控制慣性權重、學習因子、飛行速度等參數, 以平衡算法的全局搜索與局部搜索能力;2)引入一些使算法能跳出局部極值的機制;3)將群體劃分成若干個子群、定義不同的鄰域拓撲結構, 以使種群的多樣性得到保持;4)完全沿用標準PSO設計粒子的飛行模式， 規定粒子只能飛到介于當前群體最優與個體歷史最優的某一小范圍內覓食, 粒子只采用不變向飛行方式。盡管文獻[2-30]提出的方法在一定程度上改善了PSO的優化性能, 但在應用于求解維數較高的復雜優化問題時, 仍出現早熟收斂問題。考慮到標準PSO是從鳥的覓食行為特征中得到靈感而提出的，本文也從現實鳥的飛行方式和覓食行為方式中尋找答案, 提出一種新的變異粒子群算法, 即一種采用多搜索模式的粒子群算法(particle swarm optimization by using multi-search modes, MMPSO), 并通過數值仿真實驗對算法性能進行了驗證。

1標準粒子群算法存在的不足

設t時刻第i粒子在搜索空間中的位置和飛行速度分別表示為Xi(t)=(xi1(t),xi2(t), …, xiD(t))和Vi(t)=(vi1(t),vi2(t), …,viD(t)), 第i粒子經歷過的最優位置記為Pbest(t)=(pi1(t),pi2(t), …, piD(t));所有粒子當前找到的最優位置記為Gbest(t)=(g1(t),g2(t), …, gD(t))。第i粒子則按下式來更新其飛行速度和位置:

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

c2r2(gid(t)-xid(t)),

(1)

xid(t+1)=xid(t)+vid(t+1),d=1, 2， …,D。

(2)其中:w為慣性權重因子;c1和c2為正的加速常數;r1和r2為[0,1]內的均勻隨機數;D為搜索空間維數。式(1)由3部分組成:第1部分wvid(t)為“慣性(inertia)”, 代表粒子有維持自己先前速度的趨勢;第2部分c1r1(pid(t)-xid(t))為“認知(cognition)”部分, 反映了粒子對自身歷史經驗的記憶或回憶, 代表粒子有向自身歷史最佳位置逼近的趨勢;第3部分c2r2(gid(t)-xid(t))為“社會(social)”部分,反映了粒子間協同合作與知識共享的群體歷史經驗, 代表粒子有向群體或鄰域歷史最佳位置逼近的趨勢。

分析標準PSO算法中的粒子飛行控制式(1)和式(2), 可知粒子的飛行方式(搜索方式)有以下約束: 1)粒子被限制在由個體當前位置、 個體歷史最優位置與群體當前最優位置所構成的扇形區域內開展搜索活動, 由于被個體歷史最優位置與群體當前最優位置吸引， 粒子終將聚集到群體當前最優位置的附近, 從而使粒子群過早聚集到群體當前最優位置的附近, 使種群的多樣性得不到有效的保持, 導致算法搜索喪失了跳出局部最優的能力;2)群體中所有粒子任何時候都只能以式(1)和式(2)來控制其飛行(搜索)方式。這一約束條件在很大程度上使粒子的飛行(搜索)活動缺乏機動性和靈活性, 降低了粒子躲避障礙物或天敵的能力(即跳出局部最優的能力)，同時也降低了粒子的搜索能力, 最終降低了粒子跳出局部最優的能力。

2采用多搜索模式的粒子群算法

2.1算法基本思想

自然界中的鳥通常有以下特點:1)具有較好的飛行技能和較強的搜索食物的能力, 在飛行過程中可隨時調整飛行速度、改變飛行方向、 可視不同情況調整飛行模式。如鳥在覓食過程中, 可繞過障礙物、躲避天敵的攻擊, 可采用靈活多變的飛行方式在叢林里搜尋食物。2)鳥與鳥之間是通過鳴叫聲向對方傳遞信息的。然而在同一時刻, 鳥群中有些鳥可能聽到其他鳥的鳴叫聲(即接收到信息), 有些則可能沒有聽到(即沒有接收到信息)。某一個體能否接收到另一個體發出的信息, 通常與其當時所處的位置有關。所處的位置越好, 接收到信息的概率就越大;反之則越小。3)鳥在樹林里的搜索果實活動, 大體上可分為3種情況:一是個體在搜索空間中開展自由搜索活動;二是有多個個體參與和配合的集體搜索活動;三是有多個個體發現某棵樹上有果實后, 就飛到那棵樹上開展搜索果實的活動。

根據以上鳥的搜索(飛行)活動特征, 規定鳥在覓食活動中, 只有以上所提及的3種情況。相應地, 規定鳥(粒子)的搜索(飛行)模式只有3種:漫游模式、 搜索模式、 覓食模式。

2.2算法描述

基于以上基本思想, 對粒子(鳥)的搜索模式作如下改進:

(3)

則稱其在t時刻按個體搜索模式開展搜索活動。其中c為d中的隨機數,d=1,2, …,D。該粒子的搜索方向如圖1所示。

圖1　粒子搜索方向示意圖Fig.1　Sketch map of particle searching direction

② 搜索模式。若第i粒子(鳥)在t時刻開展搜索活動:

(4)

則稱其在t時刻按集體搜索模式開展搜索活動。其中w(t)為關于時間t的遞減函數, 0

③ 覓食模式。若第i粒子(鳥)在t時刻飛到Gbest(t)的周圍開展覓食行動:

xid(t+1)=gk(t),d=1,2, …,D。

(5)

其中,k為{1, 2,…,D}中的一個隨機數, 則稱其在t時刻按集體覓食模式開展搜索活動。鳥群從不同的方向飛到目標Gbest(t)附近的情景如圖2所示。

這說明， 粒子(鳥)發現目標Gbest之后, 并不是直接飛到點Gbest處覓食, 而是從不同的方向， 采用變向的飛行方式飛到點Gbest的周圍尋找食物, 或者在Gbest的周圍開展覓食活動, 而直接飛向點Gbest覓食的粒子(鳥)則非常少。

2.3飛行模式選擇方法

由于鳥是通過鳴叫向群體中的其他個體傳遞信息的, 而對方能否接收到信息, 與其當時所處相對位置的優劣有關。因此, 首先確定信息發布規則，規定當前位置最優者為信息發布者;其次, 設計信息接收規則，粒子(鳥)接收到信息的概率, 與其所處的位置優劣有關;再次, 設計粒子(鳥)的搜索模式選擇規則，粒子(鳥)視不同的情況選擇不同的搜索模式。

圖2　鳥飛到目標樹上覓食示意圖Fig.2　Schematic diagram of birds flying to the object tree to forage

根據以上描述, 假定個體利用群體信息來選擇其飛行模式的方法:設群體規模為M, 第i粒子t時刻位于Xi(t)。首先將群體依據適應度從最優到最差進行排序, 記第i粒子t時刻在群體中排第si(t)位, 則1≤si(t)≤M。若si(t)=1, 則表示第i粒子t時刻為群體當中位置最優者；si(t)=M, 則表示第i粒子t時刻為群體當中最差者, 定義

(6)

為位于Xi(t)的第i粒子(在t時刻)可接收到信息發布者(位于Gbest(t))發出聲音強度的最小值。顯然0≤si(t)≤1。此時, 若第k粒子的位置是X1(t),X2(t), …,XM(t)當中最優者, 則sk(t)≤sj(t);若第k粒子的位置是最差者, 則sj(t)≤sk(t)=1,j=1, 2,…,M。也就是說,si(t)越小, 表示位于Xi(t)的第i粒子接收到信息發布者(位于Gbest(t))發出聲音信號的概率也就越大。

記φ(t)為信息發布者在t時刻發出的聲音強度值, 其中φ(t)為(0, 1]中的均勻隨機分布。作以下規定:

(i)若φ(t)

綜上所述, 粒子的搜索模式選擇規則如下:假定信息發布者在t時刻發布信息的聲音強度值是φ(t), 則第i粒子按如下式來調整其搜索模式:

(7)

其中,φ(t)為(0, 1]中的均勻隨機分布, 是信息發布者在t時刻的鳴叫聲(信號)強度值。

3實驗仿真與結果分析

為了驗證本文算法(MMPSO)的性能, 選取比較具有代表性的PSO-w[3]、 CLPSO[16]、 UPSO[19]、 標準PSO與本文算法(MMPSO)進行算法性能比較。 本次實驗采用Matlab 2010a進行編程, 在AMD Athlon(tm) x2(2 CUPs) 3.0 GHz, 2 G RAM平臺進行測試。

3.1測試函數

在本文的數值實驗中, 選用8個比較經典的優化測試基準函數。具體選用的基準測試函數如下(其中搜索空間的維數D=50):

(a)Schwefel’sfunction:

該函數為單峰函數,Schwefel函數在點(0, …, 0)處取得全局唯一極小值是0。

(b)Rastrigin’sfunction:

|xi|≤5.12。

該函數為多峰函數, 它是一個典型的用來測試算法全局搜索性能的函數, 其峰形呈高低起伏不定跳躍性, 在搜索區域內約有10D個局部極小值點, 很難搜索到全局最優值, 該函數在點(0, …, 0)處取得全局極小值是0。

(c)Stepfunction:

該函數為不連續的階梯函數, 在-100≤xi≤100時, 在點(0, …, 0)取得全局極小值0。

(d)Schwefel’sfunction:

該函數為單峰函數, 在點(0, …, 0)處取得全局極小值是0。

(e)Spherefunction:

該函數為單峰函數, 在點(0, …, 0)處取得全局極小值是0。

(f)Griewank’sfunction:

(g)Rotatedhyper-ellipsoidfunction:

該函數是一個單峰函數, 它在點(0, …, 0)處取得全局唯一最小值是0。

(h)Zakharov’sfunction:

-5≤xi≤10。

該函數為單模函數, 它在點(0, …, 0)處取得全局極小值是0。

3.2實驗仿真

為了具有可比性, 在算法數值實驗中, 使5種算法的參數設置盡可能保持一致, 其具體參數設置如下:種群規模都設為30, 加速常數設置為c1=c2=2, 最大迭代次數設置為G=2 000。對于標準PSO、 CLPSO及UPSO 3種算法, 設置w(t)=0.628, 對于PSO-w算法, 則w從0.9線性下降到0.4， 并限定粒子的最大速度vmax≤20%(bj-aj), 其中aj和bj分別為第j維搜索域的下界和上界， 對于本文算法(MMPSO)， 取w(t)=0.9-(0.9-0.4)t/T。

實驗仿真中, 設置算法運行停止條件: 若算法搜索到精確解, 或者算法運行達到最大迭代次數時, 算法停止運行。為了避免隨機性對實驗結果的影響, 每一種算法對每個優化問題均獨立運行30次。記錄最優值、 最差值、 平均值、 標準差、 平均迭代次數等評價指標的實驗數據。 這些評價指標總體上反映了算法的優化能力, 同時也反映了算法計算代價的高低。 表1列出了5種算法獨立運行30次所得到的實驗數據。

對比這5種算法的收斂速度, 5種算法各自獨立運行30次所得到的目標函數最優值(適應度)的平均值的收斂曲線仿真圖3, 圖3a—h為上述5種算法分別對8種優化測試基準函數各自獨立運行30次所得到的目標最優值(適應度)的平均值收斂曲線仿真圖。

表1　實驗結果Table 1　Experiment results

圖3　50維測試函數平均收斂仿真圖Fig.3　Median convergence simulation diagrams of 50D test functions

3.3對比分析

從實驗結果(表1、圖3)可以看出:本文算法(MFPSO)在測試函數f1、f2、f3、f4、f5、f6、f7、f8這8個基準函數的優化問題上, 總體上都具有比標準PSO、PSO-w、CLPSO、UPSO這4種算法更快的全局收斂速度和更好的優化精度;從“標準差”這一評價指標上看, 本文算法(MMPSO)的穩定性比上述4種算法都要好;從“平均迭代次數”評價指標以及仿真圖3上看, 本文算法的收斂速度總體上比上述4種算法都要快。

綜上所述, 本文提出的MFPSO算法改善了PSO算法的優化性能, 與標準PSO、CLPSO、PSO-w以及UPSO 4種算法相比, 其優化性能得到了較大的改善, 在很大程度上克服了標準PSO易陷入局部最優之不足, 在一定程度上避免了PSO算法的早熟收斂現象的出現。

4結束語

針對標準PSO存在的早熟收斂現象, 本文通過增加粒子的搜索模式來增強粒子跳出局部最優的能力和提高粒子的搜索效率。本文選取了8個比較典型的基準函數, 用以測試本文算法(MMPSO)以及標準PSO、CLPSO、PSO-w、UPSO的優化性能。結果表明:本文算法(MMPSO)具有比標準PSO、PSO-w、CLPSO和UPSO 4種算法更快的全局收斂速度、更強的跳出局部最優的能力、更好的全局優化能力和更好的穩定性。

參考文獻:

[1]Kennedy J, Eberhart R. Particle swarm optimization[C]//Proc.of the IEEE International Conference on Neural Networks 1995,IEEE Press,1995:1942-1948.

[2]Shi Y H, Eberhart R. A modified particle swarm optimizer[C]//Procedings of IEEE International Conference on Evolutionary Computation. Piscataway, NJ, USA:IEEE Press, 1998:69-73.

[3]van den Bergh F, Engelbrecht A P. A cooperative approach to particle swarm optimization[J]. IEEE Transactions on Evolutionary Computation, 2004, 8(3): 225-239.

[4]L?pvbjerg M, Rasmussen T K, Krink T. Hybrid particle swarm optimiser with breeding and subpopulations[C]//Proc.Genetic Evol.Comput.Conf., 2001:469-476.

[5]Kennedy J, Mendaes R. Neighborhood topoligies in fully-informed and best-of-neighborhood particle swarms[J].IEEE Transactions on Systems, Man, and Cybernetics, Part C:Application and Reviews, 2006, 36(4):515-519.

[6]Kennedy J, Mendes R. Population structure and particle swarm performance[C]//Proc. of the IEEE Congress on Evolutionary Computation. Honolulu, USA, 2002:1671-1676.

[7]Liang J J,Suganthan P N. Dynamic multi-swarm particle swarm optimizer[C]//Proc. of IEEE Int. Swarm Intelligence Symposium, 2005:124-129.

[8]呂振肅, 侯志榮. 自適應變異的粒子群優化算法[J].電子學報, 2004, 32(3):416-420.

[9]赫然, 王永吉, 王青,等.一種改進的自適應逃逸微粒群算法及實驗分析[J].軟件學報, 2005, 16(12):2036-2044.

[10]陳紅洲, 顧國昌, 康望星. 一種具有感覺的微粒群算法[J]. 計算機研究與發展, 2005, 42(8):1299-1305.

[11]呂艷萍, 李紹滋, 陳水利, 等. 自適應擴散混合變異機制微粒群算法[J]. 軟件學報, 2007, 18(11): 2740-2751.

[12]王輝, 錢峰. 基于慣性權重非線性動態變化的微粒群算法[J]. 計算機科學, 2008, 35(3):146-148.

[13]Jiao B, Lian Z G,Gu X S. A dynamic inertia weight particle swarm optimization algorithm[J].Chaos,Solitons and Fractals,2008, 37(3): 698-705

[14]Ratnaweera A, Halgamuge S K,Watson H C.Self-organizing hierarchical particle swarm optimizer with time-varying acceleration coefficients[J]. IEEE Transactions on Evolutionary Computation,2004, 8 (3): 240-255.

[15]叢琳, 沙宇恒, 焦李成.組織進化粒子群數值優化算法[J].模式識別與人工智能, 2007, 20(2):145-153.

[16]Liang J J,Qin A K,Suganthan P N, et al. Comprehensive learning particle swarm optimizers for global optimization of multimodal functions[J].IEEE Transactions on Evolutionary Computation, 2006, 10(3):67-82.

[17]呂強, 劉士榮, 邱雪娜.基于信息素機制的粒子群優化算法的設計與實現[J].自動化學報, 2009, 35(11):1410-1419.

[18]呂強, 劉士榮. 一種信息充分交流的粒子群優化算法[J]. 電子學報, 2010, 38(3):664-667.

[19]吳曉軍, 楊戰中, 趙明. 均勻搜索粒子群算法[J].電子學報, 2011, 39(6):1261-1266.

[20]魏波, 李元香, 徐星, 等. 基于穩定策略的粒子群優化算法[J].計算機科學, 2011, 38(12):221-223.

[21]董方, 謝磊, 張建明. 基于反饋學習粒子群算法的極值搜索控制[J].上海交通大學學報, 2012, 46(12): 1962-1966.

[22]高哲, 廖曉鐘. 基于平均速度的混合自適應粒子群算法[J].控制與決策, 2012, 27(1):152-155，160.

[23]杜繼永, 張鳳鳴, 李建文, 等. 一種具有初始化功能的自適應慣性權重粒子群算法[J]. 信息與控制, 2012, 41(2):165-169.

[24]喻飛, 李元香, 魏波, 等. 一種基于去個性化理論的粒子群算法[J]. 控制與決策, 2013, 28(10):1520-1524.

[25]朱慶保, 徐曉晴, 朱世娟. 一種新的求解動態連續優化的分層粒子群算法[J]. 控制與決策, 2013, 28(10):1573-1577.

[26]Zhang W J, Xie X F. DEPSO: Hybrid particle swarm with differential evolution operator[C]//IEEE International Conference on System, Man and Cybernetics, 2003:3816-3821.

[27]欒麗君, 譚立靜, 牛奔.一種基于粒子群優化算法和差分進化算法的新型混合全局優化算法[J].信息與控制, 2007, 36 (6):708-714.

[28]彭曉波, 桂衛華, 黃志武, 等. GAPSO:一種高效的遺傳粒子混合算法及其應用[J].系統仿真學報, 2008, 20(18):5025-5027，5031.

[29]高尚, 韓斌, 吳小俊, 等. 求解旅行商問題的混合粒子群優化算法[J].控制與決策, 2004, 19(11):1286-1289.

[30]劉波, 楊路明, 雷剛躍, 等.融合粒子群與蟻群算法優化XML群體智能搜索[J].計算機研究與發展, 2008, 45(8):1371-1378.

文章編號:1674-9057(2016)02-0402-08

doi:10.3969/j.issn.1674-9057.2016.02.036

收稿日期：2015-02-01

基金項目：廣西自然科學基金項目(0832084)；廣西高等學?？蒲许椖?KY2015YB078)

作者簡介：張呈志(1985—)，男，碩士，研究方向：計算智能。

通訊作者：王勇，教授，博士，wangygxnn@sina.com。

中圖分類號：TP18

文獻標志碼：A

Particle swarm optimization by multi-search modes

ZHANG Cheng-zhi, WANG Yong, LI Hai-bin

(a.College of Information Science and Engineering;b.Key Laboratory of Guangxi High School Complex System and Computational Intelligence, Guangxi University for Nationalities,Nanning 530006,China)

Abstract:From inspiration of real birds search-modes,a novel variant particle swarm optimization was proposed,which is called the particle swarm optimization by multi-search modes. In this MMPSO, each particle can use three search-modes to search food in search space, and can adjust its method at any time. Experiments were done on some benchmark functions such as Schwefel function, Rastrigin function, Step function,Sphere function, Griewank function, Rotated hyper-ellipsoid function, and Zakharov function. The experimental results show that the MMPSO has stronger ability to jump out of local optimum and better ability of global optimization than that of the normal PSO, and effectively avoid the premature convergence problem.It can be used to solve the high-dimensional and complex optimization problems.

Key words:particle swarm optimization (PSO);multi-search modes;MMPSO

引文格式：張呈志, 王勇, 李海濱.采用多搜索模式的粒子群算法[J].桂林理工大學學報，2016,36(2):402-409.