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

宮玉琳，文大化

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

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

宮玉琳1，文大化2

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

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

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

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

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

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

圖1　粒子迭代過程

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

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

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

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

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

（1）隨機(jī)生成一個(gè)向量z0=［z01，z02，…，z0n］，n為粒子的維數(shù)；

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

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

3　多群體優(yōu)化

3.1早熟收斂程度評(píng)價(jià)

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

式中，N表示粒子總數(shù)；fi表示第i個(gè)粒子的適應(yīng)度值；favg表示N個(gè)粒子的平均適應(yīng)度值；fg表示粒子的最優(yōu)適應(yīng)度值；表示所有優(yōu)于 favg的適應(yīng)度值的平均值；Δ即為早熟評(píng)價(jià)指標(biāo)，Δ值越大表明粒子群早熟程度越低。

3.2多群體劃分

本文根據(jù)早熟收斂評(píng)價(jià)指標(biāo)，將整個(gè)粒子群劃分為最優(yōu)群體、一般群體和最差群體三個(gè)子群體［4，5］，如圖2所示。

圖2　多群體劃分

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

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

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

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

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

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

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

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

4　算法測試與仿真分析

為了對(duì)本文算法的性能進(jìn)行分析，選用了三個(gè)典型的測試函數(shù)：Rosenbrock函數(shù)、Griewank函數(shù)以及Rastrigin函數(shù)，對(duì)算法性能進(jìn)行了仿真分析。

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

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

典型測試函數(shù)的參數(shù)如表1所示。

表1　典型測試函數(shù)的參數(shù)

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

表2　各算法參數(shù)

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

圖3　維度n=3時(shí)的Rosenbrock函數(shù)

圖4　維度n=3時(shí)的Griewank函數(shù)

圖5　維度n=3的Rastrigin函數(shù)

圖6　Rosenbrock函數(shù)平均適應(yīng)值曲線

圖7　Griewank函數(shù)平均適應(yīng)值曲線

圖8　Rastrigin函數(shù)平均適應(yīng)值曲線

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

5　結(jié)論

本文采用Logistic映射對(duì)粒子進(jìn)行混沌初始化，使粒子在初始時(shí)具有較好的遍歷性，增強(qiáng)了粒子的全局搜索能力。同時(shí)，根據(jù)早熟收斂評(píng)價(jià)指標(biāo)將整個(gè)粒子群劃分為多個(gè)群體，針對(duì)不同群體采取與之適應(yīng)的計(jì)算方法，解決了基本粒子群體算法易陷入局部最優(yōu)、早熟收斂的問題，盡管運(yùn)算量有所增加，但仿真結(jié)果表明，本文算法具有收斂速度較快、收斂精度高的特點(diǎn)，明顯優(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，F(xiàn)an 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，F(xiàn)ine 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