一種易跳出局部最優的粒子群優化算法

趙維浩，蘇賓，夏筱筠

,（1.中國航空沈陽黎明航空發動機有限責任公司，遼寧沈陽，110043；2.中國科學院沈陽計算技術研究所有限公司，遼寧沈陽，110004）

一種易跳出局部最優的粒子群優化算法

趙維浩1，蘇賓1，夏筱筠2

,（1.中國航空沈陽黎明航空發動機有限責任公司，遼寧沈陽，110043；2.中國科學院沈陽計算技術研究所有限公司，遼寧沈陽，110004）

針對粒子群優化算法（PSO）中出現的極易陷入局部最優的問題，本文提出了一種易跳出局部最優的粒子群優化算法。該算法是在算法陷入局部最優時，通過加大慣性權重來改變群體多樣性，從而使得該算法能夠跳出局部最優。最后，通過大量仿真試驗表明，對于求解高維、多峰等復雜的非線性優化問題，該算法能表現出很好的搜索性能。

粒子群優化算法；局部最優；多樣性；慣性權重

0 引言

粒子群優化算法（PSO）是Kennedy和Eberhart于1995年提出的一種新的智能優化算法，其基本概念源于對鳥類捕食的行為模擬該算法[1]。該算法是一種基于群體的隨機優化方法，系統初始化為一組隨機解和運行速度，采用群體解的相互合作機制，通過迭代搜尋最優值[2]。粒子群優化算法與其他智能算法相比，其概念簡單、容易實現，并且需要調節的參數較少，具有較強的全局收斂能力和魯棒性，且不需要借助問題的特征信息，非常適用于對復雜環境中的優化問題的求解。雖然粒子群優化算法有許多優點，但也存在著易陷入局部最優，進化后期收斂速度慢，精度較差等缺點[3]。為了克服粒子群優化算法的這些缺點,研究人員提出了許多改進的粒子群優化算法。其改進方法的主要目的是通過混合其它智能優化算法或改進控制參數取值來改變群體的多樣性，使該算法能夠跳出局部最優。

對于通過改變慣性權重而改進該算法的方法主要是線性遞減和非線性遞減兩種，這兩種方法在陷入局部最優時，慣性權重較小，并不能更好的改變群體多樣性，從而使該類算法容易陷入局部最優。本文通過研究慣性權重對全局探測能力和局部搜索能力的影響，提出一種易跳出局部最優的粒子群優化算法，通過非遞減函數改變慣性權重，提高粒子群優化算法的速度和效率。

1 易跳出局部最優的粒子群優化算法

1.1 粒子群優化算法

粒子群優化算法的基本過程為[4]：設算法中粒子群個數為N，搜索空間的維度為D維，其中第i個粒子用向量Xi=(xi1,xi2…,xiD)表示，速度用向量Vi=(vi1,vi2…,viD)表示，到目前為止，該粒子搜索到的最優位置用向量Pi(k)=(pi1(k),pi2(k)…,piD(k ))表示，整個粒子群搜索到的最優位置用向量Pg(k)=(pg1(k),pg2(k)…,pgD(k ))表示。在搜索過程中，每個粒子的位置和速度按如公式(1)和(2)進行變化：

其中，c1和c2為加速因子，分別用于調節粒子飛向自身最好位置方向的步長和調節粒子向全局最好位置飛行的步長；r1和r2是[0,1]中的隨機數，為了控制在迭代過程中，粒子的搜索空間； 1dD≤≤；ω為慣性因子。

粒子群優化算法在搜索過程中存在易陷入局部最優的 缺點。由公式(1)可知，當xid(k)=pid(k)=pgd(k )（1≤d≤D，D為搜索空間維度）時，粒子的飛行速度僅由ω(k )和vid(k)決定；若ω(k )≠0且vid(k)≠0， 則粒子將按原有軌跡飛行； 若ω(k)=0且vid(k)=0，一旦所有粒子滿足xid(k)=pid(k)=pgd(k )時，則它們將停止飛行，并收斂于局部最優解[5]。因此，需要提高算法的全局搜索能力。

1.2 跳出局部最優方法

為了克服上述基本粒子群優化算法的不足，本文采用動態改變慣性權重的方法使其跳出局部最優。常用的動態改變慣性權重的方法主要分為線性遞減[6]和非線性遞減，由于使用遞減函數改變慣性權重，當粒子群算法陷入局部最優時，慣性權重也變得比較小，有時甚至接近于最小值。因此需要一個函數來滿足當粒子群算法陷入局部最優時，慣性權重變得比較大，這樣算法就不會停止，繼續搜索，從而跳出局部最優。因此這樣的函數應滿足先遞增后遞減，基本在陷入局部最優時達到最大值。

根據以上分析本文提出一個二次函數用于動態改變慣性權重，其函數應滿足如下公式：

其中，k為當前迭代次數。對于常數a、b和c的取值，通過找到函數應滿足的三個坐標點，從而計算出該二次函數。如：ω?ωmin的函數過點(0,0)、(M/2, ωmax?ωmin)和(M,0)，則動態改變慣性權重的函數為：其中，maxω為最大慣性因子；minω為最小慣性因子；M為最大迭代次數；k為當前迭代次數。

1.3 算法流程

易跳出局部最優的粒子群優化算法流程為：

（1） 設置最大迭代次數M，設置加速因子c1和c2；慣性權重最大值和最小值，和三個坐標，確定動態改變慣性權重函數。

（2）在D維空間中，初始化粒子群的位置X1=(x11,x12…,x1D)和速度V1=(v11,v12…,v1D)，同時初始化粒子當前的最優適應度值和最優位置，全局最優適應度值和最優位置。

（3）根據動態改變慣性權重函數，即公式(4) 動態改變慣性權重。

（4） 根據公式(1)和(2)更新粒子的位置和速度。

（5） 根據適應度函數，更新粒子當前的最優適應度值和最優位置，全局最優適應度值和最優位置。

（6） 判斷當前迭代次數j,若j

2 實驗及結果分析

2.1 測試函數

為了驗證改進的粒子群優化算法的性能，本文采用3個標準測試函數（見表1）進行實驗驗證，其中3個標準測試函數的維數都設為20。測試函數的特點為：函數1是單峰函數，各個變量之間沒有相互作用；函數2是一個復雜的單峰病態函數，其部分變量之間的關聯性特別強，全局極值點分布區域特別小，所以運用傳統的方法很難找到較好值；函數3是多峰函數，變量之間相互獨立，有大量的局部極小值，因此很容易陷入局部最優。

表1 3個標準測試函數

2 Rosenbrock ()()()2fxxxx =∑niii i=1■1001■?+?■2+1■?≤≤3030xin 3 Rastrigin ()() fxxxπ =?+∑(2i10cos210i)?≤≤55xii=1

2.2 參數設置

由于3個標準函數相對比較簡單，因此實驗仿真時，算法迭代次數設為20；種群大小設為100；加速因子c1和c2都設為2.0；慣性權重的最大值設為1.5，最小值設為0.5；則ω?ωmin的函數過點(0,0)、(10, 1)和(20,0)，則動態改變慣性權重的函數為：

其中，k為當前迭代次數。

2.3 實驗結果及分析

為了驗證本文算法的性能，本文將算法與基本的粒子群優化算法PSO和文獻[6]提出的線性遞減慣性權重的粒子群優化算法MPSO進行比較。其中圖1為函數1的3種函數的比較結果，由于函數1為單峰函數，因此3種算法都不會陷入局部最優，所以3種算法比較結果中，線性遞減慣性權重的粒子群優化算法與本文算法性能相當。

圖1 算法性能比較（函數1）

盡管函數2是一個復雜的單峰病態函數，其部分變量之間的關聯性特別強，全局極值點分布區域特別小，但是函數2仍是單峰函數，因此圖2中作為函數2的3種算法的比較結果，同樣看不出本文算法性能的優越性。

圖2 算法性能比較（函數2）

圖3為函數3的3種算法的比較結果，由于函數3是多峰函數，有大量的局部極小值，因此很容易陷入局部最優。從圖3的比較中可以看到當線性遞減慣性權重的粒子群優化算法陷入局部最優時，不能跳出局部最優找到最優解，而本文算法卻能跳出局部最優，找到最優解。因此對于求解高維、多峰等復雜的非線性優化問題，該算法能夠跳出局部最優，進而找到全局最優。

圖3 算法性能比較（函數3）

3 結論

改變慣性權重，能夠使算法在陷入局部最優時，通過增大慣性權重，跳出局部最優，進而找到全局最優解。測試函數的實驗結果表明，對于高維、多峰等復雜的非線性優化問題，采用改進的粒子群優化算法能夠使函數擺脫局部極值點，通過迭代最終找到全局最優解。

[ 1 ] Kennedy J, Eberhart R C. Particle Swarm Optimization[C]. Proceedings of the IEEE International Conference on Neural Networks, IV. Piscataway, NJ: IEEE Service Center, 1995: 1942-1948.

[ 2 ] 徐從東,陳春.一種自適應動態控制參數的粒子群優化算法[J].計算機工程,2013,10(39):203-207.

[3]吳昌友,王福林,馬力.一種新的改進粒子群優化算法[J].控制工程, 2010,3(17):359-362.

[ 4 ]張安玲,王中.一種混合粒子群優化算法的研究[J].計算機工程與應用, 2011,47(31):27-37.

[ 5 ]劉愛軍,楊育,李斐等.混沌模擬退火粒子群優化算法研究[J].浙江大學學報,2013,10(47):1722-1730.

[ 6 ] Ai-Qin Mu, De-Xin Cao, Xiao-Hua Wang. A Modified Particle Swarm Optimization Algorithm[J]. Natural Science, 2009,2(1):151-155.

A Particle Swarm Optimization Algorithm of Easily Skipping Local Optimum

Zhao Weihao1，Su Bin1，Xiao Xiaojun2
（1.AVIC Shenyang Liming Aero-engine(Group) Corporation Ltd，Shenyang Liaoning,110043; 2.Shenyang Institute of Computing Technology, Chinese Academy of Sciences, Shenyang Liaoning,110004）

Aiming at the problem that the particle swarm optimization (PSO) algorithm falls into local optimum. This paper proposes a particle swarm optimization algorithm of easily skipping local optimum. This algorithm can get out of local optimum by ramping up inertia weight that can change the variety of group, when it traps into local optimum. At last, a great of simulation results show that this algorithm can have excellent search performance for solving the multi-dimension and multi-peak nonlinear optimization questions.

particle swarm optimization; local optimum; diversity; inertia weight