分合粒子群優(yōu)化算法

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

關(guān)鍵詞:粒子群優(yōu)化算法; 早熟; 函數(shù)優(yōu)化; 分合策略

中圖分類號: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 引言

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

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

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

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

1 基本粒子群優(yōu)化算法

粒子群優(yōu)化算法是在D維目標搜索空間中，m個粒子組成一個群落，每個粒子i包含一個D維的位置向量Xi=(xi1，xi2，…，xiD)和速度向量Vi=(vi1，vi2，…，viD)。粒子i在搜索解空間時，記住其搜索到的最優(yōu)位置Pi，在每次迭代中，粒子i根據(jù)自身慣性、自身最優(yōu)Pi=(pi1，pi2，…，piD)和群體最優(yōu)Pg=(pg1，pg2，…，pgD)調(diào)整自己的速度向量，進而調(diào)整自身位置。本文在此介紹帶有慣性權(quán)重的粒子群優(yōu)化算法，用下式更新粒子狀態(tài)[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是非負常數(shù)，r1和r2是取值介于(0，1)的隨機數(shù)。 vid∈[-vmax， vmax]，vmax、ω是常數(shù)，迭代終止條件根據(jù)具體問題來設(shè)定。

2 分合粒子群優(yōu)化算法

分合策略利用人類社會系統(tǒng)中“分久必合，合久必分”的普遍規(guī)律，表1定義了該規(guī)律與分合策略的對應關(guān)系。

表1 社會系統(tǒng)普遍規(guī)律與分合策略的對比關(guān)系

社會系統(tǒng)分合策略 社會系統(tǒng)分合策略

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

h)輸出解，結(jié)束。

3 實驗與分析

3.1 實驗函數(shù)

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

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 算法設(shè)置與實驗結(jié)果

本文的分合粒群優(yōu)化算法有如下設(shè)置:

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

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

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

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

表2 三種算法的實驗結(jié)果對比

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可以明顯地看出，不論是多峰還是單峰函數(shù)，本文的PSODU比BPSO和HPSO具有更好的收斂精度、更好的穩(wěn)定性，突顯了新算法的優(yōu)勢。

4 結(jié)束語

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

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

參考文獻:

[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.