一種基于鄰域空間的混合粒子群優(yōu)化算法

曾 毅，朱旭生，廖國勇

（華東交通大學基礎(chǔ)科學學院，江西南昌 330013）

粒子群優(yōu)化算法（particle swarm optimization，PSO）是Eberhart和Kennidy1995年開發(fā)的一種新的群體智能計算技術(shù)［1-2］，源于對鳥群捕食的行為研究。由于PSO算法概念簡單，容易實現(xiàn)，只有少數(shù)參數(shù)需要調(diào)整，所以自其被提出以來受到學術(shù)界的重視和研究，并廣泛地應(yīng)用于函數(shù)優(yōu)化、神經(jīng)網(wǎng)絡(luò)訓練、模糊系統(tǒng)控制等領(lǐng)域。

PSO算法是屬于有導向的隨機性啟發(fā)式算法。盡管在求解大多數(shù)優(yōu)化問題時表現(xiàn)出色，但在求解高維復雜函數(shù)優(yōu)化問題時，極易陷入局部最優(yōu)解，進化后期收斂速度及解的精度也不夠理想。為此許多學者提出了不少改進算法，Shi和Eberhart提出了慣性權(quán)重方法［3-4］，用慣性權(quán)重ω來控制前面的速度對當前速度的影響，較大的ω可以加強PSO算法的全局搜索能力，而較小的ω能加強PSO算法的局部搜索能力。該方法加快了收斂速度，提高了PSO算法的性能。但當待解問題很復雜時，在迭代后期全局搜索能力不足，導致不能找到要求的最優(yōu)解。Clerc提出收縮因子概念［5］，通過引入收縮因子χ，可以有效地控制慣性權(quán)重ω和學習因子c1，c2，以確保算法收斂。Kennedy等［6-7］提出幾種基本的鄰域結(jié)構(gòu)及鄰域的動態(tài)選擇策略，結(jié)果表明鄰域結(jié)構(gòu)影響算法的性能。Ratnaweera等［8］為改善算法的性能，提出了學習因子c1，c2隨時間動態(tài)線性調(diào)整的策略。文獻［9-10］將求解無約束最優(yōu)化問題的直接法嵌入粒子群優(yōu)化算法中，加快了算法的收斂速度，提高了解的質(zhì)量。本文引入鄰域空間概念，提出一種基于鄰域空間的混合粒子群優(yōu)化算法（hy?brid particle swarm optimization），該算法提出新的粒子速度更新方程，給出學習因子c1，c2非線性調(diào)整策略及局部搜索算法嵌入粒子群優(yōu)化算法的新方法。數(shù)值模擬表明新的算法很好地平衡了算法的全局“探索”與局部“開發(fā)”，在避免早熟現(xiàn)象的發(fā)生、改善迭代后期的收斂速度和解的精度效果明顯。

1 標準粒子群優(yōu)化算法

式（1）（2）為標準粒子群優(yōu)化算法的在第d(d=1，2，…，n)維上的速度和位置更新方程。

其中：k為進化代數(shù),表示粒子xi在第k代d維上的速度；表示粒子xi在第k代d維上的位置；pbesti表示粒子xi所經(jīng)歷的最好位置；gbest表示群體中所有粒子所經(jīng)歷的最好位置；c1，c2為學習因子，且取非負常數(shù)；rand( )是均勻分布于[0，1]之間的隨機數(shù)；ω為慣性權(quán)重，它決定了粒子先前速度對當前速度的影響程度，從而起到平衡算法全局和局部搜索能力的作用。

2 基于鄰域空間的混合粒子群優(yōu)化算法

2.1 算法思想

粒子間的信息共享是PSO算法的基礎(chǔ)，而利用哪些信息，如何利用信息則是信息共享機制的核心問題。在標準粒子群優(yōu)化算法中，所有粒子進化過程中僅共享當前種群中最優(yōu)粒子的信息，而忽略了其它次運行獲得的最優(yōu)信息。這種信息共享策略使算法在進化后期局部開發(fā)能力較強，而全局探索的能力卻較弱。一旦粒子趕上種群最優(yōu)，粒子會聚集到相同位置并停止移動，種群的多樣性會逐漸喪失，從而導致“早熟”現(xiàn)象的發(fā)生。粒子在尋求共同認識的過程中，粒子會保留自己的最佳信息，也應(yīng)考慮同伴的信息，當粒子獲得優(yōu)于自己的同伴信息時，就會參考同伴信息，更新自己的最佳信息。這表明粒子的同伴信息的共享可提供了進化的優(yōu)勢?；谝陨戏治?，我們先給出鄰域空間概念，然后提出新的更能反映信息共享機制的粒子速度更新方程以及局部優(yōu)化算法嵌入粒子群優(yōu)化算法的新方法。

定義1在第k代粒子群中，與粒子xi歐氏距離最近的num個粒子的集合稱為粒子xi的鄰域空間［12］。

定義2在第k代粒子群中，隨機選擇的num個粒子的集合稱為粒子xi的鄰域空間［12］。

本文將粒子xi速度更新方程修改：

嶺南建筑在色彩選擇上往往喜愛用比較明朗的淺色淡色，同時又喜用青、藍、綠等純色作為色彩基調(diào)，這些都能使建筑物減少重量感，從而造成建筑外貌的輕巧。同時從嶺南傳統(tǒng)建筑的裝飾、裝修、紋樣、圖案中，提取符號，再將其抽象化，運用到建筑設(shè)計中。

其中：plbesti為粒子xi迄今為止所搜索到的最好的鄰域極值；c1，c2仍稱為學習因子，且學習因子c1，c2隨著進化代數(shù)k變化。學習因子c1，c2的取值如下

其中：run_max為算法迭代的總次數(shù)，s可取大于1的整數(shù)，本文取s=5。在整個迭代過程中，學習因子c1從2.5非線性逐漸遞減至0.5，而學習因子c2從0.5非線性逐漸遞增至2.5。迭代初期，學習因子c1取值較大，學習因子c2取值較小，算法強調(diào)粒子共享鄰域空間的局部信息，體現(xiàn)局部優(yōu)化的特性；而在進化的后期，學習因子c1取值較小，學習因子c2取值較大，算法強調(diào)粒子共享種群中最優(yōu)粒子的信息，體現(xiàn)全局優(yōu)化的特性。

2.2 模式搜索算法

在智能優(yōu)化算法研究中，人們發(fā)現(xiàn)單靠一種算法往往無法保持探測（exploration）和開發(fā)（exploitation）的平衡，從而影響了算法的性能，所以人們想到了將兩種算法或者多種算法混合在一個模型當中，使混合的算法能充分發(fā)揮各種算法的優(yōu)點，起到提升算法的性能的目的。

模式搜索算法由Hooke和Jeeves于1961年提出的，一種不需要計算導數(shù)的無約束最優(yōu)化的直接算法［13］。算法主要由探測移動和模式移動過程組成，探測移動是沿坐標軸方向的移動，模式移動則是沿相鄰兩個探索點連線方向上移動，兩種移動交替進行，順著函數(shù)值下降的最佳方向搜索到函數(shù)的最小值。模式搜索算法的步驟［14］：

Step1：給定初始點x(1)∈Rn，n個坐標方向e1，e2，…，en，初始步長δ，加速因子α≥1，縮減率β∈(0，1)，允許誤差ε＞0 ，置y(1)=x(1)，k=1，j=1；

Step2：如果f(y(j)+δej)＜f(y(j))，則令y(j+1)=y(j)+δej，進行Step4；否則，進行Step3；

Step3：如果f(y(j)-δej)＜f(y(j))，則令y(j+1)=y(j)-δej，進行Step4；否則，令y(j+1)=y(j)+δej，Step4；

Step4：如果j＜n，則置j:=j+1，轉(zhuǎn)Step2；否則，進行Step5；

Step5：如果f(y(n+1))＜f(x(k))，則進行Step6；否則，進行Step7；

Step6：置x(k+1)=y(n+1)，令y(1)=x(k+1)+α(x(k+1)-x(k))，置k:=k+1，j=1，轉(zhuǎn)Step2；

Step7：如果δ≤ε，則停止迭代，得點x(k)；否則，置δ:=βδ，y(1)=x(k)；

x(k+1)=x(k)，置k:=k+1，j=1，轉(zhuǎn)Step2。

如何使混合優(yōu)化算法能充分發(fā)揮模式搜索算法強大的局部“開發(fā)”能力，又有效地克服模式搜索算法對初始值敏感、易陷入局部最優(yōu)的缺點。目前，通用的一個做法是以最優(yōu)粒子為初值進行模式搜索，并將搜索到的新位置替代粒子原來位置，但這種算法對高維多峰函數(shù)優(yōu)化問題的全局尋優(yōu)能力并不理想。考慮到粒子群優(yōu)化算法粒子的“聚集”特性，若粒子xkj的位置是第k代粒子群中m個粒子的鄰域極值，則m越大，表明xkj所在的位置附近存在最優(yōu)解可能性越大。以這樣的粒子為初值進行局部搜索就應(yīng)該比較容易找到問題的最優(yōu)解。為此，在粒子群優(yōu)化算法中嵌入模式搜索算法的條件是，若K為某一給定正整數(shù)，粒子xkj的位置是m個粒子的鄰域極值，且m≥K，則以粒子xkj為模式搜索算法的初值進行深度開發(fā)。

2.3 混合粒子群優(yōu)化算法步驟

算法具體步驟：

Step1：設(shè)置模式搜索算法和粒子群優(yōu)化算法的參數(shù)，初始化種群中各粒子的位置和速度；

Step2：評價初始種群中粒子，確定每個粒子鄰域極值lbest，并將每個粒子鄰域極值lbest作為每個粒子的plbest，初始種群中的最佳位置設(shè)置為gbest；

Step3：判定粒子是否滿足嵌入模式搜索算法的條件，若條件滿足，則以該粒子為初值，采用模式搜索算法進行深度開發(fā)，并將搜索到的位置和相應(yīng)的適應(yīng)值替代粒子開發(fā)前的位置和適應(yīng)值；

Step4：按式（2）（3）更新粒子的速度和位置，評價種群的所有粒子，并更新plbest和gbest；

Step5：若滿足算法的終止條件，則輸出gbest及其適應(yīng)值；否則，轉(zhuǎn)step3。

3 實驗結(jié)果及其分析

為了測試本文提出的混合粒子群優(yōu)化算法的性能，選取如表1所示的4個全局最優(yōu)值為0的最小化函數(shù)進行仿真實驗?；旌狭Ｗ尤簝?yōu)化算法的參數(shù)設(shè)置見表2，最大速度限制Vmax取為各函數(shù)初始范圍的上限，慣性權(quán)重設(shè)置為從0.9到0.4的線性變化。為方便表述，本文的算法1為標準粒子群優(yōu)化算法，粒子按式（1）（2）更新速度和位置，學習因子c1，c2均取值為2；算法2為基于鄰域空間的粒子群算法，粒子按式（2）（3）更新速度和位置，粒子的鄰域空間按定義1產(chǎn)生，學習因子c1，c2按式（4）取值；算法3為算法1+模式搜索算法，每代僅對最優(yōu)粒子進行模式搜索；算法4為算法2+模式搜索算法，每代僅對滿足局部搜索條件的粒子進行模式搜索。本文采用Matlab7.1實驗平臺進行仿真實驗。實驗結(jié)果如表3所示，其中MEAN，BEST、WORST、SD分別表示算法獨立運行20次的平均值、最佳適應(yīng)值、最差適應(yīng)值和適應(yīng)值方差，SR表示達到優(yōu)化目標的尋優(yōu)次數(shù)占實驗次數(shù)的比例。所謂達到優(yōu)化目標，是指算法搜索到的測試問題解與問題的最優(yōu)解之差的絕對值小于1.0×10-4。為了直觀地反映算法的尋優(yōu)效果，圖1給出了不同算法對相關(guān)測試函數(shù)的收斂曲線。

表1 測試函數(shù)Tab.1 Test functions

表3 4種算法仿真實驗結(jié)果Tab.3 Four kindsof algorithm simulation results

圖1 測試函數(shù)收斂曲線Fig.1 Test function convergence curve

比較表3的數(shù)據(jù)和圖1測試函數(shù)收斂曲線，我們得到以下結(jié)論：

1）對單峰優(yōu)化函數(shù)而言，算法1和算法2搜索到的最優(yōu)解的精度都不高，算法2的精度略好于算法1；對多峰優(yōu)化函數(shù)而言，算法2表現(xiàn)出良好全局尋優(yōu)能力，優(yōu)化率明顯地高于算法1。這主要是算法2在算法初期，學習因子c1取值較大，遞減的速度較慢，而學習因子c2取值較小，遞增速度較慢，算法更強調(diào)粒子共享鄰域空間的局部信息，使算法在初期能夠在局部范圍內(nèi)進行比較細致的搜索，進而保證算法2搜索到多峰優(yōu)化函數(shù)的全局最優(yōu)解。算法2在算法后期，學習因子c1取值較小，遞減的速度較慢，而學習因子c2取值較大，遞增速度較慢，算法強調(diào)種群中最優(yōu)粒子信息的共享，加快算法收斂的速度，提高最優(yōu)解的精度。但從實際搜索到的最優(yōu)解來看要真正提高解的精度有必要通過局部優(yōu)化算法來提升解的精度。

2）對單峰優(yōu)化函數(shù)而言，算法3和算法4搜索到的最優(yōu)解的精度得到明顯的提高，優(yōu)化達標率均為100%，這表明模式搜索算法提高解的精度的作用是明顯的；但對多峰優(yōu)化函數(shù)而言，算法4的全局尋優(yōu)能力要比算法3強很多。這主要是因為標準粒子群優(yōu)化算法易于收斂到局部最優(yōu)解，且跳出局部最優(yōu)解的能力較弱，對每一代的最優(yōu)粒子進行模式搜索往往起到提高局部最優(yōu)解的精度作用，這必然導致算法3的尋優(yōu)能力不理想；算法4搜索到的最優(yōu)解的平均值、最佳適應(yīng)值、適應(yīng)值方差和達標率都明顯地好于算法2搜索到的。這表明每代對滿足局部搜索條件的粒子進行模式搜索，使得算法4既能發(fā)揮算法2全局尋優(yōu)能力，又能充分發(fā)揮模式搜索算法強大的局部開發(fā)能力，并較好地保持這兩種能力的平衡。

4 結(jié)語

本文提出的基于鄰域空間的混合粒子群優(yōu)化算法較好地解決了粒子群優(yōu)化算法在求解高維復雜函數(shù)優(yōu)化問題時易陷入局部最優(yōu)解的問題。新的算法既能充分發(fā)揮基于鄰域空間的粒子群算法的全局“探測”能力，又能充分發(fā)揮模式搜索算法的局部“開發(fā)”能力。通過4個典型測試函數(shù)的實驗研究表明提出算法具有優(yōu)化精度高、收斂速度快、魯棒性好，特別適合高維多峰函數(shù)的優(yōu)化問題的求解。在仿真測試的過程中，發(fā)現(xiàn)參數(shù)num、參數(shù)K及兩種鄰域空間的定義方式都會對算法的性能產(chǎn)生一定的影響，我們繼續(xù)對這些問題作進一步的研究，并將提出的算法應(yīng)用于實際問題進一步檢測算法的性能。

［1］EBERHARTR C，KENNEDY J.A new optim izer using particle swarm theory［C］//The 6thInt Symp on Micro Machine and Human Science，Nagoya，1995：39-43.

［2］ KENNEDY J，EBERHART R C.Particle swarm optimization［C］//Proc of the IEEE Int Conf on Neural Networks.Piscataway，1995：1942-1948.

［3］SHIY，EBERHARTRC.Amodified particle swarm optimizer［R］.IEEE Internatio-nal Conference of Evolutionary Computation，Anchorage，Alaska，1998.

［4］SHIY，EBERHARTRC.Empiricalstudy of particle swarm optim ization［C］//Proceeding of Congress on Evolutionary Computation.Piscataway，NJ：IEEEService Center，1999：1945-1949.

［5］ CLER CM.The swarm and the queen：towards a determ inistic and adaptive particle swarm optim ization［C］//Proceedings of the Congresson Evolutionary Computation.Piscataway，NJ：IEEEService Center，1999：1951-1957.

［6］ KENNEDY J.Stereotyping：Improving particle swarm performance w ith cluster analysis［C］//Proceedings o f the Congress on Evolut ionary Computing.Piscataway ，NJ：IEEEService Center，2000：1507-1512.

［7］ KENNEDY J，MENDESR.Population structure and particle swarm performance［C］//Proceedings of the 2002Congress on Evolutionary Computation，Piscataway，NJ，USA，2002：1671-1676.

［8］ RATNAWEERA A，HALGAMUGE S K.WATSON H C.Self-organizing hierarchical particle swarm optim izer w ith time-varying acceleration coefficients［J］.IEEETransactionson Evolutionary Computation，2004，8（3）：240-255.

［9］李炳宇，蕭蘊詩，汪鐳.一種求解高維復雜函數(shù)優(yōu)化問題的混合粒子群優(yōu)化算法.信息與控制，2004，33（1）：27-30.

［10］賈樹晉，杜斌.Rosenbrock搜索與動態(tài)慣性權(quán)重粒子群混合優(yōu)化算法［J］.控制與決策，2011，26（7）：1060-1064.

［11］楊維，李歧強.粒子群算優(yōu)化算法綜述［J］.中國工程科學，2004，6（5）：87-93.

［12］鞏敦衛(wèi)，張勇，張建化，等.新型粒子群優(yōu)化算法［J］.控制理論與應(yīng)用，2008，25（1）：112-119.

［13］ HOOKE R，JEEVES T A.Direct Search solution of numerical and statistical problems［J］Journal of the Association for Computing Machinery（ACM），1961，8（2）：212-229.

［14］陳寶林.最優(yōu)化理論與算法［M］.2版.北京：清華大學出版社，2005：333-334.