帶有非線性慣性權重和柯西變異的粒子群優化算法?

李會榮 彭 嬌

（商洛學院數學與計算機應用學院 商洛726000）

1 引言

粒子群優化算法（Particle swarm optimization，PSO）是由1995年美國的社會心理學家James Ken?nedy和電氣工程師Russell Eberhart提出的一種模擬自然界中鳥類和魚群覓食行為的智能優化算法［1］。由于PSO算法參數較少、求解速度較快、精準度高且收斂性強，而且不需要優化函數的任何可導、可微等信息，目前已經在函數優化［2~3］、濾波器的設計［4］、多模態優化［5］、目標跟蹤［6］等領域得到了廣泛的應用。

由于標準PSO算法容易陷入局部最優，后期震蕩等缺點，針對此問題，很多學者對其進行了大量的研究［7~12］。文獻［7］對基本粒子群優化算法的速度方程進行了改進，減少了控制參數，引入隨機調節因子，使得粒子的自我認知能力和社會認知能力在一定范圍內隨機產生，同時對個體最優粒子進行自適應隨機變異，提高了PSO算法的全局搜索能力。文獻［8］提出了一種最為經典的線性減小慣性權重算法。文獻［9］等探討了高斯分布、正態分布等知識，并以此為原理設置隨機變異算子來提高算法尋優能力。文獻［10］提出了一種混沌初始化和自動更新機制的粒子群優化算法。受到教學優化算法的啟發，文獻［11］提出了一種帶有個體擾動和相互學習的粒子群優化算法。

本文在對PSO算法參數慣性權值分析的基礎上，提出了一種非線性慣性權值和柯西變異的粒子群優化（NCMPSO）算法。該算法首先提出了一種非線性的慣性權重，然后利用柯西變異算子增加了種群的多樣性，從而提高了算法的性能。數值實驗表明，提出的NCMPSO算法能夠有效克服早熟收斂現象并且較有較高精度。

2 標準粒子群優化算法

PSO算法將社會中的個體比作一個無空間大小的粒子，再由大量的粒子組成一個粒子群，每個粒子在問題搜索空間中通過“飛行”找到途經的最佳方位，從而通過迭代計算的方式找到全局最優值或局部最優解。設由N個粒子組成的一個群體，在M維搜索空間中，向量xi=( )xi1，xi2，…xiM表示第i個粒子的位置，第i個粒子的速度表示為第i個粒子迄今為止搜索的最優位置為pi=(bi1，bi2，… ，biM)，整個群體的最優位置記為pg=(pg1，pg2，…，pgM)。對于每一個粒子，其第d維(1≤d≤M)空間中速度和位置更新如下：其中d=1，2，…，M；社會學習因子c1，c2為非負常數，用于調節粒子朝pi和pg方向飛行時的最大單次移動距離；r1和r2是兩個獨立分布在區間[0，1]上隨機數；t表示粒子目前的迭代次數；vid為粒子的速度，且為設定的最大速度；w為慣性權重，它決定了粒子先前速度對當前速度的影響程度，從而起到平衡算法全局搜索和局部搜索能力的作用，w一般采用線性遞減策略［12］。

3 帶有非線性慣性權重和柯西變異的粒子群算法（NCMPSO）

3.1 非線性動態遞減權值策略

慣性權重是影響PSO算法性能的重要參數之一，慣性權重越大，粒子群的運行速度加快，搜索局部空間的能力降低，探測全局空間的能力就隨之增強；慣性權重越小，粒子的運行速度降低，搜索局部空間的能力就會增強，探測全局空間的能力也就隨之減弱。因此對慣性權重進行適當的改進可以提高PSO算法的性能。為此Shi Y等學者在1998年的IEEE會議上提出了一種線性遞減慣性權重粒子群算法（Linear Decreasing Particle Swarm Optimiza?tion，LDPSO），其線性遞減慣性權重策略如下［8］：

其中：tmax表示最大的迭代次數；t表示當前的迭代次數；wmax和wmin分別表示設定的最大慣性權值和最小慣性權值。通過多次實驗分析，作者發現隨著迭代次數的增加，當wmax=0.9，wmin=0.4時，算法的搜尋性能大大提高。

本文在對LDPSO算法的基礎上，受文獻［13~14］思想的啟發，提出了一種非線性動態遞減權值策略粒子群優化算法（Nonlinear Dynamic Iner?tia Weight Particle Swarm Optimization，NDIWPSO），即將慣性權重設置成非線性的指數函數：

其中k為控制因子。與LDPSO相比，當w接近于wmax時，w的取值增大，NDIWPSO在大部分迭代期間內以式（1）的首項為主，則粒子擴大搜索空間的能力增強，在搜尋全局空間時更具優勢，同時粒子向最優值所處位置的收縮能力下降，搜索局部空間能力隨之減弱；當w接近于wmin時，w的取值減小，NDIWPSO在大部分迭代期間內以式（1）的后兩項為主，則粒子在搜尋局部區間的最優值時更具優勢，而搜尋全局空間能力隨之減弱。所以非線性指數函數式（4）可以使算法在局部搜尋和全局搜尋的能力之間達到更佳。

此外，對于復雜的非線性多峰函數，粒子就極容易陷入局部極值，這時就需要引領該粒子跳出這個局部極值點。如此一來，式（4）提出的慣性權重策略就無法解決多峰函數的問題，于是對式（4）再進行改進得到如下公式。

為了增加種群的多樣性，在式（5）的基礎上對其采用變異策略，從而引領粒子跳出局部最優值點，在更全局的空間中進行搜索。

3.2 柯西變異策略

若粒子的種群規模為N，f(xi)代表第i個粒子的適應度值，favg表示粒子群中粒子適應度值的平均值，δ代表粒子群的聚集度。則將聚集度δ定義如下［15］：

其中h為控制因子，可以自適應限制聚集度δ的大小。h定義為如下

由式（6）可知，粒子群的聚集度δ代表的是粒子群中所有粒子的匯集程度。若單個粒子的適應度值和群體平均適應度值的差距越大，則粒子能具備更好的多樣性，反之粒子的多樣性就越少。所以若δ越大，則偏差越小，即粒子的多樣性就越優；若δ越小，則所有粒子的匯集程度越小，而偏差就越大，即粒子的多樣性越差。

故當δ

然后對粒子群進行混合變異，得

帶有非線性慣性權重和柯西變異的混合粒子群算法（NCMPSO）的基本流程如下。

步驟1（初始化）設置當前迭代次數t=1，最大迭代次數tmax，種群規模N，搜索空間的維數M，以及隨機產生每個粒子的初始位置和速度。

步驟2根據式（1）、（2）以及式（5）更新每個粒子的速度與當前位置，計算每個粒子的適應度函數值f(xi)。

步驟3（個體最優更新）對每一個粒子xi，如果當前適應度函數值f(xi)優于個體歷史最優位置f(pi)，則更新個體最優pi。

步驟4（全局最優更新）對每一個粒子xi，如果當前適應度函數值f(xi)優于全局最優位置f(pg)，則更新全局最優pg。

步驟5根據式（6）計算粒子群的聚集度δ，若δ

步驟6令t=t+1，返回到步驟2，直到獲得一個預期的適應值或t達到設定的最大迭代次數停止。

4 實驗結果及分析

4.1 基本測試函數

為了驗證本文提出的NCMPSO算法的性能，選取6個常用的測試函數（如表1所示）進行實驗，函數的最優值均為0。

表1 中的測試函數都是高維復雜的最小化問題，其中f1，f3為非線性對稱單峰函數，用于檢測算法的收斂精度；f2也是單峰函數，用于測試算法的執行能力，其全局最優值點在一個平滑且極長的拋物線性山谷里，曲面山谷中點的降落方位和到函數最小值的最好方位垂直；f4，f5，f6都是非線性多峰函數，峰形高低起伏不定，具有大量的局部最優值點。

表1 標準的測試函數

4.2 參數設置

為了選取式（5）和式（8）中參數k的取值，對于六個不同的測試函數，我們分別選取k∈{0.1，0.5，1.0，1.5，2.0，2.5，3.0，3.5，4}，搜索空間維數M=30，每個實驗獨立運行10次對參數k進行選取。

實驗中參數設置如下：粒子的種群規模N=50，最大迭代次數為tmax=1000，社會因子c1=c2=1.8，最大最小慣性權重分別為wmax=0.9和wmin=0.4，允許的最大誤差為10-6。對于Sphere函數，k=4；對于Rosenbrock函數，k=2；對于Schwefel函數，k=0.1；對于Ackley函數，k=4；對于Griewank函數，k=2；對于Rastrigin函數，k=3。

4.3 實驗結果分析

為了驗證本文提出NDIWPSO算法、NCMPSO算法的性能，并分別與固定權重w=1的標準PSO算法、線性減小慣性權重LDPSO算法進行比較。每個實驗獨立運行20次，表2~3分別列舉了搜索空間的維數M=10、30不同情況下PSO、LDPSO、NDI?WPSO以及NCMPSO算法20次運行的最優值、最優值的平均值、最優值的標準差的測試結果。

表2 實驗結果統計表（M=10）

表3 實驗結果統計表（M=30）

從表2~3中可以看出，無論搜索空間M=10還是M=30，提出的NDIWPSO、NCMPSO算法的尋優性能都優于PSO、LDPSO算法。這表明，引入非線性遞減的慣性權重和柯西混合變異策略能夠有效地提高算法的性能。但是對于單峰函數Sphere、Rosenbrock和Schwefel函數，NDIWPSO算法的性能優于NCMWPSO算法；對于多峰函數Ackley、Grie?wank和Rastrigin函數，NCMWPSO算法的性能優于NDIWPSO算法。由此可見，對于復雜多峰測試函數，柯西變異算子能夠有效地跳出局部極值點，保持了種群的多樣性，進一步提高了NCMWPSO算法的性能。

圖1 給出了PSO、LDPSO、NDIPSO以及NCMP?SO算法的收斂曲線圖，從圖1中可以看出，NDIP?SO、NCMPSO無論在收斂速度還是收斂精度上都明顯地優于PSO算法和LDPSO算法，且在較小的迭代次數內收斂到最優點，使得粒子能夠保持較好的活性，能夠有效從局部極值中跳出，搜索精度優于PSO、LDPSO算法。

圖1 PSO、LDPSO、NDIPSO和NCMPSO算法的收斂曲線

5 結語

為了克服粒子群優化算法早熟收斂、容易陷于局部極值的不足，對標準PSO算法中的慣性權值進行改進，提出新的慣性權重函數公式，同時利用柯西變異算子讓算法能夠跳出局部最優，從而提出一種新的帶有非線性慣性權重和柯西變異的粒子群優化算法。數值實驗表明，本文提出的NDIPSO、NCMPSO算法相比于PSO、LDPSO算法具有更高的有效性和穩定性，有著更廣闊的應用前景。