Ant colony optimization algorithm based on Spark

doi:10.11772/j.issn.1001-9081.2015.10.2777

Abstract

Abstract: To deal with the combinatorial optimization problem in the era of big data, a parallel Ant Colony Optimization (ACO) algorithm based on Spark, a framework for the distributed memory computing, was presented. To achieve the parallelization of the phase of solution construction in ant colony optimization, a class of ants was encapsulated to a resilient distributed dataset and the corresponding transformation operators were given. The simulation results in solving the Traveling Salesman Problem (TSP) prove the feasibility of the proposed parallel algorithm. Under the same experimental environment, the comparison results between MapReduce based ant colony algorithm and the proposed algorithm show that the proposed algorithm significantly improves the optimization speed at least ten times than the MapReduce one.

Key words: Ant Colony Optimization (ACO) algorithm, paralleling, Spark, Hadoop, cloud computing

摘要： 为应对大数据时代中组合优化问题的求解,基于云计算框架Spark,借助其基于内存、分布式的特定,提出一种并行蚁群优化算法。其思路是通过将蚂蚁构造为弹性分布式数据集,由此给出相应的一系列转换算子,实现了蚂蚁构造解过程的并行化。通过在旅行商问题(TSP)求解的仿真实验结果说明了所提出的并行算法的可行性;并在同等实验环境下对比基于MapReduce的蚁群优化算法,优化速度提升达10倍以上。

关键词: 蚁群优化算法, 并行, Spark, Hadoop, 云计算

CLC Number:

TP311

WANG Zhaoyuan, WANG Hongjie, XING Huanlai, LI Tianrui. Ant colony optimization algorithm based on Spark[J]. Journal of Computer Applications, 2015, 35(10): 2777-2780.

王诏远, 王宏杰, 邢焕来, 李天瑞. 基于Spark的蚁群优化算法[J]. 计算机应用, 2015, 35(10): 2777-2780.

References

[1] YANG X. Nature-inspired metaheuristic algorithms[M]. [S.l.]: Luniver Press, 2010.
[2] GOLDBERG D E. Genetic algorithms in search, optimization, and machine learning[M]. Upper Saddle River: Addison Wesley Professional, 1989.
[3] POLI R, KENNEDY J, BLACKWELL T. Particle swarm optimization-an overview[EB/OL]. [2014-10-10]. http://cswww.essex.ac.uk/staff/rpoli/papers/PoliKennedyBlackwellSI2007.pdf.
[4] DORIGO M, GAMBARDELLA L M. Ant colonies for the travelling salesman problem[J]. Biosystems,1997, 43(2): 73-81.
[5] DORIGO M, GAMBARDELLA L M. Ant colony system: a cooperative learning approach to the traveling salesman problem[J]. IEEE Transactions on Evolutionary Computation, 1997, 1(1): 53-66.
[6] DORIGO M, MANIEZZO V, COLORNI A. Ant system: optimization by a colony of cooperating Agents[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 1996, 26(1): 29-41.
[7] ZHANG J, GU Z, ZHENG C. Survey of research progress on cloud computing[J]. Application Research of Computers, 2010, 27(2): 429-433. (张建勋, 古志民, 郑超. 云计算研究进展综述[J]. 计算机应用研究, 2010, 27(2): 429-433.)
[8] 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.
[9] CHANG F, DEAN J, GHEMAWAT S, et al. Bigtable: a distributed storage system for structured data[J]. ACM Transactions on Computer Systems, 2008, 26(2): 205-218.
[10] DEAN J, GHEMAWAT S. MapReduce: simplified data processing on large clusters[J]. Communications of the ACM, 2008, 51(1): 107-113.
[11] BURROWS M. The Chubby lock service for loosely-coupled distributed systems[C]//Proceedings of the 7th USENIX Symposium on Operating Systems Design and Implementation. Berkeley: USENIX,2006: 335-350.
[12] WHITE T. Hadoop: the definitive guide[M]. Sebastopol: O'Reilly Media,2012.
[13] ZHANG J, LI T, RUAN D, et al. A parallel method for computing rough set approximations[J]. Information Sciences, 2012, 194(5): 209-223.
[14] ZHAO W, MA H, HE Q. Parallel k-means clustering based on MapReduce [C]//CloudCom 2009: Proceedings of the 1st International Conference on Cloud Computing. Berlin: Springer-Verlag, 2009:674-679.
[15] HE L, FENG D, WANG R, et al. MapReduce-based large-scale online social network worm simulation[J]. Journal of Software, 2013, 24(7): 1666-1682 (和亮, 冯登国, 王蕊,等. 基于 MapReduce 的大规模在线社交网络蠕虫仿真[J]. 软件学报, 2013, 24(7): 1666-1682.)
[16] LI J. MapReduce implements of several cloud computing and data mining algorithms[D]. Chengdu: University of Electronic Science and Technology of China, 2010. (李军华. 云计算及若干数据挖掘算法的MapReduce化研究[D]. 成都:电子科技大学, 2010.)
[17] PAN W, LI H, WU S, et al. Evaluating large graph processing in MapReduce based on message passing[J]. Chinese Journal of Computers, 2011,34(10): 1768-1784. (潘巍, 李战怀, 伍赛,等.基于消息传递机制的MapReduce图算法研究[J]. 计算机学报, 2011,34(10): 1768-1784.)
[18] LIU Y, JING N, CHEN L, et al. Algorithm for processing k-nearest join based on R-tree in MapReduce[J]. Journal of Software, 2013,24(8): 1836-1851. (刘义, 景宁, 陈荦,等. MapReduce框架下基于R-树的k-近邻连接算法[J]. 软件学报, 2013,24(8): 1836-1851.)
[19] LI Y, DENG S, WAN Y, et al. PageRank matrix partitioned algorithm based on MapReduce-Hadoop[J]. Computer Technology and Development, 2011,21(8): 6-9. (李远方, 邓世昆, 闻玉彪,等. Hadoop-MapReduce下的PageRank矩阵分块算法[J]. 计算机技术与发展, 2011,21(8): 6-9.)
[20] XIE X. An I/O-efficient MapReduce system[D]. Wuhan: Huazhong University of Science and Technolgy, 2013. (谢旭. 基于I/O高效性的MapReduce系统[D]. 武汉:华中科技大学, 2013.)
[21] ZAHARIA M, CHOWDHURY M, FRANKLIN M J, et al. Spark: cluster computing with working sets[C]//Proceedings of the 2nd USENIX Conference on Hot Topics in Cloud Computing. Berkeley: USENIX,2010: 10.
[22] ZAHARIA M, CHOWDHURY M, DAS T, et al. Resilient distributed datasets: a fault-tolerant abstraction for in-memory cluster computing[C]//Proceedings of the 9th USENIX Conference on Networked Systems Design and Implementation. Berkeley: USENIX, 2012:141-146.
[23] MERKLE D, MIDDENDORF M, SCHMECK H. Ant colony optimization for resource-constrained project scheduling[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(4): 333-346.
[24] BELL J E, McMULLEN P R. Ant colony optimization techniques for the vehicle routing problem[J]. Advanced Engineering Informatics, 2004, 18(1): 41-48.
[25] DORIGO M, BLUM C. Ant colony optimization theory: a survey[J]. Theoretical Computer Science, 2005, 344(2): 243-278.
[26] JIA R, LI Y. Quantum-inspired ant colony algorithm based on MapReduce model[J]. Computer Engineering and Applications, 2013,49(19):246-249. (贾瑞玉, 李亚龙. 基于MapReduce的量子蚁群算法[J]. 计算机工程与应用, 2013,49(19): 246-249.)
[27] WANG H, NI Z, WU H. MapReduce-based ant colony optimization algorithm for multi-dimensional knapsack problem[J]. Computer Engineering, 2013,39(4): 248-253. (王会颖, 倪志伟, 吴昊. 求解多维背包问题的MapReduce蚁群优化算法[J]. 计算机工程, 2013,39(4): 248-253.)
[28] WANG H, NI Z, WU Z. Multi-tenant service customization algorithm based on MapReduce and multi-objective ant colony optimization[J]. Pattern Recognition and Artificial Intelligence, 2014,27(12): 1105-1116. (王会颖, 倪志伟, 伍章俊. 基于MapReduce和多目标蚁群算法的多租户服务定制算法[J]. 模式识别与人工智能, 2014,27(12): 1105-1116.)
[29] WANG Z, LI T, YI X. Approach for development of ant colony optimization based on MapReduce[J]. Computer Science, 2014,41(7): 261-265 (王诏远, 李天瑞, 易修文. 基于MapReduce的蚁群优化算法实现方法[J]. 计算机科学, 2014,41(7): 261-265).
[30] WU H, NI Z, WANG H. MapReduce-based ant colony optimization[J]. Computer Integrated Manufacturing Systems, 2012,18(7): 1503-1509. (吴昊, 倪志伟, 王会颖. 基于MapReduce的蚁群算法[J]. 计算机集成制造系统, 2012,18(7): 1503-1509.)
[31] XIA W, WANG L. Research on and implementation of parallel ant colony algorithm based on MapReduce[J]. Electronic Science and Technology, 2013,26(2): 146-149. (夏卫雷, 王立松. 基于MapReduce的并行蚁群算法研究与实现[J]. 电子科技, 2013,26(2): 146-149.)
[32] BIAN H, CHEN Y, DU X, et al. Equivalent connection optimization based on Spark[J]. Journal of East China Normal University: Natural Sciences, 2014(5): 263-270. (卞昊穹, 陈跃国, 杜小勇,等. Spark上的等值连接优化[J]. 华东师范大学学报:自然科学版, 2014(5): 263-270.)
[33] QIU R. Implement and application of CURE algorithm based on Spark[D]. Guangzhou: South China University of Technology, 2014. (邱荣财. 基于Spark平台的CURE算法并行化设计与应用[D]. 广州:华南理工大学, 2014.)
[34] TANG Z. The design and implement of a machine learning platform based on Spark[D]. Xiamen: Xiamen University, 2014. (唐振坤. 基于Spark的机器学习平台设计与实现[D]. 厦门:厦门大学, 2014.)
[35] STUTZLE T, HOOS H. MAX-MIN ant system and local search for the traveling salesman problem[C]//ICEC 1997: Proceedings of the 1997 IEEE International Conference on Evolutionary Computation. Piscataway: IEEE Press, 1997:309-314.
[36] REINELT G. TSPLIB-a traveling salesman problem library[J]. ORSA Journal on Computing, 1991, 3(4): 376-384.
[37] 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.
[38] 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.