基于混沌和多群體的粒子群優(yōu)化算法

宮玉琳，文大化

（1.長春理工大學　電子信息工程學院，長春　130022；2.中國科學院長春光學精密機械與物理研究所，長春　130033）

基于混沌和多群體的粒子群優(yōu)化算法

宮玉琳1，文大化2

（1.長春理工大學電子信息工程學院，長春130022；2.中國科學院長春光學精密機械與物理研究所，長春130033）

由于基本粒子群優(yōu)化算法存在初始化隨機性和遍歷性不強，全局搜索容易陷入局部最優(yōu)的問題，提出了基于混沌和多群體的粒子群優(yōu)化算法，利用混沌特性初始化粒子，增強其隨機性和遍歷性，并根據適應度值將粒子群劃分為多個群體，對不同群體中粒子的速度和位置采取不同的計算方法，進一步提高算法的收斂速度和精度。

混沌；多群體；粒子群優(yōu)化

粒子群優(yōu)化（Particle Swarm Optimization，PSO）算法［1］，通過追隨當前搜索到的最優(yōu)值來尋找全局最優(yōu)，在求解優(yōu)化問題等方面已經得到了越來越廣泛的應用。

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

PSO算法模擬鳥群尋找食物的過程，在尋找食物的過程中，鳥不停地改變自己在空間飛行的位置和速度，每只鳥都可以用一個粒子來表示，粒子的參數也就是需要求解問題的可能解。假設m個粒子組成的粒子群在D維空間中進行搜索，其中，第i個粒子在D維空間中的位置表示為xi=（xi1，xi2，…，xiD），第i個粒子所經歷過的最優(yōu)位置表示為Pi=（pi1，p12，…，piD），每個粒子的飛行速度表示為Vi=（vi1，v12，…，viD），所有粒子經歷過的最優(yōu)位置表示為Pg=（pg1，pg2，…，pgD），例如：pg1表示第一個粒子經歷過的最優(yōu)位置。粒子群中單個粒子的迭代過程如圖1所示。

圖1　粒子迭代過程

在搜索的過程中，每個粒子各自的速度和位置分別通過公式（1）和（2）進行更新：式中，i表示第i個粒子；d表示粒子的第d維；k表示迭代次數；w為慣性因子；c1和c2為學習因子；r1和r2為［ ］0，1區(qū)間的隨機數。

2　混沌初始優(yōu)化

為了增強粒子初始的遍歷性和隨機性，通過公式（3）的Logistic映射［2，3］對粒子分布進行優(yōu)化：

式中，μ為控制參量，決定了混沌系統(tǒng)的混沌狀態(tài)程度。

混沌初始化的過程包括如下步驟：

（1）隨機生成一個向量z0=［z01，z02，…，z0n］，n為粒子的維數；

（3）將混沌向量映射到定義域X上，第i個粒子可以表示為：

式中，xmax和xmin分別為粒子取值的上下限。

3　多群體優(yōu)化

3.1早熟收斂程度評價

由PSO算法的原理可知，粒子在搜索全局最優(yōu)解的過程中，趨同性會越來越強，這將使得粒子的多樣性受到極大限制。為了減弱趨同性又會使粒子的多樣性受到影響，這將減小算法的收斂速度。因此，選擇合適的早熟收斂評價指標十分重要，為了合理的評價粒子群的早熟收斂程度，本文采用公式（5）和式（6）對其進行評價：

式中，N表示粒子總數；fi表示第i個粒子的適應度值；favg表示N個粒子的平均適應度值；fg表示粒子的最優(yōu)適應度值；表示所有優(yōu)于 favg的適應度值的平均值；Δ即為早熟評價指標，Δ值越大表明粒子群早熟程度越低。

3.2多群體劃分

本文根據早熟收斂評價指標，將整個粒子群劃分為最優(yōu)群體、一般群體和最差群體三個子群體［4，5］，如圖2所示。

圖2　多群體劃分

劃分的群體采用非均勻劃分的方式，最優(yōu)群體和最差群體各占整個群體的25%，一般群體占整個群體的50%。由于最優(yōu)群體中粒子的適應度值較高，所以該群體中的粒子更接近全局最優(yōu)解。但是，這些粒子受群體最優(yōu)影響嚴重，弱化了粒子個體最優(yōu)的作用。粒子通過式（7）調整速度，同時根據式（8）調整粒子的慣性因子w：

式中，wmin為慣性因子w的最小值。由式（8）可以看出，適應度值越好的粒子對應的慣性因子越小。通過采用種策略，使得算法接近收斂時具有更強的局部搜索能力。

（1）自然環(huán)境狀況。洞庭湖東、南、西三面為山脈高地，北部為平原水網地區(qū)。湖區(qū)四季分明，降水充沛，生物資源豐富，有水生高等植物311種，浮游動物90種，底棲動物67種，魚類113種，鳥類216種，水生哺乳類動物22種，其中有中華鱘、白鱘等國家一級、二級保護動物48種，國家一、二級保護植物30多種，是國家重點保護野生動物江豚和麋鹿的棲憩地。

一般群體中的粒子在全局尋優(yōu)能力和局部尋優(yōu)能力方面都有較好的能力。因此，速度更新可直接采用式（1）進行，慣性因子w則通過式（9）進行調整：

慣性因子隨著搜索的進行逐漸減小，使得搜索開始時具有較高的搜索效率，并且在搜索后期具有提高搜索精度。

最差群體中的粒子搜索能力較差，需要借助一般子群體中的位置信息，因此采用式（10）對速度進行更新，慣性因子w通過式（11）進行調整：

當粒子松散地分布于搜索空間時，根據式（6）可以算得此時的Δ值較大，這時將Δ代入式（11）可得較小的w，使得算法具有較強的局部搜索能力，能夠加強粒子的收斂；當粒子集中分布于搜索空間時，則根據式（6）算得的Δ值較小，此時由式（11）可得較大的w，使得算法具有較強的全局搜索能力，能夠使粒子跳出局部最優(yōu)。

對于式（11），可以看到參數k1和k2的選擇對w的取值有著很重要的影響。其中，k1主要用來決定w的最大值，k1取值越大，則w的最大值越大。根據上文的分析可知，w的取值應大于1。因此，k1需取大于1的常數，這樣才能使式（11）計算得到的w大于1。在本文算法中，取k1=1.5，通過可以計算可以得到w的取值范圍：0.5＜w＜1.1。k2主要用來決定慣性因子w的調節(jié)，k2的取值越大，在早期停滯時，w的調節(jié)能力越強，使得算法具有較快的收斂速度，但是會使算法的收斂精度受到影響；k2的取值越小，慣性因子w的調節(jié)能力越弱，當粒子集中地分布于搜索空間時，算法不能有效地跳出局部最優(yōu)。

4　算法測試與仿真分析

為了對本文算法的性能進行分析，選用了三個典型的測試函數：Rosenbrock函數、Griewank函數以及Rastrigin函數，對算法性能進行了仿真分析。

（1）Rosenbrock函數的局部最優(yōu)值和全局最優(yōu)值十分接近，全局最優(yōu)值的求解比較復雜。Rosenbrock函數的表達式如公式（12）所示，維度為3的Rosenbrock函數如圖3所示。

（3）Rastrigin函數也是一個多峰值函數，存在很多局部最優(yōu)解，對于求解全局最優(yōu)解也是十分復雜的。Rastrigin函數的表達式如公式（14）所示，維度為3的Rastrigin函數如圖5所示。

典型測試函數的參數如表1所示。

表1　典型測試函數的參數

為了對比算法的效果，本文將CMPSO算法分別與PSO算法與遺傳算法（GA）進行對比分析。測試過程中，每種算法迭代500次，各算法的參數如表2所示。

表2　各算法參數

當測試函數的維度n=10時，得到五種測試函數的測試曲線如圖6至圖8所示。采用三種算法對測試函數得到的平均最優(yōu)值和最優(yōu)值如表3所示。由圖6至圖8和表3可見，典型的測試函數，粒子群優(yōu)化算法的速度明顯快于遺傳算法的優(yōu)化速度，并且收斂精度高。其中，對于Rastrigin函數，盡管開始時基本粒子群優(yōu)化算法的收斂速度最快，但隨著迭代次數的增加，收斂速度逐漸變慢，最終的收斂精度也明顯不及改進的粒子群優(yōu)化算法。

圖3　維度n=3時的Rosenbrock函數

圖4　維度n=3時的Griewank函數

圖5　維度n=3的Rastrigin函數

圖6　Rosenbrock函數平均適應值曲線

圖7　Griewank函數平均適應值曲線

圖8　Rastrigin函數平均適應值曲線

表3　三種算法得到的平均最優(yōu)值和最優(yōu)值

5　結論

本文采用Logistic映射對粒子進行混沌初始化，使粒子在初始時具有較好的遍歷性，增強了粒子的全局搜索能力。同時，根據早熟收斂評價指標將整個粒子群劃分為多個群體，針對不同群體采取與之適應的計算方法，解決了基本粒子群體算法易陷入局部最優(yōu)、早熟收斂的問題，盡管運算量有所增加，但仿真結果表明，本文算法具有收斂速度較快、收斂精度高的特點，明顯優(yōu)于遺傳算法和基本粒子群優(yōu)化算法。

［1］ Kennedy J，Eberhart R.Swarm Intelligence［M］.San Francisco：Morgan Kaufman Publishers，2001.

［2］Wang T Y，Huang C Y.Applying optimized BPN to a chaotic time series problem［J］.Expert Sys-tems with Applications，2007，32：193-200.

［3］Poli R，Langdon W B，Clerc M，et al.Continuous optimization theory made easy Finite-element models of evolutionary strategies，genetic algorithms and particle swarm optimizers［M］.LNCS，Proceedings of thefoundationsofgeneticalgorithmsworkshop，Springer，Berlin，2007.

［4］ Huynh D C，Dunnigan M W.Parameter estimation ofaninductionmachineusingadvancedparticle swarm optimization algorithms［J］.IET Electric Power Applications，2010，4（9）：748-760.

［5］Blackwell T，Branke J.Multiswarms，exclusion，and anti-convergence in dynamic environments［J］.IEEE Transactions on Evolutionary Computation，2010，10 （4）：459-472.

［6］Huang Fang，Fan Xiaoping.Parallel particle swarm optimization algorithm based on island group model ［J］.Control and Decision，2006，21（2）：75-188.

［7］Huang T，Mohan A S.A hybrid boundary conditionforrobustparticleswarmoptimization［J］. IEEE Antennas and Wireless Propagation Letters，2012（4）：112-117.

［8］ Xu S，Rahmat Samii Y.Boundary conditions in particle swarm optimization revisited［J］.IEEE AntennasandWirelessPropagationLetters，2011，55（3）：760-765.

Particle Swarm Optimization Algorithm Based on Chaos and Multi Group

GONG Yulin1，WEN Dahua2
（1.School of Electronic and Information Engineering，Changchun University of Science and Technology，Changchun 130022；2.Changchun Institute of Optics，Fine Mechanics and Physics，Chinese Academy of Science，Changchun 130033）

Because the basic particle swarm optimization algorithm has the problem that the initialization of the algorithm is easy to fall into local optimum，the global search is easy to fall into local optimization.The particle swarm optimization algorithm based on chaos and multi population is proposed.The algorithm can be used to improve the speed and accuracy of different populations.

chaos；multi group；particle swarm optimization

TP301

A

1672-9870（2015）05-0088-04

2015-09-16

宮玉琳（1983），男，博士，講師，E-mail：garrygong1983@126.com