JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE) ›› 2016, Vol. 46 ›› Issue (6): 23-30.doi: 10.6040/j.issn.1672-3961.1.2016.161

Previous Articles     Next Articles

Distributed particle swarm optimization algorithm based on mapreduce

FAN Debin, DENG Changshou*, YUAN Sihao, TAN Xujie, DONG Xiaogang   

  1. School of Information and Technology, Jiujiang University, Jiujiang 332005, Jiangxi, China
  • Received:2015-12-31 Online:2016-12-20 Published:2015-12-31

PDF (PC)

898

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

CLC Number: 

  • TP391
[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.
[1] WANG Qi, SUN Zhumei, LIU Shaohong, BAI Jianyun. Integration transform of dust removal system based on fieldbus compatible technology [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2018, 48(4): 37-41.
[2] HE Wenjie, HE Weichao, SUN Quansen. Parallelization and GPU acceleration of compressive sensing reconstruction algorithm [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2018, 48(3): 110-114.
[3] FENG Xia, HUANG Xixiang. Airport noise isoline parallel generating algorithm based on grid edge labeling [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2018, 48(2): 8-13.
[4] QIN Liguo, HE Xiao, ZHOU Donghua. A new distributed formation for multi-agent systems with constant time delays [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2017, 47(5): 79-88.
[5] LIU Yang, LIU Bo, WANG Feng. Optimization algorithm for big data mining based on parameter server framework [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2017, 47(4): 1-6.
[6] LI Qingdong, LUO Weichao, YE Yingxin, ZHANG Chengrui, HU Tianliang. Sharing mechanism of machine tool resource based on ontology [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2017, 47(3): 130-138.
[7] YI Yunfei, MIAO Jian, LIN Guolong, YIN Zhi. Particle network optimization algorithm based on Newtonian mechanics and game theory model [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2017, 47(1): 28-36.
[8] SUN Yibing, FU Minyue, WANG Bingchang, ZHANG Huanshui. Distributed state estimation algorithm for large-scale dynamic systems [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2016, 46(6): 62-68.
[9] WANG Huiqing, SUN Hongwei, ZHANG Jianhui. Time series similarity searching algorithm based on Map/Reduce [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2016, 46(1): 15-21.
[10] JIANG Mingjing, FANG Wei, SIMA Jun. Calibration of micro-parameters of parallel bonded model for rocks [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2015, 45(4): 50-56.
[11] DONG Hongbin, ZHANG Guangjiang, PANG Jinwei, HAN Qilong. A clustering ensemble algorithm based on co-evolution [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2015, 45(2): 1-9.
[12] REN Libo, SHANG Libao, YAN Rixiong, HE Hailan, ZHAO Hongxia, HAN Jitian. CFD-DEM simulation of bubbling and particle mixing properties in pulsed jet fluidized bed [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2015, 45(2): 62-66.
[13] YANG Longhao, FU Yanggeng, GONG Xiaoting. Parallel differential evolution algorithm for parameter learning of belief rule base [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2015, 45(1): 30-36.
[14] WANG Huifang, ZHAO Zhicheng, ZHANG Jinggang. Design of a fractional order IMC-IDμ controller for high order systems [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2014, 44(6): 77-82.
[15] HUA Jingxin, BO Yuming, CHEN Zhimin. Forecasting of real estate market based on particle swarm optimized neural network [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2014, 44(4): 22-30.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] SHEN Xiaojing, CHEN Ming, CHI Tao. An novel information fusion algorithm of multi-Agent water quality monitoring system[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2014, 44(4): 39 -45 .
[2] WANG Lihong, LI Qiang. A selective ensemble method for traveling salesman problems[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2016, 46(1): 42 -48 .
[3] ZOU Guofeng, FU Guixia, LI Zhenmei, LI Haitao, WANG Kejun. Face image quality evaluation method based on the fusion of two level evaluation indexes[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2016, 46(2): 6 -13 .
[4] WANG Yijun, ZHANG Hui, LI Bo, YANG Chunming, ZHAO Xujian. A method of opinion leaders discovering based on the topical evolution[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2016, 46(2): 35 -42 .
[5] LIU Dakun, TAN Xiaoyang. Fitting of constrained local model based on manifold[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2016, 46(3): 31 -36 .
[6] LIU Zhijun. Color image encryption algorithm based on complex chaos and affine transform[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2016, 46(4): 1 -8 .
[7] JI Xingquan, HAN Guozheng, LI Kejun, FU Rongrong, ZHU Yanghe. Application of improved K-means clustering algorithm based on density in distribution network block partitioning[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2016, 46(4): 41 -46 .
[8] LIU Bin, SONG Rui, CHAI Hui. Buffering strategy for articulated legged robot based on virtual model control and acceleration planning[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2016, 46(6): 69 -75 .
[9] YI Yunfei, MIAO Jian, LIN Guolong, YIN Zhi. Particle network optimization algorithm based on Newtonian mechanics and game theory model[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2017, 47(1): 28 -36 .
[10] WAN Li, WANG Chunhe, WANG Qi, LI Shucai, SHAO Xing, JIANG Bei, SUN Huibin, QIN Qian. The control mechanism for super section tunnel on weak surrounding rock and its application[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2017, 47(1): 59 -67 .
Copyright 2018 © Editorial office of Journal of Shandong University (Engineering Science)
Supported by Beijing Magtech Co.Ltd