一種基于Logistic混沌映射的骨干粒子群改進(jìn)算法

朱雅敏， 薛鵬祥

(西安工業(yè)大學(xué) 理學(xué)院，西安 710021)

?

一種基于Logistic混沌映射的骨干粒子群改進(jìn)算法

朱雅敏， 薛鵬祥

(西安工業(yè)大學(xué) 理學(xué)院，西安 710021)

摘要：針對(duì)骨干粒子群算法因受初始化位置分布不均影響，易陷入局部最優(yōu)的問題，提出一種基于Logistic混沌映射的改進(jìn)算法，改進(jìn)算法通過采用Logistic混沌映射控制來保證粒子初始化位置在搜索空間內(nèi)保持隨機(jī)分布，從而有效提升算法的搜索能力.仿真實(shí)驗(yàn)表明：與經(jīng)典骨干粒子群算法相比，改進(jìn)算法搜索能力有所增強(qiáng)，問題求解精度有明顯提升.

關(guān)鍵詞：骨干粒子群;Logistic混沌映射;隨機(jī)初始化

粒子群算法(Particle Swarm Optimization，PSO)是由社會(huì)心理學(xué)家James Kennedy和電子工程學(xué)專家Russell Eberhart于1995年提出的[1]，是繼遺傳算法之后，產(chǎn)生的一種全新的智能優(yōu)化方法，其基本思想是通過種群中粒子間的合作與競(jìng)爭(zhēng)產(chǎn)生的群體智能指導(dǎo)優(yōu)化搜索，其原理和機(jī)制簡(jiǎn)單，既保持了進(jìn)化算法深刻的群體智能背景，又有著良好的優(yōu)化性能.因此，PSO算法已廣泛應(yīng)用到函數(shù)優(yōu)化、多目標(biāo)規(guī)劃、神經(jīng)網(wǎng)絡(luò)訓(xùn)練、模糊系統(tǒng)控制等領(lǐng)域.

由于標(biāo)準(zhǔn)粒子群算法中涉及參數(shù)較多，Kennedy于2003年提出了骨干粒子群算法(Bare Bones PSO，簡(jiǎn)寫為BBPSO)[2]，BBPSO算法僅僅利用關(guān)于微粒全局值和個(gè)體極值的高斯分布完成微粒位置的更新，避免了復(fù)雜的參數(shù)調(diào)節(jié)，是一種十分有潛力的PSO變形算法，但由于取消了速度變量及慣性因子等參數(shù)，故BBPSO的收斂速度與求解精度等指標(biāo)僅取決于粒子初始位置的選取，粒子群位置初始化的策略會(huì)直接決定BBPSO的表現(xiàn).

針對(duì)粒子位置的初始化策略，文獻(xiàn)[2]采用的是偽隨機(jī)數(shù)的方式，為了提升BBPSO的表現(xiàn)，后來BBPSO算法出現(xiàn)了許多新變種，如文獻(xiàn)[3]中采用了高斯分布和柯西分布來完成迭代時(shí)的位置更新，文獻(xiàn)[4]中增加了擾動(dòng)的方式以實(shí)現(xiàn)迭代時(shí)粒子位置變化的多樣性，但后續(xù)所有這些變種均沿用文獻(xiàn)[2]的偽隨機(jī)數(shù)初始化方式.本文參考混沌理論的思想，提出了一種新型的粒子初始化策略：Logistic混沌映射法，仿真測(cè)試結(jié)果表明，采用Logistic混沌映射策略會(huì)獲得更好的效果.

1標(biāo)準(zhǔn)粒子群算法簡(jiǎn)介

假設(shè)搜索空間維數(shù)為D，粒子總數(shù)為N.Pi(t)=(Pi1(t),Pi2(t),…,PiD(t))表示第i個(gè)粒子經(jīng)過t次飛行后的位置，Vi(t)=(Vi1,Vi2,…,ViD)表示第i個(gè)粒子第t次飛行的速度和方向，Pbest=(Pi1,Pi2,…,PiD)表示第i個(gè)粒子第t次飛行及之前整個(gè)尋優(yōu)過程中的最優(yōu)位置，gbest=(gi1,gi2,…,giD)表示第t次飛行及之前整個(gè)粒子群尋優(yōu)過程中的最優(yōu)位置.則標(biāo)準(zhǔn)粒子群算法可以由以下公式進(jìn)行描述：

Pi(t+1)=Pi(t)+Vi(t+1)t=0,1,2,…

2骨干粒子群算法流程

Clerc和Kennedy分析微粒運(yùn)動(dòng)軌跡后，證明了標(biāo)準(zhǔn)PSO算法中，每個(gè)微粒i向它的個(gè)體歷史極值和全局極值的加權(quán)平均值Gi收斂[5]，即

式中c1,j,c2,j為[0，1]區(qū)間內(nèi)的隨機(jī)數(shù)，當(dāng)?shù)螖?shù)趨于無窮時(shí)，所有微粒將收斂到同一點(diǎn).

受上述思想啟發(fā)，Kennedy于2003年提出了骨干粒子群算法(BBPSO)，BBPSO算法利用關(guān)于微粒全局值和個(gè)體極值的高斯分布完成微粒位置的更新：

BBPSO算法的流程如下：

P0.針對(duì)具體問題，設(shè)定誤差預(yù)設(shè)值或迭代最大次數(shù).

P1.在搜索空間內(nèi)，針對(duì)每個(gè)粒子，對(duì)粒子位置進(jìn)行初始化(如是標(biāo)準(zhǔn)BBPSO算法，此處采用偽隨機(jī)數(shù)法).

P2.根據(jù)方程[3]進(jìn)行迭代.

P3.采用迭代后的粒子位置，計(jì)算函數(shù)適應(yīng)度.

P4.根據(jù)計(jì)算所得函數(shù)適應(yīng)度，計(jì)算誤差.

P5.如誤差小于預(yù)設(shè)值或迭代達(dá)到最大次數(shù)，則輸出結(jié)果退出，否則轉(zhuǎn)回P2.

在標(biāo)準(zhǔn)BBPSO算法中，由于后續(xù)算法固定，無其他任何參數(shù)可供調(diào)整，故算法的收斂性與精度等指標(biāo)唯一取決于粒子初始化位置，故本文以粒子初始化策略作為研究對(duì)象，針對(duì)上述算法流程，對(duì)應(yīng)的步驟為P1.

3初始化策略

3.1偽隨機(jī)數(shù)法

目前已有的BBPSO及其變形算法初始化一般采用此法，各種語言的底層庫對(duì)此實(shí)現(xiàn)基本相同，均采用線性同余法(LCG，LinearCongruenceGenerator)，但此法存在嚴(yán)重的缺陷，文獻(xiàn)[6]中證明如采用此法初始化N維空間的點(diǎn)坐標(biāo)，這些點(diǎn)最多位于m1/n超平面上，這是由于產(chǎn)生的X(n)值的前后強(qiáng)關(guān)聯(lián)所致.

設(shè)搜索空間為[-S，S]，空間維度為d，則針對(duì)某一維度，粒子的位置可按照如下方式進(jìn)行初始化：

pi,j=(rand()*2-1)*S

3.2Logistic混沌映射

混沌來自于非線性動(dòng)力系統(tǒng)，描述的是任意隨時(shí)間變化的過程，這個(gè)過程是確定性的、類似隨機(jī)的、非周期的、具有收斂性的，并且對(duì)于初始值有極敏感的依賴性.

Logistic一維混沌映射數(shù)學(xué)形式表述簡(jiǎn)單，但具有極其復(fù)雜的動(dòng)力學(xué)行為，其數(shù)學(xué)表達(dá)公式如下[7]：

xn+1=μ*xn*(1-xn)x∈[0,1]

其中μ∈[0,4]稱為L(zhǎng)ogistic參數(shù).

a)當(dāng)0<μ≤1

此時(shí)該模型的狀態(tài)簡(jiǎn)單，曲線迅速趨于0，且0就是吸引子，迭代方程最終歸于0值不變.

b)當(dāng)1<μ≤3

該模型狀態(tài)比較簡(jiǎn)單，不動(dòng)點(diǎn)0，1-1/μ為僅有的兩個(gè)周期點(diǎn).

c)當(dāng)3<μ≤4

此時(shí)該模型狀態(tài)十分復(fù)雜，系統(tǒng)由倍周期通向混沌.

d)當(dāng)μ>4

此時(shí)該系統(tǒng)狀態(tài)毫無混沌現(xiàn)象，0為唯一的吸引子.

由上可見Logistic系統(tǒng)隨著μ增大的變化情況是：非混沌一混沌一非混沌，經(jīng)研究發(fā)現(xiàn)，Logistic方程僅3.566 9<μ≤4時(shí)，該方程呈現(xiàn)混沌狀態(tài)[8].

在本文中，令μ=3.999.此時(shí)有初始條件X0在Logistic映射作用下產(chǎn)生的序列是混沌狀態(tài)、非周期的、不收斂的，故可采用此序列對(duì)粒子位置進(jìn)行初始化.

本文中采用此方法的初始化方式為：

pi,j=(xi*2-1)*S

4數(shù)值仿真及分析

基于上文所述之算法，采用Python語言及其科學(xué)計(jì)算擴(kuò)展包numpy、scipy編寫了仿真測(cè)試程序，針對(duì)下述典型的函數(shù)進(jìn)行了實(shí)際測(cè)試.

實(shí)際測(cè)試中，采用偽隨機(jī)數(shù)策略初始化的算法標(biāo)記為BBPSO1，采用Logistic混沌映射策略初始化的算法標(biāo)注為BBPSO2.

參考文獻(xiàn)[9]、[10]、[11]，本文最終選定下面四個(gè)典型的函數(shù)作為仿真測(cè)試函數(shù)，具體的仿真測(cè)試結(jié)果如下：

4.1Rosenbrock函數(shù)

Rosenbrock函數(shù)，非凸，病態(tài)函數(shù)，在xi=1時(shí)達(dá)到極小值0.

參數(shù)設(shè)置：粒子總數(shù)50,搜索空間[-30,30]，迭代次數(shù)100次，經(jīng)過50次運(yùn)行后，測(cè)試數(shù)據(jù)如表1：

表1　Rosenbrock函數(shù)極值測(cè)試結(jié)果

4.2Rastrigin函數(shù)

Rastrigin函數(shù)，多峰函數(shù)，在xi=0(i=1，…，n)時(shí)達(dá)到全局極小點(diǎn)，在S={xi∈(-5.12,5.12),i=1,2，…，n}范圍內(nèi)大概存在約10n個(gè)局部極小點(diǎn).

參數(shù)設(shè)置：粒子總數(shù)50,搜索空間[-5.12,5.12]，自變量維度30，常數(shù)A取10，迭代次數(shù)100次，經(jīng)過50次運(yùn)行后，測(cè)試數(shù)據(jù)如表2：

表2　Rastrigin函數(shù)極值測(cè)試結(jié)果

4.3Schewelfel函數(shù)

Schewelfel函數(shù)，單峰，在xi=0時(shí)達(dá)到極小值0.

參數(shù)設(shè)置：粒子總數(shù)50,搜索空間[-30,30]，自變量維度30，迭代次數(shù)100次，經(jīng)過50次運(yùn)行后，測(cè)試數(shù)據(jù)如表3：

表3　Schewelfel函數(shù)極值測(cè)試結(jié)果

4.4Sphere函數(shù)

Sphere函數(shù)，單峰，在xi=0時(shí)達(dá)到極小值0.

參數(shù)設(shè)置：粒子總數(shù)50,搜索空間[-100,100]，自變量維度30，經(jīng)過50次運(yùn)行后，測(cè)試數(shù)據(jù)如表4：

表4　Sphere函數(shù)極值測(cè)試結(jié)果

5數(shù)值仿真及分析

根據(jù)上述仿真測(cè)試結(jié)果可知，與BBPSO1相比，BBPSO2的收斂速度、搜索精度、跳出局部最優(yōu)能力都有不同程度的加強(qiáng).以上仿真結(jié)果證明，不管是多峰函數(shù)還是單峰函數(shù)，采用Logistic混沌映射的骨干粒子群改進(jìn)算法均具備可行性和有效性.

[1]KENNDY J，EBERHART R C.Particle swarm optimization[C].Proc IEEE Int Conf on Neural Networks，Perth，WA，Australia，1995：1942-1948.

[2]KENNEDY J.Bare bones particle swarms[C].Proceedings of the IEEE Swarm Intelligence Symposium，2003：80-87.

[3]KROHLING R A.Bare bones particle swarm optimization with gaussian or cauchy jumps，Evolutionary Computation[C].CEC′09.IEEE Congress，2009：3285-3291.

[4]MOHAMMAD M R. Bare bones particle swarms withjumps[J].Lect Notes Comput Sci.，2005， 7461:49-60.

[5]VAN DEN BERGH F，ENGELBRECHT A.A study of particle swarm optimization particle trajectories[J].Information Sciences，2005，176(8)：937-971.

[6]MARSAGLIA G,TSANG W W.The Monty Python method for generating random variables[J].ACM Transactions on Mathematical Software,1998,24 (3):341-350.

[7]GRASSBERGER P,PROCACCIA I.Measuring the strangeness of strange attractors[J].Physica D，1983，9 (1-2):189-208.

[8]SPROTT,CLINTON J.Chaos and time-series analysis[M].Oxford：Oxford University Press，2003.

[9]WILLIAM M S,DEREK T G,DIANA F S.Biases in particle swarm optimization[J].International Journal of Swarm Intelligence Research,2010，1(2):34-57.

[10]JONES D.Good practice in (pseudo) random number generation for bioinformatics applications[C].Technical report,UCL Bioinformatics Group,2010.

[11]MARINAKIS Y,MARINAKI M.A hybrid genetic-Particle Swarm Optimization Algorithm for the vehicle [J].Expert System with Applications,2010,37:1446-1455.

[責(zé)任編輯王新奇]

An Improved Algorithm for Backbone Particle Swarm OptimizationBased on Logistic Chaotic Mapping

ZHU Ya-min, XUE Peng-xiang

( School of Science, Xi’an Technological University, Xi’an 710021, China )

Abstract：In this paper, aiming at the problem that the backbone particle swarm algorithm is easy to fall into local optimum because of uneven distribution of the initial position, an improved algorithm based on logistic chaotic mapping is proposed. By using the logistic chaotic mapping control to ensure that the initial position of particles in the search space to maintain a random distribution, therefore, the search ability of the algorithm is effectively improved. The simulation experiments show that the search ability of the improved algorithm has been significantly enhanced and its problem solving accuracy is significantly improved compared with that of the classical PSO algorithm.

Key words：backbone particle swarm; Logistic chaotic mapping; random initialization

中圖分類號(hào)：TP183

文獻(xiàn)標(biāo)志碼：A

作者簡(jiǎn)介：朱雅敏(1977—)，女，河北保定人，西安工業(yè)大學(xué)理學(xué)院講師，碩士，主要從事數(shù)值代數(shù)及智能算法研究.

基金項(xiàng)目：陜西省教育廳項(xiàng)目(14JK1347)

收稿日期：2015-11-02

文章編號(hào)：1008-5564(2016)01-0001-04