粗粒度并行遗传算法的MapReduce并行化实现  

Parallel Implementation of Coarse-Grained Parallel Genetic Algorithm with MapReduce model

作　　者：程兴国[1] 肖南峰[1] 

机构地区：[1]华南理工大学计算机科学与工程学院,广州510006

出　　处：《重庆理工大学学报（自然科学）》2013年第10期66-70,74,共6页Journal of Chongqing University of Technology：Natural Science

基　　金：国家自然科学基金资助项目(61171141);广东省产学研省部合作专项资金资助项目(2012B091100448)

摘　　要：针对粗粒度并行遗传算法的特点,给出了MapReduce编程模型实现遗传算法的方法。将随机生成的初始种群分割成若干个子种群,用Map方法实现单个子种群的传统遗传算法。各个子种群在不同的Node上相互独立地并发执行个体适应值计算、选择、交叉和变异等操作,在Partition环节将每个子群所提取的最优个体迁移到其他子种群中,以实现各个子种群的共同进化。该方法充分利用了MapReduce的高度并行性,提高了算法的效率,同时在一定程度上克服了过早收敛和局部最优解问题。According to theproperties of Coarse-Grained Parallel Genetic Algorithm,the article provides a method to implement it based on MapReduce programming model.Firstly,the initial population is divided into a few subpopulations,and each of these subpopulations is maintained by different Tasktracker in which the classical Genetic Algorithm （GA）,such as fitness calculation,selection,crossover and mutation are executed in Map function,and then some excellent individuals are selected and migrated to other subpopulation in the Partition phase.The experiments on the Hadoop platform indicate this method can not only improve the efficiency of Genetic Algorithm thanks to the high Parallelism of MapReduce model,but also eliminate,to some extent,the problem of early convergence and local optima of classic GA.

关 键 词：遗传算法 粗粒度并行遗传算法 MAPREDUCE 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]