粒子群優化算法慣性權重的一種動態調整策略

羅金炎

(閩江學院數學系，福建福州 350108)

粒子群算法(PSO)是Kennedy和Eberhart于1995年提出的一種群體智能演化算法［1］，它源于對簡化社會模型的模擬.與其他進化尋優算法相類似，PSO算法也是通過個體間的協作與競爭，實現多維空間中最優解的搜索.它首先生成初始種群，即在可行解空間中隨機初始化一群粒子，每個粒子都為尋優問題的一個可行解，并用某個函數計算出相應的適應值，以確定是否達到尋優目標.每個粒子將在解空間中運動，并由一個矢量決定其運動方向和位移.通常粒子將追隨當前已知的最優位置，并經逐代搜索，最后得到最優解.在每一進化中，粒子將跟蹤兩個目標位置，一為粒子本身迄今找到的最優解，代表該粒子自身對尋優方向的認知水平;另一為全種群迄今找到的最優解，代表社會認知水平.粒子群算法已被廣泛應用于各種優化問題中，如神經網絡訓練、調度問題、組合優化等.

為改善粒子群算法的搜索性能，Shi和Eberhart對基本PSO算法進行了改進，在粒子的速度進化方程中引入慣性權重 w［2］.慣性權重 w控制著粒子運動的慣性，使粒子有擴展搜索空間的趨勢和開發新區域的能力.慣性權重w的取值對于保證算法的收斂和最優地權衡搜索與開發極其重要，一般地，較大的權重有利于提高算法的全局開發能力，而較小的權重則能增強算法的局部搜索能力.針對慣性權重w的取值問題，國內外的研究人員進行了大量的工作［3-5］，其中線性遞減權重法相對簡單且收斂速度快，被廣泛采用.但是，PSO算法在實際搜索過程中多是高度復雜非線性的，線性遞減權重法不能反映實際的優化搜索過程，也有研究人員據此提出了非線性遞減法［6-7］和引入其他因素的自適應調整權重法［8］等.本文根據PSO算法慣性權重在優化問題過程中的表現特征，提出了一種基于Logistic模型的動態慣性權重的策略，并與典型的線性遞減權重調整策略［3］進行了比較，仿真實驗表明:該策略在優化復雜多峰值的問題方面體現了一定的優越性.

1 粒子群優化算法

設第 i個粒子位置為 xi=(xi1，xi2，…，xin)T，其位移為 vi=(vij，vi2，…，vin)T.它迄今搜索到的個體極值為 pi=(pi1，pi2，…，pin)T，而迄今搜索到的種群極值為 pg=(pg1，pg2，…，pgn)T.為使粒子位移變化不致過大，可以設定其上限Vmax，即若 vid＞ Vmax，則令 vid=Vmax，而若 vid＜ -Vmax，也令vid=-Vmax.每一次迭代，粒子通過兩個極值pi和pg來更新其速度和位置.粒子在解空間內不斷跟蹤個體極值和鄰域極值進行搜索，直到滿足迭代停止條件，即達到規定的迭代次數或滿足規定的誤差標準.

假設尋優問題為求目標函數f(x)的最小值，那么粒子i的個體極值由下式確定

假設群體粒子數為m，則群體粒子的鄰域極值為:

按追隨當前已知的最優位置的原理，粒子xi將按式(3)改變位移方向和步長.

其中:d=1，2，…，n，n 為解空間的維數，即自變量個數，i=1，2，…，m，m 為種群規模，t為進化代數，r1和r2為分布與［0，1］之間的隨機數，c1和c2為位移變化的限定因子，通常取為2.0.

w為慣性權重，較大的權重有利于提高算法的全局開發能力，并增加種群的多樣性;而較小的權重則能增強算法的局部搜索能力.然而過大的權重將使種群發散，粒子不能改變運動方向以轉回需要搜索的指定區域;過小的權重將導致種群的搜索能力喪失，只有很小的慣性從上一步迭代中保存下來，加劇了速度的改變.動態的慣性權重調整通常采用線性遞減策略LDIW［9］，即:

其中T為當前迭代次數，Tmax為最大迭代次數，wmax為初始慣性權值，wmin為進化到最大代數時的慣性權值.

2 非線性權重遞減策略

在PSO算法的搜索過程中可以對慣性權重w進行動態調整.在算法開始時，給w選取較大的值，隨著搜索的進行，可以動態地遞減w的取值，這樣可以保證算法在開始時，各粒子能夠以較大的速度步長在全局范圍內開發較好的種子;而在搜索后期，較小的w值則保證粒子能夠在極點周圍做精細地搜索，使算法有較大的幾率以一定精度收斂于全局最優解.

在標準PSO算法中，存在粒子容易過早收斂于局部極值的早熟現象，在慣性權重線性遞減策略中尤為突出.由于僅僅簡單地線性減小權重w，使得函數一旦進入局部極值點鄰域內就很難跳出，極易收斂到局部極值點.這主要還是因為在搜索過程中，種群中粒子在位置上缺乏多樣性導致的早熟.可以考慮在搜索初期盡可能地保持較大的權重w，使種群粒子飛躍整個搜索空間，以獲得更好的多樣性，從而盡可能擺脫局部極值的干擾;而當種群搜索到全局最優點附近時，及時快速降低權重w，并在搜索后期保持較小的權重w，使得種群以較強的局部搜索能力收斂到全局最優點.據此，根據Logistic函數的特征，提出一種基于Logistic動態調整慣性權重w的策略LgDW算法，慣性權重w將按S形曲線非線性遞減，如圖1所示.

圖1 Logistic動態慣性權重w變化趨勢Fig.1 The evolution of Logistic dynamic inertia weight

其變化公式為

式中:wmax、wmin、Tmax和 T與(4)式一致;a和 b為調整因子，它們的取值范圍為a＞0，0＜b＜1.

3 實驗分析

為檢驗Logistic動態慣性權重PSO算法的效率，并分析確定調整因子，現采用優化領域中常用的4個經典函數來測試分析.

Sphere函數:

其為非凸、病態函數，在xi=0處達到全局最小值f(X*)=0.

Rastrigrin函數:

其為多峰函數，在xi=0處達到全局最小值f(X*)=0.

Griewank函數:

其在xi=0處達到全局最小值f(X*)=0.Schaffer函數:

其全局最大值為f(0，0)=1，在距離全局最大點附近存在大量的次全局極大點，函數的強烈震蕩使其難于全局最優化.

3.1 調整因子的確定

LgDW算法慣性權重公式(5)中的調整因子a和b可以根據目標函數不同的適應值動態地確定，它們對算法的性能有較大的影響.實驗表明:過大的a和b值容易使算法失效，而過小的a和b值則容易使算法陷入局部收斂.它們的取值在10＜a＜50，0.8＜b＜0.93時，算法的性能比較好.表1、表2所示的是在a和b不同取值下對5維Rastrigrin函數的實驗結果，實驗中算法的每組因子隨機運行50次，粒子數為30，要求精度為10-8，最大迭代次數為2 000次.

表1 a=30時取不同b值的性能比較Table 1 Comparative results of different b values with a=30

表2 b=0.88時取不同a值的性能比較Table 2 Comparative results of different a values with b=0.88

3.2 數值實驗和結果分析

實驗中，分別用LDIW策略 PSO算法和LgDW策略PSO算法對4個測試函數進行計算，參數取值 wmax=1.2，wmin=0.1，c1=c2=2.0，a=30，b=0.88，隨機運行50次，粒子數為30.實驗所得的各測試函數平均最優適應值進化情況如圖2～圖5所示，數值結果如表3所示.

由進化曲線圖可以看出:除了單峰Sphere函數，在優化多峰值的復雜函數(Rastrigrin函數、Griewank函數和Schaffer函數)方面，LgDW策略PSO算法都能較快地收斂于最優解，優于線性遞減策略的PSO算法.這主要是較大的慣性權重有利于全局探索，而較小的慣性權重有利于算法的局部開發，加速算法的收斂.

由實驗所得的數值結果可以看出:LgDW策略PSO算法對于后面3個多峰函數的優化，最優值、均值及方差均有所改善，其主要原因是在初期較大的慣性權重能增大算法的搜索能力，保持了種群的多樣性;而在Sphere函數和高維的Griewank函數改善較小，是因為Sphere函數為單峰函數，而超過15維后Griewank函數特性趨于單峰.說明LgDW策略PSO算法對于多峰值復雜函數具有一定的優越性.

圖2 Sphere函數平均最優適應值進化曲線Fig.2 Comparative evolutionary process on Sphere

圖3 Rastrigrin函數平均最優適應值進化曲線Fig.3 Comparative evolutionary process on Rastrigrin

圖4 Griewank函數平均最優適應值進化曲線Fig.4 Comparative evolutionary process on Griewank

圖5 Schaffer函數平均最優適應值進化曲線Fig.5 Comparative evolutionary process on Schaffer

表3 數值結果統計Table 3 Comparative results of LDIW and LgDW on Test Problems

4 結論

作為新的進化計算方法，粒子群優化(PSO)給大量非線性、不可微和多峰值復雜問題的優化提供了一種新的思路.本文根據PSO算法慣性權重在優化問題過程中的表現特征，提出了一種基于Logistic模型的動態慣性權重的LgDW策略，數值實驗表明:LgDW策略對于多峰值的復雜函數的優化體現出了較好的性能，具有一定的優越性.

［1］ Kennedy J，Eberhart R C.Particle Swarm Optimization［C］//Proc of IEEE Int Conf on Neural Networks.Perth:IEEE，1995:1942-1948.

［2］ Shi Y，Eberhart R C.A Modified Particle Swarm Optimizer［C］//Proceedings of the IEEE Congress on Evolutionary Computation.Now York:IEEE，1998:303-308.

［3］ Shi Y，Eberhart R C.Parameter Selection in Particle Swarm Optimization［C］//In Proceedings of the Seventh Annual Conference on Evolutionary Programming.New York:Springer-Verlag，1998:591-600.

［4］ Shi Y，Eberhart R C.Fuzzy Adaptive Particle Swarm Optimization［C］//The IEEE Congress on Evolutionary Computation.San Francisco:IEEE，2001:101-106.

［5］ Eberhart R C，Shi Y.Tracking and Optimization Dy-namic Systems with Particle Swarms［C］//The IEEE Congress on Evolutionary Computation.San Francisco:IEEE，2001:94-100.

［6］ Chatterjee A，Siarry P.Nonlinear Inertia Weight Variation for Dynamic Adaptation in Particle Swarm Optimization［J］.Computers and Operations Research，2006，33(3):859-871.

［7］ 陳貴敏，賈建援，韓琪，等.粒子群優化算法的慣性權重遞減策略研究［J］.西安交通大學學報，2006，40(1):53-56.

［8］ 張選平，杜玉平，秦國強，等.一種動態改變慣性權的自適應粒子群算法［J］.西安交通大學學報，2005，39(10):1039-1042.

［9］ Shi Y H，Eberhart R C.Empirical Study of Particle Swarm Optimization［C］//Proc of IEEE Congress on Evolutionary Computation.Washington:IEEE，1999:629.