一種混沌變參數(shù)粒子群優(yōu)化算法

虎濤濤,單要楠

(1.電子科技大學電子科學技術研究院，四川 成都 611731；2.電子科技大學數(shù)學科學學院，四川 成都 611731)

一種混沌變參數(shù)粒子群優(yōu)化算法

虎濤濤1,單要楠2

(1.電子科技大學電子科學技術研究院，四川 成都 611731；2.電子科技大學數(shù)學科學學院，四川 成都 611731)

粒子群優(yōu)化算法存在易陷入局部最優(yōu)、收斂精度低、進化后期收斂慢等問題，混沌粒子群優(yōu)化算法利用混沌運動的遍歷性、隨機性、規(guī)律性特點，很好地解決了粒子群優(yōu)化算法陷入局部最優(yōu)的問題，但混沌初始化會破壞已收斂的種群結構。在混沌粒子群優(yōu)化算法的基礎上，提出了一種混沌變參數(shù)粒子群優(yōu)化算法。對陷入局部最優(yōu)的種群進行混沌初始化，并采取一定的規(guī)則動態(tài)改變混沌運動的控制參數(shù)，以增強或減弱混沌方程的混沌特性，既可以減輕混沌初始化對已收斂種群結構的破壞性，又能利用混沌特性擺脫種群陷入局部最優(yōu)問題，提高收斂精度，從而提高算法的全局尋優(yōu)能力。通過仿真測試表明，混沌變參數(shù)的粒子群優(yōu)化算法能有效避免種群陷入局部最優(yōu)現(xiàn)象，收斂快、收斂精度高，全局尋優(yōu)能力優(yōu)于基本粒子群優(yōu)化算法。

粒子群優(yōu)化算法； 混沌運動； 變參數(shù)； 局部最優(yōu)； 收斂； 優(yōu)化

0 引言

Kennedy和Eberhart于1995年提出粒子群優(yōu)化(particle swarm optimization，PSO)算法[1]。該算法具有原理簡單、易于實現(xiàn)、收斂速度快的優(yōu)點，被廣泛應用于目標函數(shù)優(yōu)化、自適應控制、神經(jīng)網(wǎng)絡等領域[2-3]，與其他進化算法一樣，PSO算法同樣存在易陷于局部最優(yōu)、優(yōu)化計算精度低、后期收斂慢的缺點。針對這些缺點，學者們提出了很多改進的粒子群算法[4-6]。盡管這些改進算法能解決局部最優(yōu)的問題，但在收斂性能上仍存在一定的不足，效果并不理想。本文根據(jù)混沌運動的隨機性、遍歷性等特點[7]，提出一種混沌變參數(shù)粒子群優(yōu)化算法。對典型函數(shù)的仿真測試表明，與混沌粒子群優(yōu)化算法和基本粒子群優(yōu)化算法相比，混沌變參數(shù)粒子群優(yōu)化算法在保證算法能擺脫局部最優(yōu)的基礎上，收斂性能明顯提高。

1 粒子群優(yōu)化算法

PSO算法的思想源于對鳥群捕食行為的研究與模擬，是一種基于群體的智能優(yōu)化算法。基本粒子群優(yōu)化算法，又稱為標準粒子群算法(standard particle swarm optimization,SPSO)，其在粒子群優(yōu)化算法中引入了慣性權重系數(shù)，以平衡粒子的搜索能力，保證算法的局部尋優(yōu)能力和全局尋優(yōu)能力。

基本粒子群優(yōu)化算法中，粒子每次通過兩個值來更新自己的位置，一個為粒子自身的最優(yōu)解，另一個為種群所有粒子找到的最優(yōu)解，用數(shù)學方法描述如下。

假設粒子種群的群體規(guī)模為N，每個粒子在D維空間進行搜索，則xi=(xi1,xi2,...,xid)是第i個粒子的當前搜索位置，xid是第i個粒子的第d維空間位置，vi=(vi1,vi2,...,vid,...,viD)是第i個粒子的當前飛行速度，vid是第i個粒子的第d維空間飛行速度。設f(x)為目標函數(shù)，即適應度函數(shù)；pi=(pi1,pi2,...,pid,...,piD)是第i個粒子所經(jīng)歷的最優(yōu)位置，稱為個體最優(yōu)；pg(pg1,pg2,...,pgd,...,pgD)是群體中所有粒子所經(jīng)歷的最優(yōu)位置，稱為全局最優(yōu)，并且全局最優(yōu)位置pg只有一個。設當前迭代次數(shù)為k，則粒子的當前位置xi和飛行速度vi按照以下兩式來更新：

(1)

(2)

個體最優(yōu)位置pi和全局最優(yōu)位置pg由以下兩式確定：

(3)

(4)

以上公式中：i=1,2,...N;d=1,2,...,D;w為慣性因子，用于修正自身原有飛行速度，通常在[0.1，0.9]之間取值;c1、c2為學習因子，一般取常數(shù)2;rand1、rand2為兩個相互獨立、并在[0，1]之間取值的隨機數(shù)。

基本粒子群優(yōu)化算法具有操作簡單、實現(xiàn)容易、收斂速度快、無需確定太多參數(shù)等優(yōu)點。但根據(jù)文獻[2]對基本粒子群優(yōu)化算法中粒子位置和飛行速度的收斂性分析可知，基本粒子群優(yōu)化算法在進化后期收斂速度比較慢，收斂精度降低，容易陷入局部最優(yōu)值；同時，由于粒子停滯使種群喪失多樣性，會導致算法早熟收斂?；煦?Chaos)是自然界普遍存在的非線性現(xiàn)象，是由確定方程得到的非確定隨機運動狀態(tài)，具有隨機性、便利性及規(guī)律性等特點，它對初始條件極度敏感，能在一定范圍內不重復地遍歷所有狀態(tài)。本文根據(jù)混沌運動的這些特點，提出一種混沌變參數(shù)粒子群優(yōu)化算法。

2 混沌變參數(shù)粒子群優(yōu)化算法

混動運動變化過程看似雜亂無章，但其并不是完全混亂，而是含有內在的規(guī)律性[8]。呈現(xiàn)混沌狀態(tài)的變量稱為混沌變量，其對初值極其敏感。一個混沌變量在一定范圍內有如下特點：①隨機性，即它的表現(xiàn)同隨機變量一樣雜亂；②遍歷性，即它可以不重復地遍歷空間內的所有狀態(tài)；③規(guī)律性，該變量是由確定的迭代方程確定的。Logistic方程是一個典型的混沌系統(tǒng)，其公式為：

xn+1=μ×xn×(1-xn)

(5)

式中：μ為混沌控制參數(shù)，其決定Logistic方程的混沌程度，μ值越大，混沌程度越高，一般在[0，4]之間取值，xn∈[0,1]。

利用混沌對初值敏感的特點，給式(5)賦i個具有微小差異的初值，即可得到i個混沌變量。

由于混沌變量的遍歷性、隨機性有助于增強種群的搜索能力[9]，因此，為解決基本粒子群算法中出現(xiàn)的陷入局部最優(yōu)、收斂精度低等問題，很多學者將混沌思想和粒子群優(yōu)化算法相結合，提出了混沌粒子群優(yōu)化算法(chaotic particle swarm optimization,CPSO)。戴冬雪等在算法的初始階段，對粒子的位置混沌初始化；而在算法運行過程中，根據(jù)群體適應度方差來自適應地對粒子的位置進行混沌更新[10]。張勁松等以基本粒子群優(yōu)化算法的運算流程作為主體流程，當整個粒子群歷史全局最優(yōu)位置pg連續(xù)不變化或變化極小時，將混沌搜索機制引入其中，在以pg為中心的一定范圍內進行混沌搜索，將混沌搜索得到的最優(yōu)解作為新的pg，并繼續(xù)原粒子群算法的求解[11]。按概率方式來決定混沌搜索的時間，在進化初期，以較小的概率進行混沌搜索；在進化后期，以接近1的概率進行混沌搜索[12]。

混沌控制參數(shù)μ越大，混沌程度越高，對種群結構的破壞性越大，在算法運行過程中，根據(jù)種群的收斂情況，動態(tài)地減小或增大控制參數(shù)μ，就可以減少對種群結構的破壞，同時擺脫陷入局部最優(yōu)的困境。因此，本文提出的基于混沌變參數(shù)的粒子群優(yōu)化算法的思想是：在算法運行過程中，利用群體適應度方差進行早熟收斂判斷。當發(fā)現(xiàn)種群陷入局部最優(yōu)時，保留粒子群個體最優(yōu)解，混沌初始化粒子群，根據(jù)準則判斷目前粒子群收斂情況，并根據(jù)一定的規(guī)則動態(tài)增大或減小混沌控制參數(shù)μ，減少對已收斂種群結構的破壞，這樣在保證收斂速度的基礎上，既能擺脫種群陷入局部最優(yōu)的現(xiàn)象，又能提高收斂精度和全局優(yōu)化能力，其算法具體的流程描述如下。

①初始化參數(shù)。種群規(guī)模為N，粒子搜索空間維數(shù)為D，學習因子為c1、c2,慣性因子最大值為wmax，最小值為wmin，混沌控制參數(shù)為μ，迭代次數(shù)為T。

②混沌初始化種群。隨機產生一組取值區(qū)間為[0,1]的變量z1=(z11,z12,...,z1d,...,z1D)，利用Logistic方程產生(N-1)個混沌變量z2,z3,..,zN，并根據(jù)式子xi=xmin+(xmax-xmin)zi,將這N個變量映射到粒子位置取值區(qū)間[xmin,xmax]上，生成位置變量。速度變量可以根據(jù)實際情況取位置變量的百分比，根據(jù)適應度函數(shù)f(x)求出初始種群的個體最優(yōu)解pi和全局最優(yōu)解pg。

③根據(jù)式(1)、式(2)更新粒子位置xi和速度vi。

④根據(jù)適應度函數(shù)f(x)求出粒子的適應度，并根據(jù)式(3)、式(4)來更新個體最優(yōu)解pi和全局最優(yōu)解pg。

(6)

如果適應度方差σ2小于所設定的閾值且滿足混沌搜索條件，則保留粒子群個體最優(yōu)解，根據(jù)準則判斷粒子群收斂情況，動態(tài)改變混沌控制參數(shù)，并返回步驟②。對種群重新初始化，再根據(jù)適應度函數(shù)求出粒子的適應度，并與保留的粒子群個體最優(yōu)解比較，確定全局最優(yōu)解；否則繼續(xù)執(zhí)行步驟⑥。

⑥判斷是否滿足終止條件或達到最大迭代次數(shù)T，滿足即跳轉到步驟⑦，否則返回步驟③。

⑦優(yōu)化結束，輸出結果。

3 仿真測試

為了驗證本文提出的變參數(shù)混沌粒子群優(yōu)化算法的收斂性能，現(xiàn)選取三個典型函數(shù)作為測試，并與混沌粒子群優(yōu)化算法、基本粒子群優(yōu)化算法作對比。三個典型函數(shù)分別如下：

變參數(shù)混沌粒子群優(yōu)化算法的初始化參數(shù)如下：種群規(guī)模N為20，位置、速度取值和三個函數(shù)后面的標注保持一致，學習因子c1、c2都為2，慣性因子最大值wmax為1、最小值wmin為0.2，混沌控制參數(shù)μ初始值為4，最大迭代次數(shù)T為1 000。各算法獨立運行50次，測試函數(shù)f(1)、f(2)、f(3)的測試結果如表1所示。

表1 三種函數(shù)的尋優(yōu)測試計算結果

從表1可以看出，混沌粒子群優(yōu)化(CPSO)算法和變參數(shù)混沌粒子群優(yōu)化(變參數(shù)CPSO)算法都能擺脫局部最優(yōu)值。CPSO算法尋優(yōu)要優(yōu)于SPSO算法尋優(yōu)，而變參數(shù)CPSO的全局尋優(yōu)能力最好、收斂精度更高，進而說明其全局尋優(yōu)能力要優(yōu)于混沌粒子群優(yōu)化算法。

采用基本粒子群算法(SPSO)、混沌粒子群算法(CPSO)和變參數(shù)混沌粒子群算法(變參數(shù)CPSO)，得到的測試函數(shù)尋優(yōu)軌跡曲線如圖1所示。

圖1 測試函數(shù)尋優(yōu)軌跡曲線

測試函數(shù)f(1)很難極小化函數(shù)Rosenbrock，很容易找到極小點，但是要跳出這個極小點收斂到全局最小點卻十分困難。而利用混沌運動的特性，可以克服粒子群陷入局部最優(yōu)的情況，圖1(a)中測試函數(shù)f(1)的尋優(yōu)軌跡曲線表明,CPSO算法在算法迭代450次就已收斂，而變參數(shù)CPSO在252次收斂，且收斂精度最高。圖1(b)的尋優(yōu)軌跡曲線表明變參數(shù)CPSO比CPSO算法收斂快。圖1(c)中測試函數(shù)f(3)的尋優(yōu)軌跡曲線表明,CPSO算法在算法迭代263次就已收斂，而變參數(shù)CPSO在85次收斂，且收斂精度最高。以上數(shù)據(jù)充分說明，無論收斂性能，還是克服種群擺脫局部最優(yōu)性能，采用變參數(shù)CPSO算法尋優(yōu)都優(yōu)于采用CPSO算法和SPSO算法尋優(yōu)。變參數(shù)CPSO算法既可以保證種群擺脫局部最優(yōu)的問題，又可明顯改善其收斂性，提高算法的全局尋優(yōu)能力。

4 結束語

混沌變參數(shù)粒子群優(yōu)化算法是在混沌粒子群算法的基礎上，通過動態(tài)改變Logistic方程的混沌控制參數(shù)，使算法在迭代過程中根據(jù)種群收斂狀態(tài)及時增強或減弱混沌運動，以降低對已收斂種群的破壞。根據(jù)仿真測試，混沌變參數(shù)粒子群優(yōu)化算法既保留了混沌粒子群優(yōu)化算法的優(yōu)點，又保持了粒子群體的多樣性，可快速跳出局部最優(yōu)點，尋找全局最優(yōu)解，有效提高了算法的全局尋優(yōu)能力和收斂性能。

[1] KENNEDY J,EBERHART R C. Particle swarm optimization[C]//

Proceedings of IEEE International Conference on Neural Networks,Piscataway(USA):IEEE Press,1995:1942-1948.

[2] 宮玉琳,永磁同步電動機伺服系統(tǒng)自適應逆控制策略研究[D]. 長春：長春理工大學,2013.

[3] GRIMALDI E A,GRIMACCIA F,MUSSETTA M,et al. PSO as an effective learning algorithm for neural network applications[J]. Computational Electromagnetic and Its Applications,2004(3):557-560.

[4] LI J W,CHENG Y M,CHEN K Z. Chaotic particle swarm optimization algorithm based on adaptive inertia weight[C]//Control and Decision Conference. Beijing:IEEE,2014:1310-115.

[5] YAN Z C,LUO Y S. A particle swarm optimization algorithm based on simulated annealing[J]. Advanced Materials Research,2014,989(1):2301-2305.

[6] PAN T S,DAO T K,CHU S C. Hybrid particle swarm optimization with bat algorithm[M]. Switzerland : Springer International Publishing,2015:37-47.

[7] YANG D X,LI G,CHENG G D. On the efficiency of chaos optimization algorithms for global optimization[J]. Chaos,Solions and Fractals,2007,34(4) :1366-1375.

[8] LU H J. A new optimization algorithm based on Chaos[J]. Zhejiang University Science A,2006,7(4) :539-542.

[9] TAVAZOEI M S,HAERI M. An optimization algorithm based on chaotic behavior and fractal nature[J]. Journal of Computational and Applied Mathematics,2007,206(2) :1070-1081.

[10]戴冬雪,王祁,阮永順,等. 基于混沌思想的粒子群優(yōu)化算法及其應用[J]. 華中科技大學學報,2005,33(10):53-55.

[11]張勁松,李歧強,王朝霞. 基于混沌搜索的混合粒子群優(yōu)化算法[J]. 山東大學學報, 2007,37(1):47-50.

[12]楊俊杰，周建中，喻菁，等. 基于混沌搜索的粒子群優(yōu)化算法[J]. 計算機工程與應用,2005(16):69-71.

A Chaotic Particle Swarm Optimization Algorithm with Variable Parameters

HU Taotao1,SHAN Yaonan2

(1.Institute of Electronic Science and Technology,University of Electronic Science and Technology,Chengdu 611731,China；2.School of Mathematical Sciences,University of Electronic Science and Technology,Chengdu 611731,China)

Easy to fall into local optimum,low convergence precision and slow late evolutionary convergence rate are the main problems of particle swarm optimization algorithm,chaotic particle swarm optimization algorithm well solves the problem of falling into local optimum for particle swarm optimization algorithm by using the ergodicity,randomness and regularity of chaotic motion. However,chaos initialization may destroy the structure of population converged;based on the chaotic particle swarm optimization algorithm,a chaotic particle swarm optimization algorithm with variable parameters is proposed. Chaotic initialization is conducted for the population that trapped into local optimum,and certain rules are adopted to dynamically change the control parameters of chaotic motion,to enhance or weaken the chaotic characteristics of the chaotic equation. The destruction of the converged population can be reduced,and the problem of falling into local optimum can be got rid of by using chaotic characteristics,thus the convergence precision and the capability of global optimization are improved. The simulation tests show that the phenomenon of population trapped into local optimum can be effectively avoided by the algorithm proposed,the convergence precision is high,and the capability of optimization is better than of the basic particle swarm optimization algorithm.

Particle swarm optimization algorithm; Chaos motion; Variable parameter; Local optimum; Convergence; Optimization

虎濤濤(1990—)，男，在讀碩士研究生,主要從事非線性電路與系統(tǒng)、計算智能、復雜系統(tǒng)控制與優(yōu)化方向的研究。 E-mail:hutao5@126.com。

TH-3;TP18

A

10.16086/j.cnki.issn1000-0380.201703010

修改稿收到日期：2016-06-24