虎濤濤,單要楠

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

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

虎濤濤1,單要楠2

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

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

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

0 引言

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

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

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

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

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

(1)

(2)

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

(3)

(4)

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

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

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

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

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

(5)

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

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

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

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

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

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

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

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

(6)

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

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

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

3 仿真測(cè)試

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

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

表1 三種函數(shù)的尋優(yōu)測(cè)試計(jì)算結(jié)果

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

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

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

測(cè)試函數(shù)f(1)很難極小化函數(shù)Rosenbrock，很容易找到極小點(diǎn)，但是要跳出這個(gè)極小點(diǎn)收斂到全局最小點(diǎn)卻十分困難。而利用混沌運(yùn)動(dòng)的特性，可以克服粒子群陷入局部最優(yōu)的情況，圖1(a)中測(cè)試函數(shù)f(1)的尋優(yōu)軌跡曲線表明,CPSO算法在算法迭代450次就已收斂，而變參數(shù)CPSO在252次收斂，且收斂精度最高。圖1(b)的尋優(yōu)軌跡曲線表明變參數(shù)CPSO比CPSO算法收斂快。圖1(c)中測(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 結(jié)束語

混沌變參數(shù)粒子群優(yōu)化算法是在混沌粒子群算法的基礎(chǔ)上，通過動(dòng)態(tài)改變Logistic方程的混沌控制參數(shù)，使算法在迭代過程中根據(jù)種群收斂狀態(tài)及時(shí)增強(qiáng)或減弱混沌運(yùn)動(dòng)，以降低對(duì)已收斂種群的破壞。根據(jù)仿真測(cè)試，混沌變參數(shù)粒子群優(yōu)化算法既保留了混沌粒子群優(yōu)化算法的優(yōu)點(diǎn)，又保持了粒子群體的多樣性，可快速跳出局部最優(yōu)點(diǎn)，尋找全局最優(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] 宮玉琳,永磁同步電動(dòng)機(jī)伺服系統(tǒng)自適應(yīng)逆控制策略研究[D]. 長(zhǎng)春：長(zhǎng)春理工大學(xué),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)化算法及其應(yīng)用[J]. 華中科技大學(xué)學(xué)報(bào),2005,33(10):53-55.

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

[12]楊俊杰，周建中，喻菁，等. 基于混沌搜索的粒子群優(yōu)化算法[J]. 計(jì)算機(jī)工程與應(yīng)用,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)、計(jì)算智能、復(fù)雜系統(tǒng)控制與優(yōu)化方向的研究。 E-mail:hutao5@126.com。

TH-3;TP18

A

10.16086/j.cnki.issn1000-0380.201703010

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