朱雅敏，薛鵬翔

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

?

一種基于擬蒙特卡羅法的骨干粒子群改進算法

朱雅敏，薛鵬翔

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

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

關鍵詞：骨干粒子群；擬蒙特卡羅法；隨機初始化

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

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

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

針對粒子位置的初始化策略，文獻[2]采用的是偽隨機數的方式，為了提升BBPSO的表現(xiàn)，后來的BBPSO算法出現(xiàn)了許多新變種，如文獻[3]采用了高斯分布和柯西分布來完成迭代時的位置更新，文獻[4]增加了擾動的方式以實現(xiàn)迭代時粒子位置變化的多樣性，但后續(xù)所有這些變種均沿用文獻[2]的偽隨機數初始化方式.本文提出了一種新型的粒子初始化策略——擬蒙特卡羅法.針對上述幾種初始化策略進行的仿真測試結果表明，采用擬蒙特卡羅法進行初始化會獲得更好的效果.

1標準粒子群算法

，

其中：ω為慣性因子，一般取值為0.4～0.9；c1，c2為學習因子，一般取固定的值2；r1，r2為0到1之間的隨機數.

2骨干粒子群算法流程

Clerc和Kennedy在分析微粒運動軌跡后，證明了標準PSO算法中每個微粒i向它的個體歷史極值和全局極值的加權平均值Gi收斂[5]，即

(1)

式中：c1， j，c2， j為[0，1]區(qū)間內的隨機數，當迭代次數趨于無窮時，所有微粒將收斂到同一點.

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

BBPSO算法流程.P0：針對具體問題，設定誤差預設值或迭代最大次數；P1：在搜索空間內，初始化每個粒子的位置(如是標準BBPSO算法，此處采用偽隨機數法)；P2：根據式(1)進行迭代；P3：采用迭代后的粒子位置，計算函數適應度；P4：根據計算所得函數適應度，計算誤差；P5：如誤差小于預設值或迭代達到最大次數，則輸出結果退出，否則轉回P2.

在標準BBPSO算法中，由于后續(xù)算法固定，無其他任何參數可供調整，故算法的收斂性與精度等指標唯一取決于粒子初始化位置，故本文以上述算法流程中的步驟P1作為研究對象，重點考察這個步驟中粒子位置初始化策略的變化對整個算法精度的影響.

3初始化策略

3.1偽隨機數法

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

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

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

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

3.2擬蒙特卡羅法

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

Hammersley列的具體定義：對任意非負整數k，可以展開為以某一素數p為基的多項式

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

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

對任意的非負整數k，可以以素數p為基定義函數

設搜索空間維數為d，則針對素數序列p1，p2，…，pd-1可定義對應的函數序列φp1，φp2，…，φpd-1.與此對應的Hammersley列定義為

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

4數值仿真及分析

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

4.1Rosenbrock函數

表1　Rosenbrock函數極值測試結果

4.2Rastrigin函數

表2　Rastrigin函數極值測試結果

4.3Schewelfel函數

表3　 Schewelfel函數極值測試結果

4.4Sphere函數

表4　Sphere函數極值測試結果

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

5結論

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

參考文獻：

[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.

【責任編輯：郭偉】

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

中圖分類號：TP311.53

文獻標志碼：A

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

基金項目：陜西省教育廳科學研究計劃專項項目(14JK1347).

收稿日期：2015-05-18

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

DOI：10.11713/j.issn.1009-4822.2016.02.027