基于Spark的人工蜂群改进算法  

Improved algorithm of artificial bee colony based on Spark

作　　者：翟光明[1,2] 李国和[1,2,3] 吴卫江[1,2,3] 洪云峰 周晓明 汪静[1,2] 

机构地区：[1]中国石油大学(北京)地球物理与信息工程学院,北京102249 [2]中国石油大学(北京)油气数据挖掘北京市重点实验室,北京102249 [3]石大兆信数字身份管理与物联网技术研究院,北京100029

出　　处：《计算机应用》2017年第7期1906-1910,共5页journal of Computer Applications

基　　金：国家863计划项目(2009AA062802);国家自然科学基金资助项目(60473125);中国石油(CNPC)石油科技中青年创新基金资助项目(05E7013);国家重大科技专项子课题(G5800-08-ZS-WX);中国石油大学(北京)克拉玛依校区科研启动基金资助(RCYJ2016B-03-001)~~

摘　　要：针对人工蜂群(ABC)算法求解组合优化问题时效率低的问题,提出了基于Spark云计算框架的并行ABC改进算法。首先,将蜂群划分为子蜂群并将蜂群构造为弹性分布式数据集,子蜂群使用广播机制交换优秀个体;然后,采用一系列转换算子,实现蜜蜂寻找解过程的并行化;最后,用万有引力质量计算代替轮盘赌概率计算,减少计算量。通过旅行商问题(TSP)求解说明了算法的可行性。实验结果表明:对比标准ABC算法,所提算法加速比最大达到3.24;对比未改进的并行ABC算法,该算法收敛速度提高约10%。所提算法在复杂问题求解方面优势更加明显。To combat low efficiency of Artificial Bee Colony （ABC） algorithm on solving combinatorial problem, a parallel ABC optimization algorithm based on Spark was presented. Firstly, the bee colony was divided into subgroups among which broadcast was used to transmit data, and then was constructed as a resilient distributed dataset. Secondly, a series of transformation operators were used to achieve the parallelization of the solution search. Finally, gravitational mass calculation was used to replace the roulette probability selection and reduce the time complexity. The simulation results in solving the Traveling Salesman Problem （TSP） prove the feasibility of the proposed parallel algorithm. The experimental results show that the proposed algorithm provides a 3.24x speedup over the standard ABC algorithm and its convergence speed is increased by about 10% compared with the unimproved parallel ABC algorithm. It has significant advantages in solving high dimensional problems.

关 键 词：人工蜂群算法 SPARK 并行 万有引力算法 旅行商问题 

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