解決全局優化問題的粒子群進化算法

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

關鍵詞：粒子群算法；變異;全局優化；概率

中圖分類號：TP311 文獻標識碼：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年提出的一種新型智能群體計算方法^[1，2]，其源于對鳥類覓食行為的研究。目前粒子群優化算法已經成功地應用于系統識別^[3]，神經網絡訓練^[4]等領域，但是將PSO與進化算法相結合應用于復雜優化問題中的研究還很少^[5]。

在科學研究中，許多問題最終都歸結為帶有約束的函數優化問題：

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

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

本文通過設計新的變異算子，使得粒子能夠在整個空間搜索，有了能找到目標函數值更小的點；在粒子群進化過程中，使用歸檔策略，保留了較好粒子，提高了收斂速度。仿真結果表明對于復雜優化問題，該算法尋優性能優良。

2 粒子群進化算法

2.1 PSO的基本原理

PSO(粒子群優化算法)是Kennedy和Eberhart發明的一種新的全局優化進化算法，他源于對鳥類捕食行為的模擬^[1，2]。標準粒子群算法的進化方程為：

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)進行變異后的個體記作z，z=x+λ(t)B(x);λ(t)為一個遞減函數，t為循環的代數。在本文中，λ(t)=1/t，設計這樣一個遞減函數可以在進化前期沿著搜索方向進行大范圍的搜索，進化后期在最優點附近進行小范圍局部搜索。

由此可見，當個體沿著該搜索方向進行變異時，很可能會產生更好的解。因此，把合力方向作為搜索方向是有利于函數值下降的。

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

2.3 粒子群進化算法流程

粒子群進化算法流程為：

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

（2） 將粒子的pbest設置為當前位置，gbest設置為初始群體中最佳粒子的位置；

（3） 判斷算法停止準則是否滿足，如果滿足，轉向（8）；否則執行（4）；

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

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

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

（7） 判斷算法停止準則是否滿足，如果滿足轉向（8）;否則轉向（4）；

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

3 數值模擬

為了驗證算法(PSOEA)的有效性，本文選擇文獻［8］中的9個標準無約束全局優化測試函數。對這9個測試函數，用本文算法進行計算，并與文獻［8］中的方法CEP，FEP的計算結果做了比較。結果見表1。 

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

計算中對每個問題獨立運行50次，記錄50次所得函數最優值的平均值（Mean Best），標準差(Standard Deviation，Std.Dev)及每個問題的最大迭代次數(Number of Generations)。

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

4 收斂性分析

在本節，做如下假設：

假設（A）：

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

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

(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或對ω>0，有P{∩∞i=1[DD)]∪[DD(X]K≥iDK≥ε}=0則稱算法的概率1收斂于全局最優解。其中，P{A}表示A發生的概率，x*(k)為第k代中最好點。

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

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

②對任一個處于狀態S2的P(K)，存在一個常數C∈(0，1)，使P22

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

證明：對ε>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

此即證明結論。

參 考 文 獻

［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，Feng 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].吉林大學學報，2005，43(4):472-476

［6］魏靜萱，王宇平.解決全局優化問題的幾種進化算法［D］.西安:西安電子科技大學，2006.

［7］王麗，劉玉樹.基于在線歸檔技術的多目標粒子群算法［J］.北京理工大學學報，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.

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