基于Spark的并行遗传算法求解多峰函数极值  

A Spark based parallel genetic algorithm solving multimodal function extremums

作　　者：刘鹏[1,2] 叶帅 孟磊 王灿[4] 

机构地区：[1]中国矿业大学物联网(感知矿山)研究中心,江苏徐州221008 [2]矿山互联网应用技术国家地方联合工程实验室,江苏徐州221008 [3]中国矿业大学信息与控制工程学院,江苏徐州221116 [4]华东计算技术研究所航天产品部,上海201808

出　　处：《计算机工程与科学》2018年第2期210-217,共8页Computer Engineering & Science

基　　金：国家自然科学基金(61471361;41302203)

摘　　要：遗传算法求解多峰函数极值需进行反复多次的迭代运算,面对大数据样本时会出现运算效率过低的现象,这极大地限制了遗传算法的实际应用。经典Hadoop并行平台可在一定程度上提高遗传算法的运行效率,而新一代Spark并行平台可以更加充分地发挥遗传算法的并行潜能。设计并实现了基于Spark的并行遗传算法,在各个子节点上并行执行子种群个体的交叉、变异等操作,达到了高度并行化进化种群以高效求取多峰函数极值的目的。为方便比较,同时设计并实现了单机及Hadoop平台下的相应算法。实验结果表明,处理大数据样本时,相比传统单机和Hadoop平台,基于Spark的并行化遗传算法显著降低了求解多峰函数极值的耗时,大幅提高了算法的效率;同时,由于其并行计算带来的强大随机性,也有效避免了种群单一过早收敛的问题,提高了算法的准确性。The Genetic Algorithm（GA）needs many computation iterations in solving multimodal function extremums,so its running efficiency is too low when dealing with large-scale data,which greatly limits its practical application.The classical parallel platform Hadoop can improve the GA running efficiency to some extent,while the state-of-the-art parallel platform Spark can release much more parallelism of GA by realizing parallel crossover,mutation and other operations on each computing node.For the convenience of comparison,the GA solving multimodal function extremums are designed and implemented on single node,Hadoop and Spark,respectively.Experimental results show that,compared with single node platform and Hadoop platform,the Spark based implementation not only significantly reduces the running time but also effectively avoids the problem of premature convergence because of its powerful randomness,while dealing with large-scale samples.

关 键 词：遗传算法 多峰函数 极值 并行计算 SPARK HADOOP 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]