计算机科学 ›› 2016, Vol. 43 ›› Issue (9): 116-119.doi: 10.11896/j.issn.1002-137X.2016.09.022

• 2015 年第三届CCF 大数据学术会议 • 上一篇    下一篇

SparkDE:一种基于RDD云计算模型的并行差分进化算法

谭旭杰,邓长寿,董小刚,袁斯昊,吴志健,彭虎   

  1. 九江学院信息科学与技术学院 九江332005,九江学院信息科学与技术学院 九江332005,九江学院信息科学与技术学院 九江332005,九江学院信息科学与技术学院 九江332005,武汉大学软件工程国家重点实验室 武汉430072,武汉大学软件工程国家重点实验室 武汉430072
  • 出版日期:2018-12-01 发布日期:2018-12-01
  • 基金资助:
    本文受国家自然科学基金资助

SparkDE:A Parallel Version of Differential Evolution Based on Resilient Distributed Datasets Model in Cloud Computing

TAN Xu-jie, DENG Chang-shou, DONG Xiao-gang, YUAN Si-hao, WU Zhi-jian and PENG Hu   

  • Online:2018-12-01 Published:2018-12-01

摘要: 云计算MapReduce并行编程模型广泛应用于数据密集型应用领域,基于该模型的开源平台Hadoop在大数据领域获得了成功应用。然而,对于计算密集型任务,特别是迭代运算,频繁启动Map和Reduce过程将导致负载过大,影响计算效率。弹性分布式数据集(RDD)是一种基于内存的集群计算模型,有效地支持迭代运算,能够克服负载过大的问题。因此提出基于RDD模型的并行差分进化算法SparkDE。SparkDE首先将整个种群划分为若干个独立岛,然后将一个岛对应RDD中的一个分区,每个岛在RDD的一个分区中独立进化指定代数后,利用迁移算子在岛之间交换信息。利用标准测试问题对SparkDE、基于MapReduce模型的MRDE和基本DE进行对比实验研究。实验结果表明SparkDE求解精度高,计算速度快,加速效果明显,可以作为云计算平台的下一代优化器。

关键词: 并行差分进化算法,岛模型,弹性分布式数据集,转换操作,控制操作

Abstract: MapReduce is a popular cloud computing model which has been applied in data-intensive fields,and Hadoop which is based on MapReduce has been successfully used in dealing with big data.However,when dealing with computation-intensive tasks,particularly iterative computation,frequent loading of Map and Reduce processes will lead to overload.Resilient distributed dataset has been implemented in Spark,and it is an in-memory clustering computing model which can overcome this shortcoming efficiently.In this paper,a parallel version of differential evolution based on RDD (resilient distributed datasets) model named SparkDE was proposed.In SparkDE,the whole population is divided into several islands which evolve on their own,and then each island is deployed into a partition of RDD.After evolution for predefined generation in each island,migration operator is used calculation between islands.A wide range of benchmark problems are adopted to conduct numerical experiments.Compared with MapReduce (MRDE) based DE and classical DE,the results show that SparkDE can achieve higher accuracy of solution and faster speed of computation.The speedup of SparkDE is obvious.Thus SparkDE can serve as the next generation of optimizer in cloud computing.

Key words: Parallel differential evolution,Island model,Resilient distributed datasets,Transformation operation,Action operation

[1] 王宇平.进化计算的理论和方法[M].北京:科学出版社,2011
[2] Eiben A E,Smith J.From evolutionary computation to the evolution of things[J].Nature,2015,521(7553):476-482
[3] Vesterstrom J,Thomsen R.A comparative study of differential evolution,particle swarm optimization,and evolutionary algorithms on numerical benchmark problems[C]∥IEEE on CEC 2004.IEEE,2004:1980-1987
[4] Rocca P,Oliveri G,Massa A.Differential evolution as applied to electromagnetics[J].Antennas and Propagation Magazine,IEEE,2011,53(1):38-49
[5] Shen Ji-nan,Liang Fang,Zheng Ming-hui.Deep predation and secondary gradient acceleration differential evolution algorithm[J].J.Huazhong Univ.of Sci.& Tech.(Natural Science Edition), 2014,2(11):23-27,3(in Chinese) 沈济南,梁芳,郑明辉.深度捕食二次梯度加速差分进化算法[J].华中科技大学学报(自然科学版),2014,2(11):23-27,3
[6] Chen Ying,Lin Ying,Hu Xiao-min.Parallel Differential Evolution with Multi-Population and Multi-Strategy[J].Journal of Frontiers of Computer Science and Technology,2014,8(12):1502-1510(in Chinese) 陈颖,林盈,胡晓敏.多种群多策略的并行差分进化算法[J].计算机科学与探索,2014,8(12):1502-1510
[7] Bi Xiao-jun,Liu Guo-an, Xiao Jing.Dynamic Adaptive Differential Evolution Based on Novel Mutation Strategy[J].Journal of Computer Research and Development,2012,9(6):1288-1297(in Chinese) 毕晓君,刘国安,肖婧.基于新变异策略的动态自适应差分进化算法[J].计算机研究与发展,2012,9(6):1288-1297
[8] Dean J,Chemawat S.MapReduce:simplified data processing on large clusters[J].Communications of the ACM,2008,1(1):107-113
[9] Wang Zhao-yuan,Li Tian-rui,Yi Xiu-wen.Approach for Development of Ant Colony Optimization Based on MapReduce[J].Computer Science,2014,1(7):261-265(in Chinese) 王诏远,李天瑞,易修文.基于MapReduce的蚁群优化算法实现方法[J].计算机科学,2014,1(7):261-265
[10] Zhou C.Fast parallelization of differential evolution algorithmusing MapReduce[C]∥Proceedings of the 12th Annual Confe-rence on Genetic and Evolutionary Computation.ACM,2010:1113-1114
[11] Pavlech M.Framework for Development of Distributed Evolutionary Algorithms Based on MapReduce[C]∥Annals of DAAAM for 2011 & Proceedings of the 22nd International DAAAM Symposium Intelligent Manufacturing & Automation:Power of Knowledge and Creativity.Vienna:DAAAM International Vienna.2011:1475-1476
[12] 夏俊鸾,刘旭辉,邵赛赛,等.Spark大数据处理技术[M].北京:电子工业出版社,2015
[13] Zaharia M,Chowdhury M,Das T,et al.Resilient distributeddatasets:A fault-tolerant abstraction for in-memory cluster computing[C]∥Proceedings of the 9th USENIX Conference on Networked Systems Design and Implementation.USENIX Association,2012:1-16
[14] Jumonj T,Chakraborty G,Mabuchi H,et al.A novel distributed genetic algorithm implementation with variable number of islands[C]∥IEEE Congress on Evolutionary Computation,2007(CEC 2007).IEEE,2007:4698-4705
[15] Yao X,Liu Y,Lin G.Evolutionary programming made faster[J].IEEE Transactions on Evolutionary Computation,1999,3(2):82-102
[16] Yang Z,Tang K,Yao X.Large scale evolutionary optimizationusing cooperative coevolution [J].Information Sciences,2008,178(15):2985-2999
[17] Kiyouharu T,Takashi I.Concurrent Differential EvolutionBased on MapReduce[J].International Journal of Computers,2010,4(4):161-168

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!