基于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]	孙东磊,孙毅,刘蕊,孙鹏凯,张玉敏. 基于岭回归的配电网分布式光伏消纳能力预测方法[J]. 山东大学学报 (工学版), 2025, 55(3): 149-157.
[2]	王辰龑,刘轩,超木日力格. 自适应的并行天牛须优化算法[J]. 山东大学学报 (工学版), 2024, 54(5): 74-80.
[3]	杜睿山,井远光,孟令东,张豪鹏. 基于改进多目标粒子群算法的储气库注气优化[J]. 山东大学学报 (工学版), 2024, 54(4): 42-50.
[4]	刘新,刘冬兰,付婷,王勇,常英贤,姚洪磊,罗昕,王睿,张昊. 基于联邦学习的时间序列预测算法[J]. 山东大学学报 (工学版), 2024, 54(3): 55-63.
[5]	孙园,曾惠权,欧阳苏建,高佳倩,王绮楠,林智勇. 基于粒子群算法的模糊大脑情感学习非线性系统辨识[J]. 山东大学学报 (工学版), 2024, 54(1): 25-32.
[6]	范海雯,郝旭东,赵康,邢法财,蒋哲,李常刚. 基于卷积神经网络的含分布式光伏配电网静态等值[J]. 山东大学学报 (工学版), 2023, 53(4): 140-148.
[7]	刘振,孙媛媛,李亚辉,许庆燊,于涛,庞延庆. 基于用户行为预测的分布式光伏智能社区需求响应策略[J]. 山东大学学报 (工学版), 2022, 52(5): 24-34.
[8]	孙东磊,杨思,韩学山,叶平峰,王宪,刘蕊. 高比例风电接入下计及时段间耦合旋转备用响应风险的动态经济调度方法[J]. 山东大学学报 (工学版), 2022, 52(5): 111-122.
[9]	杨思,王艳,赵斌成,韩学山,刘冬,孙东磊. 含分布式电源的配电网三阶段协同优化调度[J]. 山东大学学报 (工学版), 2022, 52(5): 55-69.
[10]	孙东磊, 鉴庆之, 李智琦, 韩学山, 王明强, 陈博, 付一木. 源网协调的电力系统均匀性规划[J]. 山东大学学报 (工学版), 2022, 52(5): 92-101.
[11]	刘新锋, 张旖旎,徐惠三,宋玲,陈梦雅. 基于随机森林和专家系统的分布式光伏电站阴影遮挡诊断[J]. 山东大学学报 (工学版), 2021, 51(2): 98-104.
[12]	宋士瞻,陈浩宇,张健,王坤,郝庆水. 考虑路灯充电桩接入的城市配电网电压控制方法[J]. 山东大学学报 (工学版), 2020, 50(3): 104-110.
[13]	朱安, 徐初. 一种使用并行交错采样进行超分辨的方法[J]. 山东大学学报 (工学版), 2020, 50(2): 10-16.
[14]	韩方运, 乔梁, 赵斌成, 张利. 基于分时电价的加权太阳能价值电价[J]. 山东大学学报 (工学版), 2019, 49(6): 93-97.
[15]	顾雪平, 杨超, 梁海平, 王元博, 李少岩. 异步电网并行协调恢复策略的优化制定方法[J]. 山东大学学报 (工学版), 2019, 49(5): 9-16.

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed