一种基于拟蒙特卡罗法的骨干粒子群改进算法

朱雅敏，薛鹏翔

(西安工业大学理学院，陕西 西安　710021)



一种基于拟蒙特卡罗法的骨干粒子群改进算法

朱雅敏，薛鹏翔

(西安工业大学理学院，陕西 西安710021)

摘要：针对骨干粒子群算法因受粒子初始化位置分布不均影响易陷入局部最优的问题，提出一种基于拟蒙特卡罗法的初始化策略，用以确保粒子初始位置在搜索空间内保持随机分布，从而有效提升骨干粒子群算法的搜索能力.仿真实验表明：与经典骨干粒子群算法相比，采用拟蒙特卡罗法进行初始化的改进算法搜索能力有所增强，问题求解精度有明显提升.

关键词：骨干粒子群；拟蒙特卡罗法；随机初始化

【引用格式】朱雅敏，薛鹏翔.一种基于拟蒙特卡罗法的骨干粒子群改进算法[J].北华大学学报(自然科学版)，2016，17(2)：266-269.

粒子群算法(Particle Swarm Optimization，PSO)是继蚁群算法之后，群体智能算法中一个重要的分支，1995年由James Kennedy和Russell Eberhart共同提出[1]，其基本思想摆脱了蚁群算法中的信息素等概念，而是仅仅通过种群中粒子间的合作与竞争来进行迭代优化.与蚁群算法相比，在机制上有明显简化，避免了蚁群算法中需要调整的参数过多的弊病.目前，PSO 算法已广泛应用于多种与优化相关的领域，具备良好的发展前景.

虽然标准粒子群算法较蚁群算法参数有所简化，但仍然涉及多个参数，为此，Kennedy于2003年提出了骨干粒子群算法(Bare Bones PSO，BBPSO)[2].BBPSO算法仅仅利用关于微粒全局值和个体极值的高斯分布完成微粒位置的更新，避免了复杂的参数调节，是一种十分有潜力的PSO变形算法.但由于取消了速度变量及惯性因子等参数，BBPSO的收敛速度与求解精度等指标仅取决于粒子初始位置的选取，粒子群位置初始化的策略直接决定BBPSO的表现.

针对粒子位置的初始化策略，文献[2]采用的是伪随机数的方式，为了提升BBPSO的表现，后来的BBPSO算法出现了许多新变种，如文献[3]采用了高斯分布和柯西分布来完成迭代时的位置更新，文献[4]增加了扰动的方式以实现迭代时粒子位置变化的多样性，但后续所有这些变种均沿用文献[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]区间内的随机数，当迭代次数趋于无穷时，所有微粒将收敛到同一点.

受上述思想启发，Kennedy于2003年提出了骨干粒子群算法，该算法利用关于微粒全局值和个体极值的高斯分布完成微粒位置的更新：

BBPSO算法流程.P0：针对具体问题，设定误差预设值或迭代最大次数；P1：在搜索空间内，初始化每个粒子的位置(如是标准BBPSO算法，此处采用伪随机数法)；P2：根据式(1)进行迭代；P3：采用迭代后的粒子位置，计算函数适应度；P4：根据计算所得函数适应度，计算误差；P5：如误差小于预设值或迭代达到最大次数，则输出结果退出，否则转回P2.

在标准BBPSO算法中，由于后续算法固定，无其他任何参数可供调整，故算法的收敛性与精度等指标唯一取决于粒子初始化位置，故本文以上述算法流程中的步骤P1作为研究对象，重点考察这个步骤中粒子位置初始化策略的变化对整个算法精度的影响.

3初始化策略

3.1伪随机数法

目前已有的BBPSO及其变形算法初始化一般采用此法，各种语言的底层库对此实现基本相同，均采用线性同余法(LCG，LinearCongruenceGenerator)：

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

式中：a，c，m为常数.但此法存在严重缺陷，文献[6]中证明如采用此法初始化N维空间的点坐标，这些点最多位于m/n超平面上，这是由产生的X(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]区间的整数.

对任意的非负整数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的收敛速度、搜索精度、跳出局部最优能力都有不同程度的加强.4个案例可以证明，无论是多峰函数还是单峰函数，采用拟蒙特卡罗法的BBPSO优化算法都具有良好的可行性和有效性.

5结论

与经典骨干粒子群算法相比，比较收敛速度和精度两个指标，改进算法具有更加良好的表现，但目前关于初始位置随机分布程度与算法执行情况之间的具体关联尚缺乏严格的数学分析，可作为后续的一个研究方向.

参考文献：

[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