Journal of Computer Applications ›› 2017, Vol. 37 ›› Issue (7): 1906-1910.DOI: 10.11772/j.issn.1001-9081.2017.07.1906

Previous Articles     Next Articles

Improved algorithm of artificial bee colony based on Spark

ZHAI Guangming1,2, LI Guohe1,2,3, WU Weijiang1,2,3, HONG Yunfeng3, ZHOU Xiaoming3, WANG Jing1,2   

  1. 1. College of Geophysics and Information Engineering, China University of Petroleum-Beijing, Beijing 102249, China;
    2. Beijing Key Lab of Data Mining for Petroleum Data, China University of Petroleum-Beijing, Beijing 102249, China;
    3. PanPass Institute of Digital Identification Management and Internet of Things, Beijing 100029, China
  • Received:2017-01-24 Revised:2017-02-12 Online:2017-07-10 Published:2017-07-18
  • Supported by:
    This work is partially supported by the National High Technology Research and Development Program (863 Program) of China (2009AA062802), the National Natural Science Foundation of China (60473125), Youth Innovation Fund of China National Petroleum Corporation (CNPC) (05E7013), Sub-project of the National Science and Technology Major Project (G5800-08-ZS-WX), China University of Petroleum-Beijing Karamay Campus Research Start Fund (RCYJ2016B-03-001).


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

  1. 1. 中国石油大学(北京) 地球物理与信息工程学院, 北京 102249;
    2. 中国石油大学(北京) 油气数据挖掘北京市重点实验室, 北京 102249;
    3. 石大兆信数字身份管理与物联网技术研究院, 北京 100029
  • 通讯作者: 翟光明
  • 作者简介:翟光明(1993-),男,湖南怀化人,硕士研究生,主要研究方向:数据挖掘、知识发现;李国和(1965-),男,北京人,教授,博士,主要研究方向:人工智能、机器学习、知识发现;吴卫江(1971-),男,北京人,副教授,博士研究生,主要研究方向:人工智能、知识发现;洪云峰(1966-),男,湖北武汉人,工程师,主要研究方向:ERP、数据管理;周晓明(1963-),男,湖北武汉人,工程师,硕士,主要研究方向:信息管理系统、决策支持;汪静(1989-),女,山东聊城人,硕士研究生,主要研究方向:数据挖掘、知识发现。
  • 基金资助:

Abstract: 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.

Key words: Artificial Bee Colony (ABC) algorithm, Spark, paralleling, gravitational search algorithm, Traveling Salesman Problem (TSP)

摘要: 针对人工蜂群(ABC)算法求解组合优化问题时效率低的问题,提出了基于Spark云计算框架的并行ABC改进算法。首先,将蜂群划分为子蜂群并将蜂群构造为弹性分布式数据集,子蜂群使用广播机制交换优秀个体;然后,采用一系列转换算子,实现蜜蜂寻找解过程的并行化;最后,用万有引力质量计算代替轮盘赌概率计算,减少计算量。通过旅行商问题(TSP)求解说明了算法的可行性。实验结果表明:对比标准ABC算法,所提算法加速比最大达到3.24;对比未改进的并行ABC算法,该算法收敛速度提高约10%。所提算法在复杂问题求解方面优势更加明显。

关键词: 人工蜂群算法, Spark, 并行, 万有引力算法, 旅行商问题

CLC Number: