李 艷，楊華芬

（曲靖師范學(xué)院計算機科學(xué)與工程學(xué)院，云南 曲靖655011）

0 引言

粒子群算法（Particle Swarm Optimization，PSO）是一種進化算法［1］，它和其他智能算法一樣：隨機初始化種群，通過多次迭代尋優(yōu)，根據(jù)個體當(dāng)前的信息進行更新。和其他算法相比，PSO算法具有結(jié)構(gòu)簡單、參數(shù)較少、易于描述和實現(xiàn)、全局搜索能力較強、無需梯度信息等諸多特點，這使其在函數(shù)優(yōu)化、多目標(biāo)問題求解、模式識別等諸多領(lǐng)域得到廣泛應(yīng)用［2－6］，尤其適用于非線性、多極值和不可微且多變量復(fù)雜優(yōu)化問題的求解。盡管PSO算法有很多優(yōu)點，但是基本粒子群算法還是存在早熟收斂，難以平衡全局和局部搜索能力等問題，若不加以改進，將影響其應(yīng)用領(lǐng)域。常見的方法有：引入慣性權(quán)重因子［7－8］、收縮因子和自適應(yīng)變異算子［9－10］、線性遞減方法［11］、模糊自適應(yīng)方法［12］、距離信息方法［13］、帶壓縮因子的PSO算法［14］等。盡管提出的粒子群改進算法在性能和效率上都有一定程度的改善，但很難達到在避免早熟收斂的同時提高算法的局部搜索能力。

為了較好地平衡算法全局和局部搜索能力，提高算法的搜索效率和精度，本文提出一種改進的動態(tài)慣性權(quán)重粒子群優(yōu)化算法。改進慣性權(quán)重的同時考慮粒子的集聚程度和算法的進化速度：當(dāng)粒子的多樣性較低，則容易陷入局部最優(yōu)，此時應(yīng)增大慣性權(quán)重，避免算法陷入局部最優(yōu)；當(dāng)粒子的多樣性較好，此時集聚程度較低，為防止算法成為隨機搜索，應(yīng)降低慣性權(quán)值。改進算法能較好地平衡算法的求精和求泛的能力，同時還能提高算法的搜索效率和精度。

1 基本粒子群算法

在D維搜索空間中，由N個粒子組成的種群X ＝（X1，X2，…，XN），第i個粒子表示為一個D 維向量Xi＝ （xi1，xi2，…，xiD），i＝1，2，…，N。第i個粒子的速度為Vi＝ （vi1，vi2，…，viD）。粒子i找到的最優(yōu)位置表示為Pi＝ （pi1，pi2，…，piD），群體找到的最優(yōu)位置為Pg＝ （pg1，pg2，…，pgD）。粒子i分別根據(jù)式（1）和式（2）更新速度和位置。

式中：n為當(dāng)前進化的代數(shù)，i＝1，…，N；c1和c2為學(xué)習(xí)因子，且c1＞0，c2＞0；rand為均勻分布于（0，1）的隨機數(shù)；w為慣性權(quán)重，它決定粒子原來的速度對現(xiàn)在速度的影響程度，起到平衡全局搜索和局部搜索能力的作用。

2 算法描述及仿真實驗

從基本的粒子群更新速度和位置的公式（1）和（2）可以看出：粒子速度的改變由3個因素決定：1）慣性權(quán)重表明當(dāng)前速度與前速度之間的關(guān)系，很多學(xué)者認為：慣性系數(shù)決定搜索步長，較大有利于全局搜索，較小有利于局部探索；2）認知因子c1反映粒子的搜索能力；3）探索因子c2，也稱全局學(xué)習(xí)因子，或者稱為社會共享能力系數(shù)，表示粒子之間的信息共享與合作能力。適當(dāng)調(diào)整慣性權(quán)重，可以平衡粒子的全局和局部搜索能力。粒子的慣性權(quán)重極大影響算法的尋優(yōu)效果，慣性權(quán)重應(yīng)該隨著粒子群的進化速度和集聚程度不斷的調(diào)整，以提高算法的尋優(yōu)效率。在進化過程中，每個粒子的進化速度不盡相同，為讓慣性權(quán)重隨著粒子群的進化速度和集聚程度自適應(yīng)的變化，本文提出一種基于集聚度和進化速度的動態(tài)變化的慣性權(quán)重調(diào)整方法。

粒子的集聚度越高，ct的值越大，粒子的多樣性越差，搜索容易陷入局部最優(yōu)，應(yīng)增大慣性權(quán)值，幫助算法跳出局部最優(yōu)，提高算法全局搜索能力；粒子的集聚程度越低，ct的值越小，粒子的多樣性越好，全局搜索能力越強，為平衡粒子全局和局部搜索能力，防止算法變成隨機搜索，應(yīng)適當(dāng)降低慣性權(quán)值。為了能夠讓慣性權(quán)值自適應(yīng)的改變，慣性權(quán)值可以表示為ct和的函數(shù)，即

式中：wini為w的初始值，通常wini＝1；wv和wc分別為和ct的比例因子。

2.1 本文的算法

在上述討論的基礎(chǔ)上，本文提出一種改進的粒子群算法，該算法在運行過程中，w的值根據(jù)和ct動態(tài)調(diào)整，初始狀態(tài)下，wv＝0，wc＝0。本文提出的算法步驟如下：

1）初始化粒子的位置和速度，計算粒子的適應(yīng)度；

2）初始化粒子的全局最優(yōu)值和個體最優(yōu)值；

3）如果算法收斂達到精度要求或達到最大迭代次數(shù)，則執(zhí)行步驟7），否則執(zhí)行步驟4）；

4）根據(jù)式（3）、式（4）和式（5），分別計算sti，ct和wti；

5）根據(jù)式（1）和式（2）分別更新粒子的速度和位置，計算粒子的適應(yīng)度，更新粒子群的全局最優(yōu)值和個體最優(yōu)值；

6）將迭代次數(shù)加1，并執(zhí)行步驟3）；

7）輸出最優(yōu)個體，算法結(jié)束。

該算法考慮到粒子的進化速度和集聚程度對算法尋優(yōu)的影響，如果粒子太過于集聚，則種群的多樣性較差，容易陷入局部最優(yōu)，此時應(yīng)該增大慣性權(quán)值，增加粒子的多樣性，擴大算法的搜索范圍。本文采用適應(yīng)度方差來度量粒子的集聚程度，方差越大，粒子的集聚程度越低，種群的多樣性越好；方差越小，粒子的集聚程度越高，種群的多樣性越差。為平衡算法全局不局部尋優(yōu)能力，當(dāng)進化速度較快時，應(yīng)該減小算法全局搜索能力，提高局部搜索能力，以免錯過較好的位置。由于每個粒子的進化速度各不相同，因此本文針對各個粒子提出自己的進化速度。由此可以看出，本文提出的算法不僅可以平衡局部和全局的搜索能力，還可以提高算法的效率，避免算法陷入局部最優(yōu)。

2.2 仿真實驗

為驗證本文算法的有效性，與傳統(tǒng)的PSO算法進行比較。采用4個典型測試函數(shù)進行實驗，函數(shù)如下：

1）Sphere函數(shù)

Sphere函數(shù)是一個單峰二次函數(shù)病態(tài)函數(shù)，全局極小點在x＝（0，0，…，0）處，全局極小值為f（x）＝0。該函數(shù)是一個病態(tài)函數(shù)，只有一個極小點，但難以尋優(yōu)，搜索區(qū)域為xi∈ ［－10，10］。

2）Rastrigrin函數(shù)

Rastrigrin函數(shù)在x＝ （0，0，…，0）處取得全局極小值，極小點值為f（x）＝0，搜索區(qū)域為xi∈ ［－5.12，5.12］。

3）Noisy Quadric函數(shù)

Noisy Quadric函數(shù)在x＝ （0，0，…，0）處取得最優(yōu)值0，搜索區(qū)域為xi∈ ［－1.28，1.28］。

4）Rosenbrock函數(shù)

Rosenbrock函數(shù)在x＝（1，…，1）處取得最優(yōu)值0，搜索區(qū)域為xi∈ ［－5，10］。

用傳統(tǒng)粒子群算法和本文算法優(yōu)化每一個函數(shù)都采用同一組規(guī)模為40的粒子，進化1 000代，每個函數(shù)的維度都為30。用2種算法優(yōu)化上述4個函數(shù)，優(yōu)化1 000代得到的最優(yōu)值的變化情況分別如圖1～4所示。

圖1 Sphere函數(shù)進化1 000代最優(yōu)值的變化情況

圖2 Rastrigrin函數(shù)進化1 000代最優(yōu)值的變化情況

圖3 Noisy Quadric函數(shù)進化1 000代最優(yōu)值的變化情況

圖4 Rosenbrock函數(shù)進化1 000代最優(yōu)值的變化情況

優(yōu)化Sphere函數(shù)時，基本粒子群算法在前10代進化速度非?？欤?0代以后進化速度非常慢，600代以后基本就陷入局部最優(yōu)0.850 512 221 140 020；用本文算法優(yōu)時，經(jīng)過10代的進化，最優(yōu)值降低到0.1左右，此后進化速度減慢，最終得到最優(yōu)值0.100 512 221 140 020。

在優(yōu)化Rastrigrin函數(shù)時，基本粒子群算法在30代以前進化速度較快，從第1代的最優(yōu)值2.985 226 741 101 385降低到第30代的0.892 207 868 042 702，此后進化速度較慢，最終得到最優(yōu)值0.737 767 653 668 991；本文算法在前13代進化比較快，從第1代的最優(yōu)值2.985 226 741 101 385降低到第13代的0.997 335 940 729 150，此后進化速度降低，得到最優(yōu)值0.205 362 085 666 930。

在優(yōu)化Noisy Quadric函數(shù)時，基本粒子群算法在前面3代進化速度較快，從第1代的最優(yōu)值1.747 821 696 213 246降低到第3代的0.568 825 851 997 124，此后進化速度非常的慢，最后得到最優(yōu)值0.513 012 935 365 487。

在優(yōu)化Rosenbrock函數(shù)時，前6代進化速度比較快，從第1代的最優(yōu)值9.192 361 368 484 599下降到第6代的最優(yōu)值0.677 038 897 510 543，最終得到最優(yōu)值0.151 365 801 046 284；用本文算法優(yōu)化時，前面10代的進化速度比較快，從第1代的最優(yōu)值9.192 361 368 484 599降低到第10代的最優(yōu)值0.010 392 238 053 912，最后得到最優(yōu)值0.007 303 451 374 953。

由此可以看出，本文的算法在跳出局部最優(yōu)的能力要比基本粒子群算法要強，可以較好平衡求精和求泛的能力。

3 結(jié)語

在粒子群算法中，慣性權(quán)值是較為重要的參數(shù)，它的取值直接關(guān)系到算法的性能。本文從算法進化速度和粒子的集聚程度考慮，提出動態(tài)變化的慣性權(quán)重機制，讓權(quán)重根據(jù)算法的運行狀態(tài)動態(tài)變化，控制了粒子的搜索范圍，使粒子較好地平衡全局和局部搜索能力。和傳統(tǒng)的粒子群優(yōu)化算法相比，進一步說明固定的慣性權(quán)重在實際應(yīng)用中受到很大的限制。對幾種典型函數(shù)的測試實驗表明，本文算法既能保持傳統(tǒng)粒子群算法的簡單，搜索速度快的特點，還能跳出局部最優(yōu)，提高算法的搜索效率和精度。

［1］Shi Y，Eberhart R C.A modified particle swarm optimizer［C］／／Evolutionary Computation Proceedings，IEEE World Congress on Computational Intelligence.，The 1998IEEE International Conference.Anchorage，AK：IEEE，1998：69－73.

［2］趙曦，李穎，徐江，等.基于PSO－SVM 的發(fā)動機故障診斷研究［J］.計算機仿真，2014，31（3）：171－174.

［3］趙衛(wèi)偉，潘宏俠.基于PSO參數(shù)優(yōu)化的支持向量機齒輪箱故障診斷研究［J］.機床與液壓，2014，42（7）：152－154.

［4］劉巖.增強學(xué)習(xí)的PID控制參數(shù)優(yōu)化快速整定算法［J］.計算機測量與控制，2014，22（2）：467－479.

［5］張春.PID控制參數(shù)優(yōu)化在合成氨控制系統(tǒng)中的應(yīng)用［J］.計算機仿真，2013，30（5）：366－369.

［6］趙越，起嵩正.多樣性P S O＿S V R油氣操作成本時間序列預(yù)測模型［J］.計算機仿真，31（1）：96－102.

［7］ZHAN Zhi－Hui，ZHANG Jun，LI Yun，et al.Adaptive particle swarm optimization［J］.IEEE Transactions On Systems Man And Cybernetics Part B－cybernetics，2009，39：1362－1381.

［8］趙志剛，黃樹運，王偉倩.基于隨機慣性權(quán)重的簡化粒子群優(yōu)化算法 ［J］.計算機應(yīng)用 研究，2014，31（2）：361－363.

［9］申元霞，王國胤，曾傳華.相關(guān)性粒子群優(yōu)化模型［J］.軟件學(xué)報，2011，22（4）：695－708.

［10］高衛(wèi)峰，劉三陽.一種高效粒子群優(yōu)化算法［J］.控制與決策，2011，26（8）：1158－1162.

［11］Khare A，Rangnekar S.A review of particle swarm optimization and its applications in SolarPhotovoltaic system［J］.Applied Soft Computing，2013，13：2997－3006.

［12］Valdez F，Melin P，Castillo O.An improved evolutionary method with fuzzy logic for combining particle swarm optimization and genetic algorithms［J］.Applied Soft Computing，2011，11：2625－2632.

［13］Marinakis Y，Marinaki M.Particle swarm optimization with expanding neighborhood topology for the permutation flowshop scheduling problem［J］.Soft Computing，2013，17：1159－1173.

［14］王曉佳，張寶霆，徐達宇.含有壓縮因子的粒子群優(yōu)化灰色模型在智能電網(wǎng)中的應(yīng)用［J］.運籌與管理，2012，21（3）：114－118.