分合粒子群優化算法

摘 要:基于社會系統中普遍存在“分久必合，合久必分”的現象，提出了基于分合思想的粒子群優化算法。分策略提高了演化群體的多樣性，克服了粒子群優化算法局部收斂的缺陷。合策略吸取了不同群體的優良特性，提高了算法的全局搜索能力。函數優化的仿真結果證明了算法的有效性。

關鍵詞:粒子群優化算法; 早熟; 函數優化; 分合策略

中圖分類號:TP301.6文獻標志碼:A

文章編號:1001-3695(2010)06-2024-02

doi:10.3969/j.issn.1001-3695.2010.06.006

Particle swarm optimization based on division and union strategy

CHEN Jian-chao1， HU Gui-wu1，2，3

(1. School of Mathematics Computational Science， Guangdong University of Business Studies， Guangzhou 510320， China; 2. Key Laboratory of Data Engineer Knowledge Engineer for Ministry ofEducation， Beijing 100872， China; 3. School of Information， Renmin University of China， Beijing 100872， China)

Abstract:Basing on a ubiquitous scheme:the world， long divided， must reunite; long united， must divide， which was reported to well represent the nature of social evolution process， this paper proposed divided and united particle swarm optimization. In the new algorithm， division strategy was able to improve the diversity of population， which overcame the local convergence of PSO.Union strategy was able to combine the merit of different population and improved its global research ability. Finally， used the novel algorithm to solve function optimization problem. The result shows that the algorithm is effective.

Key words:particle swarm optimization; premature; function optimization; division and union strategy

0 引言

在人類社會發展長河中，人總是不停地經歷著分與合的運動。遠古時期，為了壯大生存的力量，相近或相似的個體自然地合在一塊，成為一個群體。當這個群體發展到一定的階段，由于生存條件的局限，這個群體不得不分開成為幾個群體，獨立地去尋找生存的機會;當分開到一定的時間后，為了克服暫時的惡劣自然環境或復雜的社會環境，不得不走向合的道路。簡單地講，人類的歷史是一個不停地“分久必合，合久必分”的歷史，對智能優化算法和“分久必合，合久必分”規律的研究表明，兩者存在一定的關聯，文中面向智能算法提出了分和合兩種策略。

粒子群優化算法(particle swarm optimization，PSO)是由Kennedy等人[1]在1995年提出的一種全新的全局優化技術。近年來， 該算法作為一種新興的演化計算技術，已成為越來越多研究者的關注焦點，已經成功地用于多目標優化、模式辨識、信號處理和決策支持[2，3]等領域。

很多研究者對基本的PSO算法作了各種改進。文獻[4]采用模糊規則動態修改ω值，使算法自適應地調整全局系數，兼顧了搜索效率和搜索精度。Angeline等人[5]借鑒遺傳算法思想提出雜交PSO 算法概念，提高了算法的收斂速度和精度。LV Zhen-su等人[6]根據粒子群適應度方差作為全局最優化變異條件，提出自適應變異的粒子群優化算法。Bergh等人[7]提出協同PSO，使粒子更容易跳出局部極小點，達到較高收斂精度，但出現了明顯的啟動延遲現象，在迭代初期減緩了收斂速度。Ratnaweera 等人[8]在自組織算法的基礎上給出了一種變異操作隨時間變化的自適應層次PSO 算法(hierarchical particle swarm optimizer，HPSO)，以進一步提高搜索性能，并給出了適合變異操作的自適應參數選擇方式。但HPSO 算法消除了速度公式中的慣性部分，其發生變異的條件是微粒速度為0，使微粒不能快速、有效地逃出局部極小點。其他一些工作[9]也分別對基本PSO算法作了一些局部改進。

針對PSO算法容易出現早熟，甚至陷入局部最優的問題，筆者在充分理解社會進化過程中的一個普遍規則“分久必合，合久必分”的基礎上，提出了分合粒子群優化算法(PSODU)，克服了粒子群優化算法局部極值問題，提高了其全局搜索能力。

1 基本粒子群優化算法

粒子群優化算法是在D維目標搜索空間中，m個粒子組成一個群落，每個粒子i包含一個D維的位置向量Xi=(xi1，xi2，…，xiD)和速度向量Vi=(vi1，vi2，…，viD)。粒子i在搜索解空間時，記住其搜索到的最優位置Pi，在每次迭代中，粒子i根據自身慣性、自身最優Pi=(pi1，pi2，…，piD)和群體最優Pg=(pg1，pg2，…，pgD)調整自己的速度向量，進而調整自身位置。本文在此介紹帶有慣性權重的粒子群優化算法，用下式更新粒子狀態[1]:

Vi(t+1)=ωVi(t)+c1r1(Pi-Xi(t))+c2r2(Pg-Xi(t))(1)

Xi(t+1)=Xi(t)+Vi(t+1)(2)

i=1，2，…，n;d=1，2，…，D

其中:c1和c2是非負常數，r1和r2是取值介于(0，1)的隨機數。 vid∈[-vmax， vmax]，vmax、ω是常數，迭代終止條件根據具體問題來設定。

2 分合粒子群優化算法

分合策略利用人類社會系統中“分久必合，合久必分”的普遍規律，表1定義了該規律與分合策略的對應關系。

表1 社會系統普遍規律與分合策略的對比關系

社會系統分合策略 社會系統分合策略

社會群體種群{X1X2…Xn}合久必分分策略

群體成員種群個體Xk分久必合合策略

定義1 分策略。已知在D維目標搜索空間中，若干個個體組成一個種群，每個個體i包含一個D維的位置向量Xi，當種群在進化過程中陷入局部最優，則種群按一定的機制分成若干個子群，每個子群在一定的機制下向某一個方向移動。

定義2 合策略。已知在D維目標搜索空間中，若干個種群，各個種群在進化過程中都陷入局部最優之后，讓每個種群按一定的機制選擇部分個體組合成為一個全新的種群，通常該種群規模不變。

針對粒子群優化算法陷入局部極值的固有弱點，本文把上面的分策略和合策略融入到粒子群優化算法。當PSO算法陷入局部最優時，種群分為若干個子群，獨立擴充規模，獨立進化，提高了群體的多樣性。當每個種群陷入局部最優時，每個子種群選出部分個體合成一個新的種群，提高算法的全局尋優能力。由此得到分合粒子群優化算法(PSODU)，算法的具體流程如下:

a)初始化粒子群，即隨機設定各粒子的初始位置X和初始速度V。

b)計算每個粒子的適應值。

c)對于每個粒子，將其適應值與其所經歷過最好位置Pi的適應值進行比較，若較好，則將其作為當前的最好位置。

d)對于每個粒子，將其所經歷過最好位置Pi的適應值與群體所經歷過的全局最好位置Pg的適應值進行比較，若較好，則將其作為群體當前的全局最好位置。

e)根據式(1)和(2)修改各個粒子的速度和位置。

f)如果算法陷入局部最優，不滿足停止準則，則執行定義1的分策略:

(a)將原種群分為若干個子群，讓每個子群獨立擴大規模到原種群的規模;

(b)執行并行策略，每一個種群獨立執行基本粒子群體優化算法直到陷入局部極值，如果不滿足停止準則，則轉g)。

g)執行定義2的合策略:

(a)每個子群按一定的機理選擇部分個體，組合成為一個新種群，規模不變;

(b)在新種群中執行粒子群優化算法直到陷入局部極值，如果不滿足停止準則，則轉f)，否則轉h)。

h)輸出解，結束。

3 實驗與分析

3.1 實驗函數

為了驗證改進算法的性能，選用了以下四個常用的非線性基準函數:

a)function f1(n=30)

f1=∑ni=1x2i，-100≤xi≤100，min(f(x))=0

b)function f2(n=30)

f2=14000∑ni=1x2i-∏ni=1cosxii+1

-600≤xi≤600，min(f(x))=0

c)function f3

f3=0.5+sin(x2+y2)-0.5(1.0+0.001(x2+y2))2-100≤x，y≤100，min(f(x))=0

d)function f4

f(x，y)={∑5i=1icos[(i+1)x+i]}{∑5i=1icos[(i+1)y+1]}+0.5[(x+1.42513)2+(y+0.80032)2]-100≤x，y≤100，min(f(x))=-186.7309

3.2 算法設置與實驗結果

本文的分合粒群優化算法有如下設置:

a)分策略。把種群規模設置為30，分為四個子群，每一子群獨立地向四個不同的方向移動，然后再隨機生成一部分個體，使得每個子群規模達到30。

b)合策略。從四個種群選擇部分最優秀和最差的個體，合成規模為30。

c)式(1)中，c1、c2和ω的分別取2、2和0.8。

d)本文的實驗主要是與基本粒子群優化算法[1](標記為BPSO)和文獻[2]中的混合粒子群優化算法比較(標記為HPSO)，算法的適應值函數F(x)=log(f(x)-最優值)，適應值最低只取到-20，各個算法都執行3 000次迭代，并分別重復運行100次，最后分別統計三個算法的最好尋優結果、平均尋優結果和最差尋優結果。表2是三種算法的實驗結果對比情況。

表2 三種算法的實驗結果對比

functionresult

algorithms

BPSOPSODUHPSO

f1fitnessbestavgworst-20.0000-19.2752-4.9674-20.0000-20.0000-20.0000-20.0000-13.9035-4.4006

f2fitness

bestavgworst-20.0000-7.7499-1.1491-20.0000-16.4916-8.2758-20.0000-6.9371-0.9753

f3fitnessbestavgworst-20.0000-16.0427-2.0125-20.0000-20.0000-20.0000-20.0000-16.2824-2.0125

f4fitnessbestavgworst-8.0468-3.14551.6005-8.0468-7.4357-0.4086-8.0468-2.72941.5962

從表2可以明顯地看出，不論是多峰還是單峰函數，本文的PSODU比BPSO和HPSO具有更好的收斂精度、更好的穩定性，突顯了新算法的優勢。

4 結束語

本文主要工作是分、合策略的設置，得到

了一種新算法——分合粒子群優化算法，它克服了算法出現早熟現象， 提高了算法全局搜索能力。嚴格地講，該算法是一種新的范式，目前筆者在國內外文獻中還沒有發現。該范式可以與任何一種智能算法結合，從理論和實際上來講都有很大的探索空間，但本文只局限于實驗階段，缺乏理論的研究，這些是筆者未來努力的方向。

參考文獻:

[1]KENNEDY J， EBERHART R C. Particle swarm optimization[C]//Proc of IEEE International Conference on Neural Networks. Piscataway:IEEE Press，1995:1942-1948.

[2]LOVBJERG M，RASMUSSEN T K，KRINK T.Hybrid particle swarm optimizer with breeding and subpopulations[C]//Proc of the 3rd Genetic and Evolutionary Computation Conference. San Francisco:[s.n.]，2001:469-476.

[3]HU Wang， LI Zhi-shu. A simpler and more effective particle swarm optimization algorithm [J]. Journal of Software，2007，18(4):861-868.

[4]SHI Yu-hui， EBERHART R C. Fuzzy adaptive particle swarm optimization[C]//Proc of Congress on Evolutionary Computation. Piscataway:IEEE Press，2001:101-106.

[5]ANGELINE P J. Evolutionary optimization versus particle swarm optimization:philosophy and performance differences[C]//Proc of the 7th Annual Conference on Evolutionary Programming. Berlin:Sprin-ger-Verlag，1998:601-610.

[6]LV Zhen-su， HOU Zhi-rong. Particle swarm optimization with adaptive mutation[J]. Acta Electronica Sinica，2004，32(3):416-420.

[7]van den BERGH F， ENGELBRECHT A P. Cooperative learning in neural networks using particle swarm optimizers[J]. South African Computer Journal，2000，26(11):84-90.

[8]RATNAWEERA A， HALGAMUGE S K， WATSON H C. Self-organizing hierarchical particle swarm optimizer with time-varying acceleration coefficients[J]. IEEE Trans on Evolutionary Computation，2004，8(3):240-255.

[9]SHARMA K D， CHATTERJEE A， RAKSHIT A A. A hybrid approach for design of stable adaptive fuzzy controllers employing lyapunov theory and particle swarm optimization[J]. IEEE Trans on Fuzzy Systems，2009，17(2):329-341.