朱雅敏，薛鵬翔

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

?

一種基于擬蒙特卡羅法的骨干粒子群改進(jìn)算法

朱雅敏，薛鵬翔

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

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

關(guān)鍵詞：骨干粒子群；擬蒙特卡羅法；隨機(jī)初始化

【引用格式】朱雅敏，薛鵬翔.一種基于擬蒙特卡羅法的骨干粒子群改進(jìn)算法[J].北華大學(xué)學(xué)報(bào)(自然科學(xué)版)，2016，17(2)：266-269.

粒子群算法(Particle Swarm Optimization，PSO)是繼蟻群算法之后，群體智能算法中一個(gè)重要的分支，1995年由James Kennedy和Russell Eberhart共同提出[1]，其基本思想擺脫了蟻群算法中的信息素等概念，而是僅僅通過種群中粒子間的合作與競(jìng)爭(zhēng)來進(jìn)行迭代優(yōu)化.與蟻群算法相比，在機(jī)制上有明顯簡(jiǎn)化，避免了蟻群算法中需要調(diào)整的參數(shù)過多的弊病.目前，PSO 算法已廣泛應(yīng)用于多種與優(yōu)化相關(guān)的領(lǐng)域，具備良好的發(fā)展前景.

雖然標(biāo)準(zhǔn)粒子群算法較蟻群算法參數(shù)有所簡(jiǎn)化，但仍然涉及多個(gè)參數(shù)，為此，Kennedy于2003年提出了骨干粒子群算法(Bare Bones PSO，BBPSO)[2].BBPSO算法僅僅利用關(guān)于微粒全局值和個(gè)體極值的高斯分布完成微粒位置的更新，避免了復(fù)雜的參數(shù)調(diào)節(jié)，是一種十分有潛力的PSO變形算法.但由于取消了速度變量及慣性因子等參數(shù)，BBPSO的收斂速度與求解精度等指標(biāo)僅取決于粒子初始位置的選取，粒子群位置初始化的策略直接決定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ù)初始化方式.本文提出了一種新型的粒子初始化策略——擬蒙特卡羅法.針對(duì)上述幾種初始化策略進(jìn)行的仿真測(cè)試結(jié)果表明，采用擬蒙特卡羅法進(jìn)行初始化會(huì)獲得更好的效果.

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

，

其中：ω為慣性因子，一般取值為0.4～0.9；c1，c2為學(xué)習(xí)因子，一般取固定的值2；r1，r2為0到1之間的隨機(jī)數(shù).

2骨干粒子群算法流程

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

(1)

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

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

BBPSO算法流程.P0：針對(duì)具體問題，設(shè)定誤差預(yù)設(shè)值或迭代最大次數(shù)；P1：在搜索空間內(nèi)，初始化每個(gè)粒子的位置(如是標(biāo)準(zhǔn)BBPSO算法，此處采用偽隨機(jī)數(shù)法)；P2：根據(jù)式(1)進(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)唯一取決于粒子初始化位置，故本文以上述算法流程中的步驟P1作為研究對(duì)象，重點(diǎn)考察這個(gè)步驟中粒子位置初始化策略的變化對(duì)整個(gè)算法精度的影響.

3初始化策略

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

目前已有的BBPSO及其變形算法初始化一般采用此法，各種語言的底層庫對(duì)此實(shí)現(xiàn)基本相同，均采用線性同余法(LCG，LinearCongruenceGenerator)：

xn+1=(axn-1+c)%m，

式中：a，c，m為常數(shù).但此法存在嚴(yán)重缺陷，文獻(xiàn)[6]中證明如采用此法初始化N維空間的點(diǎn)坐標(biāo)，這些點(diǎn)最多位于m/n超平面上，這是由產(chǎn)生的X(n)值的前后強(qiáng)關(guān)聯(lián)所致.

設(shè)搜索空間為[-S，S]，空間維度為d，則針對(duì)某一維度，粒子的位置可按照pi， j=(rand()×2-1)×S進(jìn)行初始化.

3.2擬蒙特卡羅法

擬蒙特卡羅法的基本思想是采用確定性的超均勻分布序列代替MonteCarlo方法中的隨機(jī)數(shù)序列，常采用的超均勻分布序列為Hammersley列、Halton列等低差異列.考慮到Hammersley列的超均勻分布特性，本文中采用Hammersley序列對(duì)粒子位置進(jìn)行初始化.

Hammersley列的具體定義：對(duì)任意非負(fù)整數(shù)k，可以展開為以某一素?cái)?shù)p為基的多項(xiàng)式

k=a0+a1p+a2p2+…+arpr，

式中：ai為[0，p-1]區(qū)間的整數(shù).

對(duì)任意的非負(fù)整數(shù)k，可以以素?cái)?shù)p為基定義函數(shù)

設(shè)搜索空間維數(shù)為d，則針對(duì)素?cái)?shù)序列p1，p2，…，pd-1可定義對(duì)應(yīng)的函數(shù)序列φp1，φp2，…，φpd-1.與此對(duì)應(yīng)的Hammersley列定義為

在實(shí)際的粒子群初始化中，針對(duì)粒子的某一維度，具體的初始化方式為pi， j=(H[i]×2-1)×S.

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

為驗(yàn)證本算法的有效性，參考文獻(xiàn)[9-11]中所使用的仿真測(cè)試手段，選取下面的幾個(gè)函數(shù)進(jìn)行了程序仿真測(cè)試.測(cè)試中，采用偽隨機(jī)數(shù)策略初始化的算法標(biāo)記為BBPSO1，采用擬蒙特卡羅法策略初始化的算法標(biāo)注為BBPSO2.參數(shù)設(shè)置約定：N為粒子總數(shù)；S為搜索空間；I為迭代次數(shù)；R為程序運(yùn)行次數(shù)；V為自變量維度.

4.1Rosenbrock函數(shù)

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

4.2Rastrigin函數(shù)

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

4.3Schewelfel函數(shù)

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

4.4Sphere函數(shù)

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

根據(jù)上述仿真測(cè)試結(jié)果可知：與BBPSO1相比，BBPSO2的收斂速度、搜索精度、跳出局部最優(yōu)能力都有不同程度的加強(qiáng).4個(gè)案例可以證明，無論是多峰函數(shù)還是單峰函數(shù)，采用擬蒙特卡羅法的BBPSO優(yōu)化算法都具有良好的可行性和有效性.

5結(jié)論

與經(jīng)典骨干粒子群算法相比，比較收斂速度和精度兩個(gè)指標(biāo)，改進(jìn)算法具有更加良好的表現(xiàn)，但目前關(guān)于初始位置隨機(jī)分布程度與算法執(zhí)行情況之間的具體關(guān)聯(lián)尚缺乏嚴(yán)格的數(shù)學(xué)分析，可作為后續(xù)的一個(gè)研究方向.

參考文獻(xiàn)：

[1] Kenndy J，Eberhart R C.Particle swarm optimization[C]//Proc IEEE Int Conf on Neural Networks，Perth：Australian，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[C]//Evolutionary Computation，IEEE Congress，2009：3285-3291.

[4] Mohammad M R.Bare bones particle swarms with jumps[J].Lect Notes Comput Sci，2010，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] P Grassberger，I Procaccia.Measuring the strangeness of strange attractors[J].Physica D，1983，9(1-2)：189-208.

[8] Julien Clinton.Sprott，chaos and time-series analysis[M].Oxford：Oxford University Press，2003.

[9] William M Spears，Derek T Green，Diana F Spears.Biases in particle swarm optimization[J].International Journal of Swarm Intelligence Research，2010，1(2)：34-57.

[10] David Jones.Good practice in(pseudo)random number generation for bioinformatics applications[C]//Technical Report，UCL Bioinformatics Group，2010：15-21.

[11] Yannis Marinakis，Magdalene Marinaki.A hybrid genetic-particle swarm optimization algorithm for the vehicle[J].Expert System with Applications，2010，37：1446-1455.

【責(zé)任編輯：郭偉】

An Improved BBPSO Algorithm Using Quasi-Monte Carlo

Zhu Yamin，Xue Pengxiang

(SchoolofScience，Xi’anTechnologicalUniversity，Xi’an710021，China)

Abstract：Aimed to the classics Bare Bones PSO(BBPSO)was easily influenced by initialized position distribution，one initial strategy based on Quasi-Monte Carlo was proposed in this paper.New strategy enhanced the performance of BBPSO by assured randomness of the particles initialized distribution.Four numerical experiments showed the algorithm’s convergence speed and search accuracy have been improved by using the new strategy.

Key words：bare bones swarms；Quasi-Monte Carlo；random initialization

中圖分類號(hào)：TP311.53

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

作者簡(jiǎn)介：朱雅敏(1977-)，女，碩士，講師，主要從事數(shù)值代數(shù)及智能算法研究，E-mail：zhu_ya_min@yeah.net.

基金項(xiàng)目：陜西省教育廳科學(xué)研究計(jì)劃專項(xiàng)項(xiàng)目(14JK1347).

收稿日期：2015-05-18

文章編號(hào)：1009-4822(2016)02-0266-04

DOI：10.11713/j.issn.1009-4822.2016.02.027