摘 要：針對復(fù)雜全局優(yōu)化問題，提出一種粒子群進(jìn)化算法(PSOEA)。針對粒子群算法容易陷入局部最優(yōu)等缺點(diǎn)，設(shè)計(jì)一個(gè)新的變異算子，使得粒子能夠在整個(gè)空間進(jìn)行搜索，同時(shí)保證了算法的收斂性。用概率論的有關(guān)知識證明了算法的收斂性。仿真結(jié)果表明，對于全局優(yōu)化問題，算法尋優(yōu)性能優(yōu)良，特別是對于超高維優(yōu)化問題，該算法能獲得更高精度的解。

關(guān)鍵詞：粒子群算法；變異;全局優(yōu)化；概率

中圖分類號：TP311 文獻(xiàn)標(biāo)識碼：B

文章編號：1004-373X(2008)10-120-03

A Particle Swarm Evolutionary Algorithm for Solving Global Optimization Problems

BAI Xuying1，2，YANG Youlong2

(1.College ofScience，Northwest AF University，Xi′an，712100，China;2.College of Science Xidian University，Xi′an，710071，China)

Abstract： A particle swarm evolutionary algorithm for solving global optimization is proposed.Firstly，a new mutation operator is proposed in order to escape from the local optimum.Meanwhile，the convergence of algorithm can be ensured.Finally，the convergence of this algorithm is proved based on the probability.The simulation results show that the algorithm is effective for global optimization problems with high dimension.

Keywords：particle swarm optimization;mutation;global optimization;probability

1 引 言

微粒群算法(PSO)是Kennedy與Eberhart于1995年提出的一種新型智能群體計(jì)算方法^[1，2]，其源于對鳥類覓食行為的研究。目前粒子群優(yōu)化算法已經(jīng)成功地應(yīng)用于系統(tǒng)識別^[3]，神經(jīng)網(wǎng)絡(luò)訓(xùn)練^[4]等領(lǐng)域，但是將PSO與進(jìn)化算法相結(jié)合應(yīng)用于復(fù)雜優(yōu)化問題中的研究還很少^[5]。

在科學(xué)研究中，許多問題最終都?xì)w結(jié)為帶有約束的函數(shù)優(yōu)化問題：

minx∈［L，U］f(x)[JY](1)

x=(x1，x2，…，xn)是決策變量；f(x)是目標(biāo)函數(shù)，其中:超立方體［L，U］={x=(x1，x2，…，xn)|li≤xi≤ui，i=1，2，…，n}為問題的搜索空間，［li，ui］為可行解x的第i個(gè)分量xi化區(qū)間，n為優(yōu)化變量數(shù)目。

本文通過設(shè)計(jì)新的變異算子，使得粒子能夠在整個(gè)空間搜索，有了能找到目標(biāo)函數(shù)值更小的點(diǎn)；在粒子群進(jìn)化過程中，使用歸檔策略，保留了較好粒子，提高了收斂速度。仿真結(jié)果表明對于復(fù)雜優(yōu)化問題，該算法尋優(yōu)性能優(yōu)良。

2 粒子群進(jìn)化算法

2.1 PSO的基本原理

PSO(粒子群優(yōu)化算法)是Kennedy和Eberhart發(fā)明的一種新的全局優(yōu)化進(jìn)化算法，他源于對鳥類捕食行為的模擬^[1，2]。標(biāo)準(zhǔn)粒子群算法的進(jìn)化方程為：

V[WB](t+1)=ω#8226;V(t)+c1#8226;rand#8226;(pbest(t)－x(t))+

B(x)=(B1，B2，…，Bn)

Bi=∑y∈pop(t)yi－xi‖y－x‖(ui－li)exp［f(y)－f(x)］－1exp［f(y)－f(x)］+1，

i=1，2，…，n 

x沿著合力搜索方向B(x)進(jìn)行變異后的個(gè)體記作z，z=x+λ(t)B(x);λ(t)為一個(gè)遞減函數(shù)，t為循環(huán)的代數(shù)。在本文中，λ(t)=1/t，設(shè)計(jì)這樣一個(gè)遞減函數(shù)可以在進(jìn)化前期沿著搜索方向進(jìn)行大范圍的搜索，進(jìn)化后期在最優(yōu)點(diǎn)附近進(jìn)行小范圍局部搜索。

由此可見，當(dāng)個(gè)體沿著該搜索方向進(jìn)行變異時(shí)，很可能會(huì)產(chǎn)生更好的解。因此，把合力方向作為搜索方向是有利于函數(shù)值下降的。

為了避免粒子朝著某一個(gè)方向“飛行”對變異后的粒子進(jìn)行二次高斯變異：xi=xi+σ#8226;N(0，1)。

2.3 粒子群進(jìn)化算法流程

粒子群進(jìn)化算法流程為：

（1） 隨機(jī)初始化粒子群pop(t)中粒子的位置與速度；

（2） 將粒子的pbest設(shè)置為當(dāng)前位置，gbest設(shè)置為初始群體中最佳粒子的位置；

（3） 判斷算法停止準(zhǔn)則是否滿足，如果滿足，轉(zhuǎn)向（8）；否則執(zhí)行（4）；

（4） 對所有粒子按式(2)，(3)進(jìn)化，得進(jìn)化后種群pop′(t)；

（5） 對pop′(t)中的粒子按第2.2節(jié)方法進(jìn)行變異得pop(t+1)；

（6） 更新pop(t+1)中每個(gè)粒子所經(jīng)歷的最好位置，及全局最優(yōu)位置，令t=t+1；

（7） 判斷算法停止準(zhǔn)則是否滿足，如果滿足轉(zhuǎn)向（8）;否則轉(zhuǎn)向（4）；

（8） 輸出gbest，算法停止。

3 數(shù)值模擬

為了驗(yàn)證算法(PSOEA)的有效性，本文選擇文獻(xiàn)［8］中的9個(gè)標(biāo)準(zhǔn)無約束全局優(yōu)化測試函數(shù)。對這9個(gè)測試函數(shù)，用本文算法進(jìn)行計(jì)算，并與文獻(xiàn)［8］中的方法CEP，F(xiàn)EP的計(jì)算結(jié)果做了比較。結(jié)果見表1。 

在運(yùn)行PSOEA時(shí)參數(shù)取下值:種群規(guī)模N為100;第1次變異概率pm1=0.3；第2次變異概率pm2=0.1；粒子群算法中的參數(shù)參照文獻(xiàn)［1］；算法終止條件為：f1~f6進(jìn)化達(dá)到指定的代數(shù)100，f7~f9進(jìn)化達(dá)到指定的代數(shù)4 000。

計(jì)算中對每個(gè)問題獨(dú)立運(yùn)行50次，記錄50次所得函數(shù)最優(yōu)值的平均值（Mean Best），標(biāo)準(zhǔn)差(Standard Deviation，Std.Dev)及每個(gè)問題的最大迭代次數(shù)(Number of Generations)。

從表1可以看出，對所有的9個(gè)測試函數(shù)，在進(jìn)化代數(shù)相同的情況下，PSOEA所得函數(shù)最優(yōu)值的平均值均好于（至少不差于）CEP和FEP對這些問題所求出的最優(yōu)解，而且PSOEA所求出的所有解均很接近于真正的最優(yōu)解，而CEP和FEP對有些問題所求的解與真正的最好解有一定的差距。比如f1，真正最優(yōu)解為min(f1)1，而CEP求出的平均最好值為1.66，對f5，真正的最優(yōu)解為min(f5)0，而CEP所求出的解為4.08.從標(biāo)準(zhǔn)方差來看，對f1，PSOEA每次都能找到最優(yōu)點(diǎn)0.997 5，而FEP和CEP相差很多。對f2和f4，雖然FEP和CEP所求的標(biāo)準(zhǔn)差稍小于PSOEA的標(biāo)準(zhǔn)差，但是PSOEA所求出的平均最優(yōu)值要好于CEP和FEP所求出的結(jié)果。對f3，不論是PSOEA所求出的標(biāo)準(zhǔn)差還是平均最優(yōu)值都要優(yōu)于FEP所求出的結(jié)果。對f5和f6~f9，PSOEA所求出的標(biāo)準(zhǔn)差和平均最優(yōu)值都要優(yōu)于CEP和FEP所得結(jié)果。因此，PSOEA有較好的穩(wěn)定性。 由表1可以看出，本文算法能迅速而較精確地找到全局最優(yōu)解，另外值得提出的是，有些函數(shù)PSOEA仍可以繼續(xù)下降，但為了和FEP，CEP的進(jìn)化代數(shù)相同，中途人為停止。

4 收斂性分析

在本節(jié)，做如下假設(shè)：

假設(shè)（A）：

(1) 問題（1）的可行域D是Rn中一個(gè)有界閉集；

(2) f(x)在［L，U］D上連續(xù)；

(3) 對γ>0，及x*∈D，有M(Nγ(x*)∩D)>Cγ>0，其中M(Nγ(x*)∩D)表示集合Nγ(x*)∩D的Lebesgue測度，Nγ(x*)={x∈Rn:x－x*≤γ}。

[HTH]定義 1 令Dk=|f(x*(k))－f*|， 若P{limx→∞ D=0}=1或?qū)Κ笑?gt;0，有P{∩∞i=1[DD)]∪[DD(X]K≥iDK≥ε}=0則稱算法的概率1收斂于全局最優(yōu)解。其中，P{A}表示A發(fā)生的概率，x*(k)為第k代中最好點(diǎn)。

定理 1 若Pij(i，j=1，2)表示P(k)處于狀態(tài)Si，而P(K+1)處于狀態(tài)Sj的概率，則在假設(shè)(A)下有:

①對任一個(gè)處于狀態(tài)S1的P(K)，必有P11=1；

②對任一個(gè)處于狀態(tài)S2的P(K)，存在一個(gè)常數(shù)C∈(0，1)，使P22

定理2 設(shè){P(K)}是由PSOEA算法產(chǎn)生的種群序列，且P(0)中至少有一點(diǎn)屬于D (實(shí)際上，只要K0，使P(K0)中有一點(diǎn)屬于D即可)，記x*(k)=argmin {f(x)x∈P(k)∩D}，則在假設(shè)(A)下，有P{limk→∞ f(x*(k))=f*}=1，即算法以概率1收斂到全局最優(yōu)解。

證明：對ε>0，記pk=P{f(x*(k))－f*≥ε}

Pk=0，若m∈{1，2，…，k}，使x*(m)∈Q1

k若對t∈{1，2，…，k}，有x*(t)∈Q2 

由定理1知：k=P{x*(t)∈Q1，t=(1，2，…，k)}=Pk22≤Ck

∴ ∑∞k=1Pk≤∑∞k=1k≤∑∞k=1Ck=C1－C<∞

由Borel-Canteli 引理知:

P{∩∞i=1[DD)]∪[DD(X]K≥i{|f(x*(k))－f*|≥ε}=0

此即證明結(jié)論。

參 考 文 獻(xiàn)

［1］Kennedy I，Eberhart R C.Particle Swarm Optimization ［A］.Proc.IEEE Int.Conf.on Neural Networks ［C］.Perth，WA，Australia，1995:1 942-1 948.

［2］Shi Y，Eberhart R C.A Modified Swarm Optimizer［A］.IEEE International Conference of Evolutionary Computation ［C］.Anchorage，Alaska，1998:125-129.

［3］Voss M S，F(xiàn)eng Xin.A RMA Model Selection Using Particle Swarm Optimization and AIC Criteria ［A］.15th Triennial World Congress ［C］.Barcelona，Spain:IFAC，2002:41-45.

［4］Bergh F，Engelbrecht A P.Cooperative Learning in Neural Networks Using Particle Swarm Optimizers ［J］.South African Computer Journal， 2000，11(6)：84-90.

［5］劉華璽，林玉娥.粒子群算法的改進(jìn)及其在求解約束優(yōu)問題中的應(yīng)用[J].吉林大學(xué)學(xué)報(bào)，2005，43(4):472-476

［6］魏靜萱，王宇平.解決全局優(yōu)化問題的幾種進(jìn)化算法［D］.西安:西安電子科技大學(xué)，2006.

［7］王麗，劉玉樹.基于在線歸檔技術(shù)的多目標(biāo)粒子群算法［J］.北京理工大學(xué)學(xué)報(bào)，2006，26(10):883-886.

［8］Yao Xin，Liu Yong，Lin Guangming.Evolutionary Programming Made Faster[J].IEEE Trans.on Evolutionary Computation，1999，3(2):82-102.

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文。