一種基于鄰域空間的混合粒子群優化算法

曾 毅，朱旭生，廖國勇

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

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

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

1 標準粒子群優化算法

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

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

2 基于鄰域空間的混合粒子群優化算法

2.1 算法思想

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

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

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

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

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

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

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

2.2 模式搜索算法

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

模式搜索算法由Hooke和Jeeves于1961年提出的，一種不需要計算導數的無約束最優化的直接算法［13］。算法主要由探測移動和模式移動過程組成，探測移動是沿坐標軸方向的移動，模式移動則是沿相鄰兩個探索點連線方向上移動，兩種移動交替進行，順著函數值下降的最佳方向搜索到函數的最小值。模式搜索算法的步驟［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，轉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，轉Step2；

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

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

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

2.3 混合粒子群優化算法步驟

算法具體步驟：

Step1：設置模式搜索算法和粒子群優化算法的參數，初始化種群中各粒子的位置和速度；

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

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

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

Step5：若滿足算法的終止條件，則輸出gbest及其適應值；否則，轉step3。

3 實驗結果及其分析

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

表1 測試函數Tab.1 Test functions

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

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

比較表3的數據和圖1測試函數收斂曲線，我們得到以下結論：

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

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

4 結語

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

［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］李炳宇，蕭蘊詩，汪鐳.一種求解高維復雜函數優化問題的混合粒子群優化算法.信息與控制，2004，33（1）：27-30.

［10］賈樹晉，杜斌.Rosenbrock搜索與動態慣性權重粒子群混合優化算法［J］.控制與決策，2011，26（7）：1060-1064.

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

［12］鞏敦衛，張勇，張建化，等.新型粒子群優化算法［J］.控制理論與應用，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］陳寶林.最優化理論與算法［M］.2版.北京：清華大學出版社，2005：333-334.