基于MapReduce模型的分布式粒子群算法

doi:10.6040/j.issn.1672-3961.1.2016.161

摘要/Abstract

摘要： 通过对传统的单种群粒子群算法的分析,提出一种基于MapReduce模型的分布式粒子群算法,解决粒子群算法在求解大规模优化问题时求解效率和精度明显下降等问题。在粒子群进化过程中,粒子速度和位置的更新采用惯性权重的方法,其权重值线性递减,并且利用多子群进化策略,提高算法的收敛精度。通过MapReduce模型实现算法的并行化,有效提高算法求解效率。选取目前比较流行的几种算法,并在13个500维、1 000维的标准测试函数上仿真试验,结果显示该算法具有良好的优化性能。

关键词: 并行, 粒子群, 大规模优化, MapReduce模型, 分布式

Abstract: A distributed particle swarm optimization algorithm based on MapReduce was proposed through the analysis of the traditional single population particle swarm optimization algorithm, which was used to solve the algorithm problems of decreased efficiency and accuracy in large scale optimization. In the evolutionary process of particle swarm algorithm, the particles velocity and position was updated by using the method of inertia weight, its value was decreased linearly, the accuracy of convergence was improved by adopting the strategies of multi population evolution. The process of the algorithm was parallel through the MapReduce model, which could improve the efficiency of the algorithm effectively. Several popular algorithms were selected and tested on 13 benchmark functions of 500 dimensions and 1 000 dimensions. The results showed that the algorithm has good optimization performance.

Key words: particle swarm optimization, large scale optimization, MapReduce model, distributed, parallel

中图分类号:

TP391

范德斌,邓长寿,袁斯昊,谭旭杰,董小刚. 基于MapReduce模型的分布式粒子群算法[J]. 山东大学学报(工学版), 2016, 46(6): 23-30.

FAN Debin, DENG Changshou, YUAN Sihao, TAN Xujie, DONG Xiaogang. Distributed particle swarm optimization algorithm based on mapreduce[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2016, 46(6): 23-30.

参考文献

[1] KENNEDY J, EBERHART R C.Particle swarm optimization[C] //IEEE International Conference on Neural NetworksPerth. Australia:IEEE, 1995:1942-1948.
[2] 陈永刚,魏汪洋,肖春宝.粒子群优化算法在函数优化上的研究与发展[J].西安邮电学院学报,2009,14(3):113-116. CHEN Yonggang, WEI Wangyang, XIAO Chunbao. Research and development of particle swarm optimization algorithm in function optimazation[J]. Journal of Xi'an University of Post and Telecommunications, 2009, 14(3):113-116.
[3] 孟庆宽,仇瑞承,张漫,等.基于改进粒子群优化模糊控制的农业车辆导航系统[J].农业机械学报,2015,46(3):29-36. MENG Qingkuan, QIU Ruicheng, ZHANG Man, et al. Navigation system of agricultural vehicle based on fuzzy logic controller with improved particle swarm optimization algorithm [J]. Journal of Transactions of the Chinese Society for Agricultural Machinery, 2015, 46(3):29-36.
[4] 徐乐华,凌卫新,熊丽琼.基于面向对象自适应粒子群算法的神经网络训练[J].计算机应用研究,2009,26(1):111-113. XU Lehua, LIN Weixin, XIONG Liqiong.Neural network training based on object-oriented adaptive particle swarm optimization[J].Journal of Application Research of Computers, 2009, 26(1):111-113.
[5] 张鑫源,胡晓敏,林盈. 遗传算法和粒子群优化算法的性能对比分析[J].计算机科学与探索,2014,8(1):90-102. ZHANG Xinyuan, HU Xiaomin, LIN Ying. Comparisons of genetic algorithm and particle swarm optimization[J]. Journal of Frontiers of Computer Science & Technology, 2014, 8(1):90-102.
[6] 金敏,鲁华祥.一种遗传算法与粒子群优化的多子群分层混合算法[J].控制理论与应用,2013,30(10):1231-1238. JIN Min, LU Huaxiang. A multi-subgroup hierarchical hybrid of genetic algorithm and particle swarm optimization[J].Journal of Control Theory & Applications, 2013, 30(10):1231-1238.
[7] 汪靖,吴志健.在GPU上求解大规模优化问题的反向策略的PSO算法[J].武汉大学学报(理学版), 2011,57(2):148-154. WANG Jing, WU Zhijian. Opposition-based particle swarm optimization for solving large scale optimization problems on graphic process unit[J]. Journal of Wuhan University(Science Edition), 2011, 57(2):148-154.
[8] DEAN J, GHEMAWAT S. MapReduce: simplified data processing on large clusters[J]. Proceedings of Operating Systems Design and Implementation, 2004, 51(1):107-113.
[9] DEAN J, GHEMAWAT S. MapReduce: a flexible data processing tool[J]. Communications of the Acm, 2010, 53(1):72-77.
[10] MCNABB A W, MONSON C K, SEPPI K D. Parallel PSO using MapReduce[C] //IEEE Congress on Evolutionary Computation. Singapore:IEEE, 2007:7-14.
[11] 马汉达,杨丽娜.基于Hadoop的PSO-KM聚类算法的并行实现[J].信息技术,2015,39(7):90-94. MA Handa, YANG Lina. Parallel implementation of PSO-KM clustering algorithm based on Hadoop[J]. Journal of information technology, 2015, 39(7):90-94.
[12] 黄奕平,万剑怡,万中英,等. 基于MapReduce的粒子群投影寻踪模型的设计与实现[J].江西师范大学学报(自然科学版),2012,36(4):388-394. HUANG Yiping, WAN Jianyi, WAN Zhongying, et al. The design and implementing for projection pursuit model using PSO based on MapReduce[J]. Journal of Jiangxi Normal University(Natural Science Edition), 2012, 36(4):388-394.
[13] SHI Y, EBERHART R C. Particle swarm optimization with fuzzy adaptive inertia weight[J]. International Journal of Bio Inspired Computation, 2001, 1(12):32-49.
[14] RANGER C, RAGHURAMAN R, PENMETSA A, et al. Evaluating MapReduce for multi-core and multiprocessor systems[C] //IEEE 13th International Symposium on High Performance Computer Architecture. Scottsdale, USA: IEEE, 2007:13-24.
[15] SHI Y, EBERHART R C. A modified particle swarm optimizer[C] //Proceedings of IEEE World Congress on Computational Intelligence. Scottsdale, USA: IEEE,1998:69-73.
[16] LØVBJERG M, RASMUSSEN T K, KRINK T. Hybrid particle swarm optimizer with breeding and subpopulations[C] //Proceedings of International Conference on Genetic and Evolutionary Computation. San Francisco, USA:ACM, 2001:469-476.
[17] 王雪飞,王芳,邱玉辉.一种具有动态拓扑结构的粒子群算法研究[J].计算机科学,2007,34(3):205-207,233. WANG Xuefei, WANG Fang, QIU Yuhui. Research on a Novel Particle Swarm Algorithm with Dynamic Topology [J]. Journal of Computer Science, 2007, 34(3):205-207,233.
[18] 石松,陈云.层次环形拓扑结构的动态粒子群算法[J].计算机工程与应用,2013,49(8):1-5. SHI Song, CHEN Yun.Dynamic particle swarm optimization algorithm with hierarchical ring topology[J].Journal of Computer Engineering and Applications, 2013, 49(8):1-5.
[19] RUCINSKI M, IZZO D, BISCANI F. On the impact of the migration topology on the island model[J]. Parallel Computing, 2010, 36(10):555-571.
[20] YANG Z Y, TANG K, YAO X. Large scale evolutionary optimization using cooperative coevolution[J]. Information Sciences, 2008, 178(15):2985-2999.
[21] YAO X, LIU Y, LIN G M, et al. Evolutionary programming made faster[J].IEEE Transactions On Evolutionary Computation, 1999, 3(2):82-102.

相关文章 15

[1]	梁蒙蒙,周涛,夏勇,张飞飞,杨健. 基于PSO-ConvK卷积神经网络的肺部肿瘤图像识别[J]. 山东大学学报 (工学版), 2018, 48(5): 77-84.
[2]	何文杰 ,何伟超,孙权森. 压缩感知重构算法的并行化及GPU加速[J]. 山东大学学报(工学版), 2018, 48(3): 110-114.
[3]	冯霞,黄熙祥. 基于GEL的机场噪声等值线并行生成算法[J]. 山东大学学报(工学版), 2018, 48(2): 8-13.
[4]	姬安召,王玉风,刘雪芬. 复合Bessel函数零点数值计算方法及分布规律[J]. 山东大学学报(工学版), 2018, 48(1): 71-77.
[5]	宋正强,杨辉玲,肖丹. 基于在线粒子群优化方法的IPMSM驱动电流和速度控制器[J]. 山东大学学报(工学版), 2018, 48(1): 112-116.
[6]	马汉杰,林霞,胥晓晖,张健,张智晟. 基于自适应粒子群算法的智能家居管理系统负荷优化模型[J]. 山东大学学报(工学版), 2017, 47(6): 57-62.
[7]	秦利国,何潇,周东华. 一种时延多智能体系统的分布式编队[J]. 山东大学学报(工学版), 2017, 47(5): 79-88.
[8]	刘洋,刘博,王峰. 基于Parameter Server框架的大数据挖掘优化算法[J]. 山东大学学报(工学版), 2017, 47(4): 1-6.
[9]	李庆冬,骆伟超,叶瑛歆,张承瑞,胡天亮. 基于本体的机床设备资源共享机制[J]. 山东大学学报(工学版), 2017, 47(3): 130-138.
[10]	易云飞,苗剑,林郭隆,殷智. 基于牛顿力学和博弈论模型的粒子网络优化算法[J]. 山东大学学报(工学版), 2017, 47(1): 28-36.
[11]	孙一冰,付敏跃,王炳昌,张焕水. 大规模动态系统的分布式状态估计算法[J]. 山东大学学报(工学版), 2016, 46(6): 62-68.
[12]	王会青,孙宏伟,张建辉. 基于Map/Reduce的时间序列相似性搜索算法[J]. 山东大学学报(工学版), 2016, 46(1): 15-21.
[13]	刘德宝, 吴耀华, 郭耀阳, 王艳艳. 基于串并行混合拣选策略的自动拣选系统品项分配优化[J]. 山东大学学报(工学版), 2015, 45(6): 36-44.
[14]	董红斌, 张广江, 逄锦伟, 韩启龙. 一种基于协同进化方法的聚类集成算法[J]. 山东大学学报(工学版), 2015, 45(2): 1-9.
[15]	任立波, 尚立宝, 闫日雄, 何海澜, 赵红霞, 韩吉田. 脉冲鼓泡床内鼓泡和颗粒混合特性的CFD-DEM数值模拟[J]. 山东大学学报(工学版), 2015, 45(2): 62-66.

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed