Improved algorithm of artificial bee colony based on Spark

doi:10.11772/j.issn.1001-9081.2017.07.1906

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 Guangming^1,2, LI Guohe^1,2,3, WU Weijiang^1,2,3, HONG Yunfeng³, ZHOU Xiaoming³, WANG Jing^1,2

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).

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

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

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

通讯作者: 翟光明
作者简介:翟光明(1993-),男,湖南怀化人,硕士研究生,主要研究方向:数据挖掘、知识发现;李国和(1965-),男,北京人,教授,博士,主要研究方向:人工智能、机器学习、知识发现;吴卫江(1971-),男,北京人,副教授,博士研究生,主要研究方向:人工智能、知识发现;洪云峰(1966-),男,湖北武汉人,工程师,主要研究方向:ERP、数据管理;周晓明(1963-),男,湖北武汉人,工程师,硕士,主要研究方向:信息管理系统、决策支持;汪静(1989-),女,山东聊城人,硕士研究生,主要研究方向:数据挖掘、知识发现。
基金资助:
国家863计划项目（2009AA062802）；国家自然科学基金资助项目（60473125）；中国石油（CNPC）石油科技中青年创新基金资助项目（05E7013）；国家重大科技专项子课题（G5800-08-ZS-WX）；中国石油大学（北京）克拉玛依校区科研启动基金资助（RCYJ2016B-03-001）。

Abstract

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:

TP301.6
TP18

ZHAI Guangming, LI Guohe, WU Weijiang, HONG Yunfeng, ZHOU Xiaoming, WANG Jing. Improved algorithm of artificial bee colony based on Spark[J]. Journal of Computer Applications, 2017, 37(7): 1906-1910.

翟光明, 李国和, 吴卫江, 洪云峰, 周晓明, 汪静. 基于Spark的人工蜂群改进算法[J]. 计算机应用, 2017, 37(7): 1906-1910.

References

[1] KARABOGA D. An idea based on honey bee swarm for numerical optimization[R]. Kayseri:Erciyes University, 2005.
[2] KARABOGA D, BASTURK B. On the performance of Artificial Bee Colony (ABC) algorithm[J]. Applied Soft Computing, 2008, 8(1):687-697.
[3] 李乔,郑啸.云计算研究现状综述[J].计算机科学,2011,38(4):32-37.(LI Q, ZHENG X. Research survey of cloud computing[J]. Computer Science, 2011, 38(4):32-37.)
[4] 林闯,苏文博,孟坤,等.云计算安全:架构、机制与模型评价[J].计算机学报,2013,36(9):1765-1784.(LIN C, SU W B, MENG K, et al. Cloud computing security:architecture, mechanism and modeling[J]. Chinese Journal of Computers, 2013, 36(9):1765-1784.)
[5] GHEMAWAT S, GOBIOFF H, LEUNG S. The Google file system[C]//SOSP 2003:Proceedings of the Nineteenth ACM Symposium on Operating Systems Principles. New York:ACM Press, 2003:29-43.
[6] CHANG F, DEAM J, GHEMAWAT S, et al. Bigtable:a distributed storage system for structured data[J]. ACM Transactions on Computer Systems, 2008, 26(2):205-218.
[7] DEAN J, GHEMAWAT S. MapReduce:simplified data processing on large clusters[J]. Communications of the ACM, 2008, 51(1):107-117.
[8] 李建中,王宏志,高宏.大数据可用性的研究进展[J].软件学报,2016,27(7):1605-1625.(LI J Z, WANG H Z, GAO H. State-of-the-art of research on big data usability[J]. Journal of Software, 2016, 27(7):1605-1625.)
[9] 宋杰,刘雪冰,朱志良,等.一种能效优化的MapReduce资源比模型[J].计算机学报,2015,38(1):59-73.(SONG J, LIU X B, ZHU Z L, et al. An energy-efficiency optimized resource ratio model for MapReduce[J]. Chinese Journal of Computers, 2015, 38(1):59-73.)
[10] Alitouka. Spark-DBSCAN[EB/OL].[2016-10-23]. https://github.com/alitouka/spark_dbscan.
[11] 王桂兰,周国亮,萨初日拉,等.Spark环境下的并行模糊C均值聚类算法[J].计算机应用,2016,36(2):342-347.(WANG G L, ZHOU G L, SA C, et al. Parallel fuzzy C-means clustering algorithm in Spark[J]. Journal of Computer Applications, 2016, 36(2):342-347.)
[12] 牛海玲,鲁慧民,刘振杰.基于Spark的Apriori算法的改进[J].东北师大学报(自然科学版),2016,48(1):84-89.(NIU H L, LU H M, LIU Z J. The improvement and research of Apriori algorithm based on Spark[J]. Journal of Northeast Normal University (Natural Science Edition), 2016, 48(1):84-89.)
[13] SABET S, FAROKHI F, SHOKOUHIFAR M. A novel artificial bee colony algorithm for the knapsack problem[C]//INISTA 2012:Proceedings of the 2012 International Symposium on Innovations in Intelligent Systems and Applications. Piscataway, NJ:IEEE, 2012:141-151.
[14] 杨进,马良.蜂群优化算法在车辆路径问题中的应用[J].计算机工程与应用,2010,46(5):214-216.(YANG J, MA L. Wasp colony algorithm for vehicle routing problem[J]. Computer Engineering and Applications, 2010, 46(5):214-216.)
[15] 张维平,任雪飞,李国强,等.改进的万有引力搜索算法在函数优化中的应用[J].计算机应用,2013,35(5):1317-1320.(ZHANG W P, REN X F, LI G Q, et al. Improved gravitation search algorithm and its application to function optimization[J]. Journal of Computer Applications, 2013, 35(5):1317-1320.)
[16] 胡中华,赵敏.基于人工蜂群算法的TSP仿真[J].北京理工大学学报,2009,29(11):978-982.(HU Z H, ZHAO M. Simulation on Traveling Salesman Problem (TSP) based on artificial bees colony algorithm[J]. Transaction of Beijing Institute of Technology, 2009, 29(11):978-982.)
[17] 王诏远,王宏杰,邢焕来,等.基于Spark的蚁群优化算法[J].计算机应用,2015,35(10):2777-2780.(WANG Z Y, WANG H J, XING H L, et al. Ant colony optimization algorithm based on Spark[J]. Journal of Computer Applications, 2015, 35(10):2777-2780.)
[18] CUI W, LI X, ZHOU S, et al. Investigation on process parameters of electrospinning system through orthogonal experimental design[J]. Journal of Applied Polymer Science, 2007, 103(5):3105-3112.
[19] XING H, QU R, KENDALL G, et al. A path-oriented encoding evolutionary algorithm for network coding resource minimization[J] Journal of the Operational Research Society, 2013, 65(8):1261-1277.

Improved algorithm of artificial bee colony based on Spark

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

[1]	WANG Binrong, TAN Dailun, ZHENG Bochuan. Solving auto part spraying sequence by transforming to traveling salesman problem and genetic algorithm [J]. Journal of Computer Applications, 2021, 41(3): 881-886.
[2]	WEI Bo, YANG Rong, SHU Sihao, WAN Yong, MIAO Jianguo. Path planning of mobile robots based on ion motion-artificial bee colony algorithm [J]. Journal of Computer Applications, 2021, 41(2): 379-383.
[3]	Wenxia LI, Linzhong LIU, Cunjie DAI, Yu LI. Artificial bee colony algorithm based on multi-population combination strategy [J]. Journal of Computer Applications, 2021, 41(11): 3113-3119.
[4]	LIU Bin, HE Jinrong, LI Yuancheng, HAN Hong. Apple price prediction method based on distributed neural network [J]. Journal of Computer Applications, 2020, 40(2): 369-374.
[5]	GU Junhua, WANG Feng, QI Yongjun, SUN Zheran, TIAN Zepei, ZHANG Yajuan. Retrieval method of pulmonary nodule images based on multi-scale convolution feature fusion [J]. Journal of Computer Applications, 2020, 40(2): 561-565.
[6]	ZHANG Xiajie, ZHU Jinghua, CHEN Yang. Distributed rough set attribute reduction algorithm under Spark [J]. Journal of Computer Applications, 2020, 40(2): 518-523.
[7]	CUI Yixin, CHEN Xiaodong. Spark framework based optimized large-scale spectral clustering parallel algorithm [J]. Journal of Computer Applications, 2020, 40(1): 168-172.
[8]	CHENG Wenliang, WANG Zhihong, ZHOU Yu, GUO Yi, ZHAO Junfeng. Design of distributed computing framework for foreign exchange market monitoring [J]. Journal of Computer Applications, 2020, 40(1): 173-180.
[9]	ZHANG Zhiqiang, LU Xiaofeng, SUN Qindong, WANG Kan. Improved artificial bee colony algorithm with enhanced exploitation ability [J]. Journal of Computer Applications, 2019, 39(4): 949-955.
[10]	YANG Jidong, SUN Zhaoqi, WANG Feilong. Optimal path control of parallel truss manipulator based on visual grasping [J]. Journal of Computer Applications, 2019, 39(3): 913-917.
[11]	LIU Jing, XIAO Guanfeng. Bus arrival time prediction system based on Spark and particle filter algorithm [J]. Journal of Computer Applications, 2019, 39(2): 429-435.
[12]	LIU Zihao, LI Ling, YE Feng. Anomaly detection method for hydrologic sensor data based on SparkR [J]. Journal of Computer Applications, 2019, 39(2): 436-440.
[13]	ZHANG Weicun, GAO Rui, ZHANG Man. Procurement-production-distribution joint scheduling model in job shop environment [J]. Journal of Computer Applications, 2019, 39(11): 3383-3390.
[14]	LI Longyang, DONG Yihong, SHI Weijie, PAN Jianfei. SQM: subgraph matching algorithm for single large-scale graphs under Spark [J]. Journal of Computer Applications, 2019, 39(1): 46-50.
[15]	ZHAO Wenfang, WANG Jingli, SHANG Min, LIU Yanan. Forecasting model of pollen concentration based on particle swarm optimization and support vector machine [J]. Journal of Computer Applications, 2019, 39(1): 98-104.