粒子群算法的改進策略述評

摘要： 首先介紹了基本粒子群算法。其次分析出四類粒子群算法改進策略即混沌優(yōu)化策略﹑調(diào)整參數(shù)取值策略﹑混合啟發(fā)式算法策略﹑保持種群多樣性策略；同時，對算法各種改進策略實現(xiàn)原理及實現(xiàn)方法進行介紹。第三對粒子群算法四類改進策略性能進行分析。最后對粒子群算法改進策略進行展望。

關(guān)鍵詞： 粒子群算法（PSO）； 混沌優(yōu)化； 調(diào)整參數(shù)取值； 混合啟發(fā)式算法； 保持種群多樣性

中圖分類號：TP301.6 文獻標志碼：A 文章編號：1006-8228(2012)10-01-03

0 引言

粒子群（Particle Swarm Optimization，PSO）算法是由美國的心理學(xué)家J.Kennedy和工程師R.C.Eberhart于1995年提出的群體智能進化算法[1-2]。該算法具有概念簡單、參數(shù)較少、易于實現(xiàn)等特點，所以問世以來受到了很大的關(guān)注。目前，PSO算法廣泛應(yīng)用于多目標優(yōu)化、預(yù)測系統(tǒng)、神經(jīng)網(wǎng)絡(luò)訓(xùn)練、智能控制等方面[3-5]。但傳統(tǒng)的PSO算法具有局部搜索能力較差，易陷入局部最優(yōu)，搜索性能對參數(shù)具有依賴性等缺點。

因此，研究者們從各種角度出發(fā)對算法進行改進。目前改進算法的研究方向主要有混沌優(yōu)化策略﹑調(diào)整參數(shù)取值策略﹑混合各種啟發(fā)式算法策略﹑保持種群多樣性策略。然而，各種粒子群算法改進策略分析的文獻尚未見報道?；诖?，本文對代表性較強的四類改進策略進行分析研究。

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

在粒子群算法中，搜索空間中每個“粒子”的狀態(tài)都代表優(yōu)化問題的解。每個粒子都有一個適應(yīng)值(fitness value)由被優(yōu)化函數(shù)決定，同時粒子飛行的方向和距離由速度決定。粒子通過跟蹤兩個位置來更新自身，一個是粒子自身所找到的最優(yōu)解pbest，即個體最優(yōu)位置；另一個是整個種群當前找到的最優(yōu)解gbest，即全局最優(yōu)位置。

PSO算法計算過程中，隨機產(chǎn)生一個初始種群，同時賦予每個粒子一個隨機速度，并根據(jù)公式⑴和⑵來更新粒子的速度和位置[1]。

其中，vid是粒子的速度，w是慣性因子，c1、c2是學(xué)習因子，φ1、φ2是介于(0，1)之間的隨機數(shù)，xid是粒子當前位置，pid代表粒子當前最優(yōu)位置，pgd代表種群當前最優(yōu)位置，也就是全局最優(yōu)。根據(jù)式⑴、⑵對粒子的速度、位置不斷更新進化，直至達到最大迭代的次數(shù)或者達到所要求的精度停止迭代。在式⑴中，第一項是粒子先前速度的繼承，依據(jù)自身的速度進行慣性運動；第二項是“認知”部分，結(jié)合自身以往的經(jīng)驗實現(xiàn)下一步行為決策；第三項是“社會”部分，表示粒子間的信息共享與合作。

2 粒子群算法的改進策略

2.1 混沌優(yōu)化策略

混沌是一種非周期運動現(xiàn)象普遍存在于非線性系統(tǒng)中，其表現(xiàn)出介于隨機與規(guī)則之間的運動行為，具有遍歷性、隨機性和規(guī)則性特征?；煦鐑?yōu)化是利用混沌運動的上述特征來提高隨機優(yōu)化算法的效率[6-8]。其基本思想是:通過混沌映射規(guī)則將優(yōu)化變量映射到混沌變量空間的取值范圍內(nèi)，利用混沌序列可以在一個特定區(qū)域內(nèi)遍歷所有狀態(tài)的特征進行尋優(yōu)搜索，最后將獲得的優(yōu)化解線性轉(zhuǎn)換到優(yōu)化空間。

文獻[9]采用邏輯自映射函數(shù)Logistic映射產(chǎn)生混沌序列，在已搜索到的精英粒子周圍嘗試搜索更優(yōu)解并動態(tài)調(diào)整搜索范圍，在防止算法陷入局部最優(yōu)的同時還提高了算法搜索的精度。文獻[10]應(yīng)用Tent映射初始化均勻分布的粒群，并以目前整個粒子群搜索到的最優(yōu)位置為基礎(chǔ)產(chǎn)生Tent混沌序列，混沌序列的搜索范圍采用自適應(yīng)調(diào)整的方法。該方法可以有效避免計算的盲目性，還能夠提高搜尋最優(yōu)解的速度。文獻[11]使用Sobol序列映射決策變量初始值，使得初始解集均勻的分布在全決策空間范圍。仿真結(jié)果表明該算法能夠在滿足優(yōu)化解收斂性的同時獲得更好的種群多樣性。

2.2 調(diào)整參數(shù)取值策略

2.2.1 加速系數(shù)調(diào)整策略

在標準粒子群優(yōu)化算法中，加速系數(shù)c1控制著個體的“認知”能力，加速系數(shù)c2控制著群體的“社會引導(dǎo)”能力。理想的加速系數(shù)調(diào)整策略是：進化的初期應(yīng)該具有較大的c1和較小的c2，這樣利于算法在整個空間進行搜索；進化的末期應(yīng)該具有較小的c1和較大的c2，這樣有利于算法收斂到全局最優(yōu)解，從而提高算法的收斂速度和精度。

文獻[12]提出了一種自適應(yīng)擴展的簡化粒子群優(yōu)化算法。該算法采用除去速度項的簡化算法結(jié)構(gòu)，自適應(yīng)動態(tài)調(diào)整加速系數(shù)。實驗結(jié)果顯示，算法能夠有效避免早熟收斂現(xiàn)象，其全局收斂性能明顯提高，收斂速度增快。文獻[13]提出了一種振蕩參數(shù)策略，用以提高粒子群優(yōu)化算法在進化后期的收斂性能。在整個搜索過程中通過加速度系數(shù)值的變化交替進行全局搜索和局部挖掘。加速度系數(shù)振蕩變化既能提高初期的全局搜索能力，又克服早熟收斂，并使粒子最終趨于全局最優(yōu)。文獻[14]提出了一種帶極值抖動的變尺度粒子群優(yōu)化算法，該算法在粒子進化過程中通過動態(tài)調(diào)整學(xué)習因子來改善粒子的搜索性能，采用極值抖動方法使粒子逃離局部最優(yōu)解。實驗表明，該算法優(yōu)化效率及優(yōu)化精度均優(yōu)于典型粒子群改進算法。

2.2.2 慣性權(quán)重調(diào)整策略

為了改善基本PSO算法容易早熟收斂陷入局部最優(yōu)的缺點，Y.Shi和R.C. Eberhart將慣量權(quán)重引入算法的速度進化方程中[15]。慣量權(quán)重使得粒子能夠保持運動慣性，增強了粒子對新區(qū)域的搜索能力。Shi和R.C.Eberhart的研究表明，慣量權(quán)重較大時，粒子具有較好的全局搜索能力，而慣量權(quán)重較小時，粒子則具有較好的局部搜索能力。基于上述研究，他們進一步提出了慣量權(quán)重線性遞減(linearly decreasing weight，LDW)[16]的調(diào)整方法。LDW方法比基本的PSO算法在性能上有顯著的提高，所以該策略至今仍被眾多研究者所使用。

文獻[17]提出了動態(tài)慣性權(quán)重和維變異的改進粒子群優(yōu)化算法。算法根據(jù)維多樣性動態(tài)地調(diào)整慣性權(quán)重。仿真實驗說明該算法能增強粒子全局搜索能力，并且能提高粒子收斂速度。文獻[18]提出了一種全局粒子群優(yōu)化(GPSO)算法。算法中慣性權(quán)重被定義為一個隨機數(shù)與一個指數(shù)型函數(shù)的乘積，這有利于均衡算法的全局搜索和局部搜索。仿真實驗說明，算法具有更快的收斂速度和更強的逃離局部最優(yōu)的能力。文獻[19]提出基于正切曲線、正弦曲線和對數(shù)曲線的非線性慣性權(quán)值調(diào)整策略。實驗結(jié)果顯示，針對連續(xù)函數(shù)優(yōu)化問題，正弦曲線和對數(shù)曲線方法優(yōu)于傳統(tǒng)的線性調(diào)整策略，而傳統(tǒng)的線性調(diào)整方法又優(yōu)于正切曲線策略。

2.3 混合各種啟發(fā)式算法策略

很多研究者將基本PSO算法與其他智能算法相混合，目的是利用其他智能優(yōu)化算法的優(yōu)勢來彌補基本PSO算法的不足。

當整個種群陷入局部最優(yōu)的時候，PSO算法難以從局部最優(yōu)中跳出。為此，將遺傳算法中的交叉和變異操作引入粒子群算法，以保持種群的多樣性，避免陷入局部最優(yōu)，最終搜索到最優(yōu)解。針對粒子群算法處理復(fù)雜優(yōu)化問題時可能出現(xiàn)早熟收斂現(xiàn)象，將蟻群算法中信息素表的選擇機制引入粒子群算法。通過構(gòu)造單個粒子的多個進化方向，提高了粒子間的多樣性差異，從而改善算法性能。

文獻[20]集成蟻群算法和PSO算法，并將其應(yīng)用于生物數(shù)據(jù)集的層次分類。文獻[21]在PSO算法中引入選擇機制對算法進行改進，實驗結(jié)果表明對某些復(fù)雜的測試函數(shù)效果比較好。文獻[22]在PSO算法中引入變異機制改進算法性能，提高了算法收斂性能。文獻[23] 將遺傳算法中的雜交思想引入標準粒子群優(yōu)化算法中，提出了基于繁殖粒子群優(yōu)化算法的負荷優(yōu)化分配方法，克服了標準粒子群算法易陷入局部最優(yōu)及遺傳算法優(yōu)化計算時間長的缺陷。文獻[24]提出了一種混合的粒子群優(yōu)化算法（Hybrid Particle Swarm Algorithm，HPSA），將粒子群算法、局部搜索策略以及遺傳操作有效地結(jié)合在一起。實驗結(jié)果表明：HPSA通過改進種群選取方法和擴大搜索范圍提高了解的質(zhì)量，在性能上均優(yōu)于目前較有效的混合禁忌搜索算法和啟發(fā)式算法。

2.4 保持種群多樣性策略

保持種群多樣性方法很多，最常見的是使用變異算子增強種群的多樣性。該操作增強了粒子在全局最優(yōu)解附近進行隨機搜索的能力，可以有效避免算法早熟。該策略的關(guān)鍵問題是變異概率的選取。過大的變異概率導(dǎo)致盲目地擴大搜索范圍，這會降低算法的收斂性；而過小的變異概率則導(dǎo)致粒子被局限在一個較小搜索范圍內(nèi)，這會減弱算法跳出局部最優(yōu)的能力，也不足以維持種群的多樣性。

文獻[25]將魚群算法中擁擠度因子的概念引入粒子群算法，提出了前饋擾動粒子群算法，以當前最優(yōu)值為圓心擁擠度因子為半徑的圓域內(nèi)計算粒子的數(shù)量，當粒子數(shù)量超過某一常數(shù)時，給種群加入適當擾動避免種群陷入局部最優(yōu)。仿真實驗驗證了理論及所提出算法的有效性。文獻[26]提出一種自適應(yīng)指導(dǎo)的文化粒子群算法。算法根據(jù)群體適應(yīng)度方差的值判斷群體空間狀態(tài)，一旦算法陷入局優(yōu)，利用影響函數(shù)自適應(yīng)地對群體空間進行變異更新，實驗結(jié)果表明該算法不僅具有較好的全局收斂性，而且算法收斂速度和穩(wěn)定性也都有顯著提高。文獻[27]借鑒群體位置方差的早熟判斷機制，將變異算子和基因換位引入到算法中，構(gòu)造出新的個體及個體基因的適應(yīng)值函數(shù)，并對適應(yīng)值最差的基因進行變異。實驗表明，該算法具有更快的收斂速度且具有很強的避免陷入局優(yōu)的能力。文獻[28]提出一種基因變異粒子群算法成功的應(yīng)用于在線參數(shù)識別系統(tǒng)。

3 四類改進策略性能分析

PSO常見的缺點是算法后期收斂速度慢、收斂精度差、易陷入局優(yōu)，其根本原因是在進化過程中未能很好保持種群多樣性，這與PSO自身的運作機制有很大關(guān)系。改進策略的目的就是改善PSO的這些缺點，從而提升算法的優(yōu)化性能。

3.1 混沌優(yōu)化策略

混沌系統(tǒng)對初值極其敏感，初始條件的細微變化會引起輸出結(jié)果巨大的差異；混沌是確定性系統(tǒng)本身產(chǎn)生的不穩(wěn)定現(xiàn)象，使系統(tǒng)在動力性持久性上表現(xiàn)出相似隨機的復(fù)雜行為，這種性質(zhì)被稱為內(nèi)在隨機性；在進行混沌優(yōu)化搜索時，由于混沌序列可以在一個特定區(qū)域內(nèi)不重復(fù)地遍歷所有狀態(tài)，所以混沌搜索已成為一種有效的優(yōu)化工具。

利用混沌序列特征進行粒子群的初始化分布，能擴大粒子搜索范圍，大大增強算法的搜索多樣性，為找到更優(yōu)解和提高收斂速度奠定堅實的基礎(chǔ)。該策略雖然對算法性能有一定改善，但同樣存在缺陷：一是不能從根本上克服早熟收斂現(xiàn)象；二是會導(dǎo)致算法的運算量增加。

3.2 調(diào)整參數(shù)取值策略

調(diào)整參數(shù)取值策略思想是算法前期具有較好的全局搜索能力，算法后期具有較好的局部尋優(yōu)能力。這種策略可以通過調(diào)整加速系數(shù)或者調(diào)整慣性權(quán)重的變化方式來實現(xiàn)。

慣性權(quán)重變化方式通常是隨著進化代數(shù)的增加而線性變小，而實際搜索過程中是非線性的且具有高度復(fù)雜性，如果用這種單純線性遞減的策略來反映實際的優(yōu)化過程，一旦在進化的初期搜索不到最優(yōu)點，隨著慣性權(quán)重的逐漸減小，容易使算法陷入局部最優(yōu)，出現(xiàn)早熟收斂現(xiàn)象；而且對于不同問題，每一代所需要的比例關(guān)系也不相同，所以，線性遞減關(guān)系只對某些問題有效，對其他問題顯然不一定合適。

3.3 混合各種啟發(fā)式算法策略

很多研究者將基本PSO算法與其他智能算法相混合，目的是利用其他智能優(yōu)化算法的優(yōu)勢來彌補基本PSO算法的不足。

例如，與遺傳算法混合就是將遺傳算法的基因交叉算子引入到基本 PSO中。通過對種群中的粒子兩兩實施基因操作形成新一代粒子。基因交叉能提高種群質(zhì)量，使得算法后期的收斂速度和精度明顯提高。這類混合粒子群算法能夠在一定程度上使算法保持種群的多樣性，避免陷入局部最優(yōu)；但是也不可避免的使得算法在每次進化過程中的計算量增加，進而影響了PSO的快速收斂能力。

3.4 保持種群多樣性策略

通過對粒子速度或位置引入隨機變異操作來增強種群多樣性，使算法能夠有效地進行全局搜索。該方法的問題是過大的變異率在增加種群多樣性的同時也將導(dǎo)致群體發(fā)生混亂，使種群不能進行精確的局部搜索，同樣降低了算法的收斂速度。

使用變異算子增強種群的多樣性會破壞粒子結(jié)構(gòu)導(dǎo)致收斂速度慢；而且這種策略也會增加算法在每次進化過程中的計算量，進而影響了PSO的快速收斂能力。該方法是否合理需要對具體問題進行大量的仿真實驗后方能確定。

4 粒子群算法改進策略展望

隨著研究者對粒子群算法研究的不斷深入，算法未來的改進方向總結(jié)如下：

⑴ 可以考慮從新的角度對PSO算法進行改進，例如統(tǒng)計物理和熱力學(xué)理論對于改進粒子群優(yōu)化算法的性能有很大的促進作用，又如耗散結(jié)構(gòu)理論和自組織臨界理論等；

⑵ PSO算法是一種基于種群的算法，具有并行性，可以從并行優(yōu)化的角度對算法進行改進；

⑶ 拓撲結(jié)構(gòu)對搜索性能的影響較大，可以從分析粒子拓撲結(jié)構(gòu)的思路來改進算法。

5 結(jié)束語

本文敘述了粒子群算法的基本原理。對粒子群算法的各種改進策略進行了歸納總結(jié)，目前改進算法的研究方向主要有混沌優(yōu)化策略﹑調(diào)整參數(shù)取值策略﹑混合各種啟發(fā)式算法策略﹑保持種群多樣性策略；介紹了各種改進策略的實現(xiàn)方法；對各種改進策略進行了分析；對粒子群算法的改進策略進行了展望。希望本文能為從事粒子群算法研究的學(xué)者提供有價值的參考。