基于萊維飛行的改進簡化粒子群算法

梁 田，曹德欣

中國礦業大學 數學學院，江蘇 徐州 221116

粒子群優化算法（Particle Swarm Optimization，PSO）是基于群體的啟發式優化算法，由Kennedy和Eberhart[1]于20世紀90年代首次提出。通過模擬鳥類捕食行為來構建優化算法。每個個體都被稱作是一個粒子，算法通過粒子之間的群體協作使其達到最優。與其他復雜智能算法不同，PSO算法原理簡單，沒有交叉、變異等復雜的操作。故在經濟管理、信息科學、工程技術、函數優化等諸多領域中應用廣泛。

但PSO算法參數固定，對復雜函數進行優化時表現出較差的求解精度。雖然算法在前期若干次迭代效果尚好，但后期易陷入局部最優。因此，對基本PSO算法的改進成為國內外學者研究的焦點。Shi等在文獻[2]中初次提出慣性權重概念，文中將慣性權重的取值從0.9線性遞減至0.4，算法性能得到明顯的改善。Kennedy等[3]分析粒子間的信息流，提出一系列的拓撲結構。高立群等[4]在粒子群算法中加入變異因子，在粒子速度和位置更新之后進行變異操作。以上對基本PSO算法的改進可有效地避免算法的參數固定、粒子種群多樣性減少等不足，改善其收斂性能。

上述改進算法雖在性能上有所改善，但早熟收斂現象仍然存在。為能更好改善基本PSO算法的尋優性能，提出一種基于萊維飛行的改進簡化粒子群算法（LISPSO）。首先，將帶有隨機性的非線性遞減慣性權重引入到簡化PSO上。前期的慣性權重值較大，全局搜索能力強。而后期取值較小能夠提高算法局部搜索能力。其次，為保證粒子逃離局部最優，該算法融入基于相似度及聚集度分析的萊維飛行。利用粒子與最優粒子之間的歐氏距離來定義粒子與最優粒子間的相似度，同時利用粒子與最優粒子的平均相似度計算粒子群的聚集度。粒子間的相似度或者聚集度越大，則粒子進行萊維飛行的概率就越大。保持粒子種群多樣性，避免算法早熟收斂。

1 標準粒子群優化算法NPSO（Normative Paticle Swarm Optimization）

PSO算法從隨機解出發，通過不斷迭代尋求最優解或近似最優解，通常用于解決各類優化問題。在PSO算法模型中，每個粒子代表優化問題在搜索空間的潛在解。首先，算法初始化每個粒子，它們都有自己相對應的初始速度和位置。其次，算法每進行一次更新，粒子都通過追蹤目前自身找到的最優位置（個體極值）和所有粒子搜索到的最優位置（全局極值）來重新調整自身的狀態。另外，每個粒子都有其對應的適應度函數值，由此來評判該粒子所在位置的優劣。

可用d維向量來表示所有粒子的位置和速度，即：

每次迭代，粒子速度及位置更新公式如下：

在式（1）和（2）中，t表示當前進化代數；c1、c2為學習因子，一般取值為2；r1、r2為()0,1之間相互獨立的隨機數；在文獻[2]中，Shi和Eberhart提出慣性權重w，后來他們又給出線性遞減慣性權重：

速度更新公式（1）進一步修改為：

其中，wmax和wmin分別表示慣性權重最大值和最小值，通常取值為0.9和0.4。tmax代表最大迭代次數，t表示當前迭代次數。一般稱上述算法為標準粒子群算法（NPSO）。

2 基于萊維飛行的改進簡化粒子群算法（LISPSO）

2.1 預備知識介紹

2.1.1 簡化粒子群優化算法（SPSO）

粒子速度過于發散會導致后期收斂速度慢，為了解決此問題，文獻[5]提出了一種簡化粒子群算法。該算法舍去了速度項，僅由粒子的位置項控制粒子的進化方向。標準粒子群算法中公式（2）和（4）簡化為：

式中，c1、c2一般取值均為2，文獻[5]中w取值0.8。

2.1.2 萊維飛行

萊維飛行是服從萊維分布的短距離和偶爾較長距離行走相間的一種隨機搜索路徑。經大量研究，它符合蜜蜂和果蠅等自然界的許多動物昆蟲的覓食軌跡[6]。目前萊維飛行在優化領域應用廣泛，如王慶喜等在文獻[7]中提出若算法陷入局部最優，則用萊維飛行公式重新調整粒子的位置。劉曉龍等利用萊維飛行改進鳥群算法[8]。萊維飛行的位置更新方程為：

式中，i∈[1,2,…,N],表示第i個粒子在第t次迭代時的位置；⊕為點對點乘法；α代表步長控制量。

萊維飛行的步長符合萊維分布，常使用Mantegna算法模擬，步長s計算公式：

β通常取值1.5。

2.2 算法改進

2.2.1 帶有隨機性的非線性遞減慣性權重

在PSO算法中，慣性權重取值大利于算法進行更廣泛的搜索，小的慣性權重值則能夠提高算法精準的局部搜索能力。因此，慣性權重的取值至關重要?；诖?，提出帶有隨機性的非線性遞減慣性權重，該慣性權重如下：

式中，t表示當前迭代次數，rand為(0,1)之間的隨機數。wmax和wmin分別表示慣性權重的最大值和最小值。

慣性權重w在()0,1之間取值，迭代次數增加，慣性權重取值非線性地逐漸減小。另外，為了避免種群多樣性減少，文獻[9]給出反向搜索策略，即算法每次迭代都要根據隨機數的取值來決定是否進行反向搜索。本文引入文獻[9]的反向搜索機制y()r。其計算公式為：

則改進后的簡化粒子群算法的迭代公式由式（5）修改如下：

其中，r為()0,1之間的隨機數，式（11）中的w按照式（10）進行更新。

2.2.2 粒子群的相似度及聚集度

隨著迭代次數的增加，粒子最終都會向最優粒子靠攏[10-11]?？繑n過程中，粒子間距隨之縮小，相似度隨之增大?，F將粒子間的相似度定義如下：

其中，s(i,j)代表粒子i與粒子j之間的相似度；d(i,j)表示粒子i和粒子j的歐式距離；dmax表示粒子間所有距離的最大值。

從公式（12）可以看出，粒子間的相似度在()0,1之間取值，且兩個粒子之間的相似度隨著距離的增大而減小。當d(i,j)→0時，s(i,j)→1，說明兩個粒子很相似。反之，當d(i,j)→∞時，s(i,j)→0，說明兩個粒子幾乎不相似。

在PSO算法迭代過程中會出現粒子聚集現象。文獻[12]給出聚集度的定義以及計算公式，將每個粒子與當前代最優粒子的平均相似度作為粒子群的聚集度。聚集度越高，粒子種群多樣性越低。本文采用文獻[11]的聚集度計算方法，即：

其中，N代表粒子群數，s(i,g)為粒子i與當前最優粒子g的相似度，c(t)表示第t代粒子群的聚集度。

2.2.3 基于相似度及聚集度分析的萊維飛行

由2.2.2小節得到粒子群相似度及聚集度的計算方法。用相似度來衡量兩個粒子的間距，而聚集度則量化粒子群多樣性。

若所有粒子都聚集在目前最優粒子p g附近，算法會隨著迭代的進行而出現停滯。若目前的p g是局部最優點，那么此時得到的解并非全局最優解。為使粒子逃離局部最優，提高種群多樣性，對其進行萊維飛行，以此來重新更新粒子的位置。

其中，1<λ≤3，參數α1為一個關于迭代次數的非線性遞減函數。α2為步長控制量，是一固定常數，經過大量實驗，當α2=0.01時，算法的數值實驗效果較好；rand為(0,1)之間的隨機數。

分析式（14）、（15），s(i,g)越大，或者c(t)越大，粒子利用萊維飛行來重新更新自己位置的可能性也就越大，利于粒子快速逃離局部最優。

2.3 LISPSO算法

綜合2.2節的分析，提出基于萊維飛行的改進簡化粒子群算法（LISPSO）。算法步驟如下：

步驟1對粒子的位置進行初始化處理，并設置相關參數：種群規模N；學習因子c1、c2；最大迭代次數M等。

步驟2計算每個粒子適應度值，并將適應度值進行比較、替換，記錄全局最優值和個體最優值。

步驟3分別按照公式（10）、（11）更新粒子的慣性權重值及粒子的位置。

步驟4重新調整粒子的個體最優值及全局最優值。

步驟5根據公式（12）、（13）計算s(i,g)和c(t)，并利用式（14）、（15）判斷粒子是否進行萊維飛行。若粒子進行萊維飛行，則返回步驟4；否則，進行步驟6。

步驟6記錄當前全局最優值。

步驟7判斷算法是否滿足迭代搜索條件，若滿足，則算法終止；否則，算法轉至步驟3。

3 LISPSO算法的時間復雜度分析

在基本粒子群算法中，假設位置自變量維數為d，種群大小為n。初始化階段，各參數初始值的設置、粒子隨機生成初始速度和位置、生成隨機數、計算粒子適應度值以及將所有個體適應度值進行排序得到最優個體適應度值的時間分別為t1、t2、t3、f()d以及t4。則初始化階段總體時間復雜度為：

設迭代階段的迭代次數為m，粒子個體每一維進行位置和速度更新所花費的時間分別為t5和t6。則該階段的時間復雜度為：

每個粒子在更新位置和速度之后，都會重新計算其適應值并將它們進行比較、替換。在記錄最優解階段，設重新計算更新位置和速度后的粒子適應值以及每個個體適應度值與當前最優解進行比較、替換的時間分別為f(d)和t7，那么該階段的時間復雜度為：

最后判斷算法是否達到迭代終止條件，設所花費時間為t8，那么該階段的時間復雜度為：

綜上所述，基本粒子群算法的時間復雜度為：

LISPSO算法在基本粒子群算法的基礎上增加了帶有隨機性的非線性遞減慣性權重、反向搜索機制、相似度及聚集度。設系統計算慣性權重w的時間為g1，判斷粒子是否進行反向搜索所需要的時間為g2，計算粒子與最優粒子的相似度以及每一代粒子的聚集度所花費的時間分別為g3和g4。則計算非線性慣性權重、反向搜索機制、相似度及聚集度所產生的時間復雜度為：

從而LISPSO算法的時間復雜度為：

由此可知，與基本粒子群算法相比，LISPSO算法沒有增加額外的時間復雜度，執行效率并沒有下降。

4 數值實驗與結果分析

4.1 測試函數

為了測試算法的有效性，本文從2017年的基準函數測試集中選取了11個基準測試函數：

（1）Sphere函數

（2）Schwefel函數

（3）Sum of Different Powers函數

（4）Alpine函數

（5）Sum Squares函數

（6）Rastrigin函數

（7）powell函數

（8）Griewank函數

（9）Zakharov函數

（10）Needle-in-a-haystack函數

（11）Michalewicz’s函數

其中，f1～f9的理論最優值為0，f10的理論最優值近似為-3 600,f11的理論最優值為：

4.2 與其他算法實驗對比

4.2.1 數值實驗

為了測試改進粒子群算法LISPSO的性能，將本文算法LISPSO與SPSO、HCPSO算法進行數值實驗對比，其中，SPSO是簡化粒子群算法[5]，HCPSO是文獻[13]提出的基于分層自主學習的改進粒子群優化算法（Particle Swarm Optimization based on Hierar Chical autonomous learning）。LISPSO與SPSO算法的種群大小設置為40，慣性權重w設置為0.6，學習因子c1、c2均設置為2.05，wmax、wmin分別設置為0.9和0.5。HCPSO算法的參數按照文獻[12]進行設置。三種算法的迭代次數均設置為500。

為了測試本文算法對不同維函數的求解能力，f1～f9維數設置為10維、50維，f10維數設置為2維，f11維數設置為2維、5維。每個算例用這三種算法獨立運行20次，并計算這20次的平均值及最優值，將其作為最終的實驗結果，得到表1、表2。另外，為了能更直觀地比較出實驗結果的好壞，在編寫函數時，將函數f10、f11的理論非零值轉化為零，實驗結果越接近零，則說明數值效果越好。將f1～f9維數設置為50維，f10維數設置為2維，f11維數設置為5維。畫出三種算法在11種基準測試函數下的收斂曲線圖，見圖1。其中，表1、表2中加粗部分為實驗對比的最好結果。

4.2.2 實驗結果分析

由表1、表2可以看出，對于上述11個基準測試函數，HCPSO算法表現出來的尋優性能隨著維數的增加逐漸下降。SPSO算法受維度的影響不是很大，但除了f6、f8和f10函數，SPSO在求解其他函數時均未達到理論最優值。而對于函數f1～f10，LISPSO算法在不同維數下找到的最優解以及平均值均為理論最優值。其尋優性能遠超于SPSO算法和HCPSO算法。雖然三種算法對理論最優值與維數相關的函數f11求解結果均未達到理論最優值，但無論是2維還是5維，LISPSO的求解性能均優于其他兩種對比算法。

表1 三種算法對f1～f9的測試結果對比Table 1 Comparison of test results of three algorithms for f1～f9

表2 三種算法對f10～f11的測試結果對比Table 2 Comparison of test results of three algorithms for f10～f11

另外圖1（a）～（k）清晰地展現了在迭代次數為500、函數維數為2維、5維或者50維的情況下，各種算法收斂曲線的變化趨勢。觀察圖1（a）～（j），對于每一個算例，LISPSO算法的收斂速度均優于其他兩種對比算法，且均能在150代以內收斂成功，達到理論最優值。HCPSO表現的尋優性能相對較差。雖然對于函數f6、f8和f10，SPSO與LISPSO均達到理論最優值，但從收斂圖上看，LISPSO的收斂速度還是優于SPSO。無論是收斂速度還是求解精度，本文算法LISPSO均優于其他兩種對比算法。

圖1 三種算法的適應值迭代趨勢圖Fig.1 Iterative trend maps of fitness values of three algorithms

4.3 慣性權重的有效性分析

本文在位置更新公式中引入了帶有隨機性的非線性遞減慣性權重，不僅可以協調局部和全局的搜索能力，添加的rand隨機數更是保持了w的多樣性。為了進一步說明改進慣性權重的有效性，將LISPSO與LISPSOW、LISPSOC進行數值實驗對比。其中，LISPSOW是把LISPSO算法中的慣性權重w換成標準粒子群算法（文獻[2]）中的線性遞減慣性權重。LISPSOC是把LISPSO算法中的慣性權重w換成文獻[7]中的常數因子(w=0.6)。函數維數選擇50維、5維或者2維，每個函數用這三種算法獨立運行20次，其他參數同4.2節。表3為數值實驗結果，圖2為三種算法的尋優收斂曲線圖，這里只選擇了f3、f5、f6、f7和f10五種函數的收斂曲線圖。

觀察表3、表4，LISPSO在求解f1～f10時均達到了理論最優值。雖然LISPSO在求解f11時，并未達到理論最優，但從數值結果來看，LISPSO的求解精度優于其他兩種對比算法。另外兩種對比算法在求解除f6、f8和f10之外的函數時均未達到理論最優解。三種算法中，LISPSO不僅在求解精度上表現最佳，從圖2也可以看出，LISPSO在收斂速度方面也明顯快于其他兩種對比算法。數值結果均表明，改進的慣性權重優于文獻[2]中非線性遞減的慣性權重和文獻[7]中的常數慣性權重，達到較好的協調局部和全局搜索的效果。

表3 不同慣性權重算法對比結果(f1～f9)Table 3 Comparison results of different inertia weight algorithms(f1～f9)

圖2 LISPSO、LISPSOW和LISPSOC算法收斂圖Fig.2 Convergence graphs of LISPSO，LISPSOW and LISPSOC

表4 不同慣性權重算法對比結果(f10～f11)Table 4 Comparison results of different inertia weight algorithms(f10～f11)

5 LISPSO算法求解min-max-min問題

5.1 min-max-min問題

min-max-min問題是一類不可導優化問題，其表達式如下：

min-max-min問題在電子線路設計、工程優化設計、控制系統優化設計等方面應用廣泛。它是典型的不可微問題，所以無論是從理論上還是計算上，解決起來均比較困難。不過仍有一些學者利用智能算法或者區間算法解決min-max-min問題：文獻[14]將提出的混合三群粒子群算法應用到min-max-min問題，并取得較好的數值效果；文獻[15-16]利用區間算法對無約束的minmax-min問題進行求解。本文利用LISPSO算法求解一類min-max-min問題，并進行數值實驗。令：

那么問題（17）轉化為：

min-max-min的適應度函數定為式（18），和前面基準測試函數一樣，求解函數（18）的極小值。將三種算法HCPSO、SPSO和LISPSO應用到以下兩個min-max-min問題，比較它們的算法性能。其中，x*、f*、X(0)分別表示精確最優點、精確值和初始搜索區間。

HCPSO、SPSO以及LISPSO的參數同4.2節，每個算例運行20次，最大迭代次數設置為100，計算這20次的最優值、平均值和方差，見表5，最好的結果用粗體表示。三種算法的收斂曲線圖見圖3、圖4。

表5 兩個min-max-min問題的運行結果Table 5 Results of two min-max-min problems

圖3 問題（1）收斂圖Fig.3 Convergence graph of problem（1）

圖4 問題（2）收斂圖Fig4 Convergence graph of problem（2）

5.2 min-max-min問題的數值實驗結果分析

觀察表5，對于兩個min-max-min函數，本文算法LISPSO均可達到理論最優值，表現出較好的尋優性能。雖然SPSO算法也可以達到理論最優值，但從平均值和方差來看，SPSO算法求解非常不穩定。相對于LISPSO和SPSO，HCPSO求解精度較差。從圖3和圖4來看，LISPSO的收斂速度也明顯快于其他兩種對比算法。

以上算例均表明，改進的算法求解min-max-min問題是行之有效的，且無論是求解精度還是收斂速度，本文算法都表現出較好的尋優性能。

6 結束語

為了避免粒子陷入局部最優，提出了一種基于萊維飛行的改進簡化粒子群算法（LISPSO）。首先該算法舍去速度項，僅由粒子的位置控制粒子的進化方向。其次，LISPSO算法在每次迭代都隨機地、非線性遞減地更新慣性權重，較好地協調全局和局部搜索。最后，算法融入基于相似度及聚集度分析的萊維飛行，幫助粒子跳出局部最優。數值實驗結果更直觀地表明LISPSO算法能夠增強粒子跳出局部最優的能力，提高算法尋優精度及收斂速度。

另外，將LISPSO算法應用于求解一類min-maxmin問題，取得了較好的數值效果，體現出LISPSO算法解決一類min-max-min問題的可靠性和有效性。