一種改進(jìn)的動(dòng)態(tài)慣性權(quán)重粒子群優(yōu)化算法

李 艷，楊華芬

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

0 引言

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

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

1 基本粒子群算法

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

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

2 算法描述及仿真實(shí)驗(yàn)

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

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

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

2.1 本文的算法

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

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

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

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

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

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

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

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

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

2.2 仿真實(shí)驗(yàn)

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

1）Sphere函數(shù)

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

2）Rastrigrin函數(shù)

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

3）Noisy Quadric函數(shù)

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

4）Rosenbrock函數(shù)

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

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

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

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

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

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

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

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

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

在優(yōu)化Rosenbrock函數(shù)時(shí)，前6代進(jìn)化速度比較快，從第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)化時(shí)，前面10代的進(jìn)化速度比較快，從第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)的能力要比基本粒子群算法要強(qiáng)，可以較好平衡求精和求泛的能力。

3 結(jié)語(yǔ)

在粒子群算法中，慣性權(quán)值是較為重要的參數(shù)，它的取值直接關(guān)系到算法的性能。本文從算法進(jìn)化速度和粒子的集聚程度考慮，提出動(dòng)態(tài)變化的慣性權(quán)重機(jī)制，讓權(quán)重根據(jù)算法的運(yùn)行狀態(tài)動(dòng)態(tài)變化，控制了粒子的搜索范圍，使粒子較好地平衡全局和局部搜索能力。和傳統(tǒng)的粒子群優(yōu)化算法相比，進(jìn)一步說(shuō)明固定的慣性權(quán)重在實(shí)際應(yīng)用中受到很大的限制。對(duì)幾種典型函數(shù)的測(cè)試實(shí)驗(yàn)表明，本文算法既能保持傳統(tǒng)粒子群算法的簡(jiǎn)單，搜索速度快的特點(diǎn)，還能跳出局部最優(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ā)動(dòng)機(jī)故障診斷研究［J］.計(jì)算機(jī)仿真，2014，31（3）：171－174.

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

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

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

［6］趙越，起嵩正.多樣性P S O＿S V R油氣操作成本時(shí)間序列預(yù)測(cè)模型［J］.計(jì)算機(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］趙志剛，黃樹運(yùn)，王偉倩.基于隨機(jī)慣性權(quán)重的簡(jiǎn)化粒子群優(yōu)化算法 ［J］.計(jì)算機(jī)應(yīng)用 研究，2014，31（2）：361－363.

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

［10］高衛(wèi)峰，劉三陽(yáng).一種高效粒子群優(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］王曉佳，張寶霆，徐達(dá)宇.含有壓縮因子的粒子群優(yōu)化灰色模型在智能電網(wǎng)中的應(yīng)用［J］.運(yùn)籌與管理，2012，21（3）：114－118.