A Hybrid Ant Colony Algorithm Based on MapReduce

doi:10.3969/j.issn.1006-2475.2016.10.002

Abstract

Abstract: The traditional ant colony algorithm has a slow rate of convergence and is easy to result in local optimal solution. This paper raises a new hybrid ant colony algorithm, which is based on a mixed mode of elite mode and normal mode. The algorithm selects a mode proportionally in each iteration to obtain the optimal path. In this way, we are able to find the optimal path in a less time and avoid falling into local optimal solution. Because of the parallel property of ant colony algorithm, it’s feasible to use MapReduce to run it. Experimental results show that the MapReducebased hybrid ant colony algorithm can find out the optimum path in a relatively less time.

Key words: ant colony algorithm, hybrid ant colony algorithm, MapReduce, cloud computing

CLC Number:

TP301

CAI Ming， ZUO Yongan. A Hybrid Ant Colony Algorithm Based on MapReduce[J]. Computer and Modernization, doi: 10.3969/j.issn.1006-2475.2016.10.002.

References

［1］Colorni A, Dorigo M, Maniezzo V. Distributed optimization by ant colonies［C］// Proceedings of the 1st European Conference on Artificial Life. 1991,142:134-142.
［2］杨剑峰. 蚁群算法及其应用研究［D］. 杭州:浙江大学, 2007.
［3］杨学峰. 蚁群算法求解TSP问题的研究［D］. 长春:吉林大学, 2010.
［4］许智宏,宋勃,郭艳艳. 模拟退火与蚁群混合并行算法解旅行商问题［J］. 河北工业大学学报, 2010,39(2):48-51.
［5］吴昊,倪志伟,王会颖. 基于MapReduce的蚁群算法［J］. 计算机集成制造系统, 2012,18(7):1503-1509.
［6］武交峰. 应用遗传算法提高蚁群算法性能的研究［D］. 太原:太原理工大学, 2007.
［7］Dorigo M, Gambardella L M， Birattari M, et al. Ant Colony Optimization and Swarm Intelligence(Proceedings of the 5th International Workshop(ANTS 2006))［M］. Springer, 2006.
［8］Socha K, Dorigo M. Ant colony optimization for continuous domains［J］. European Journal of Operational Research, 2008,185(3):1155-1173.
［9］Leguizamón G, Coello C A C. An Alternative ACOR Algorithm for Continuous Optimization Problems［M］. Swarm Intelligence. Springer Berlin Heidelberg, 2010:48-59.
［10］Dorigo M, Birattari M, Stützle T. Ant colony optimization［J］. Computational Intelligence Magazine, IEEE, 2006,1(4):28-39.
［11］Dorigo M, Blum C. Ant colony optimization theory: A survey［J］. Theoretical Computer Science, 2005,344(2):243-278.
［12］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.
［13］Dean J, Ghemawat S. MapReduce: Simplified data processing on large clusters［J］. Communications of the ACM, 2008,51(1):107-113.
［14］刘鹏．云计算［M］．北京：电子工业出版社， 2010．
［15］White T. Hadoop: The Definitive Guide［M］. O’Reilly Media. 2012.
［16］Borthakur D. The hadoop distributed file system: Architecture and design［J］. Hadoop Project Website, 2007,11(11):1-10.

[1]	HE Yu-peng, TAO Yong, WANG Bing-heng, ZHAO Ying-nan. Research Status and Prospect of Edge Computing in Smart Distribution Network [J]. Computer and Modernization, 2023, 0(08): 87-92.
[2]	YANG Bo, XU Sheng-chao. Security Protection Method of Cloud Network Special Line Scenarios Based on SRv6#br# Service Chain [J]. Computer and Modernization, 2023, 0(08): 107-111.
[3]	MAO Ming-yang, XU Sheng-chao. Communication Terminal Attack Behavior Identification Algorithm Based on Trusted Cloud Computing#br# [J]. Computer and Modernization, 2022, 0(11): 37-42.
[4]	ZHANG Xiong, PAN Da-zhi, . Ant Colony Algorithm Combining Neighborhood Search Strategy for Vehicle Routing Problem with Time Window [J]. Computer and Modernization, 2022, 0(03): 98-102.
[5]	CAO Yu, LI Xiao-hui, LIU Zhong-lin, JIA He, FEI Zhi-wei. Review of Big Data Workflow Orchestration and Management System in Cloud Environment [J]. Computer and Modernization, 2022, 0(01): 41-53.
[6]	ZHANG Xiao-min. An Attribute-based Multi-keyword Searchable Scheme Based on Bloom Filters [J]. Computer and Modernization, 2021, 0(08): 104-111.
[7]	DENG Bin-tao, XU Sheng-chao. A Differential Evolution K-mediods Clustering Algorithm Based on Dynamic Gemini Population [J]. Computer and Modernization, 2021, 0(07): 54-59.
[8]	WU Jun-cai, LIU Xue-fang . Digital Resource Allocation Based on Cloud Computing and Deep Belief Network [J]. Computer and Modernization, 2021, 0(05): 78-82.
[9]	QU Jian-bo, SUN Jian-wei. Ant Colony Algorithm-based Navigation Satellite Power Enhancement Mission Planning [J]. Computer and Modernization, 2021, 0(02): 104-108.
[10]	GAO Yue-ren, WU Tao, GAO Xia. Dynamic Routing of Routing Frequency Based on Ant Colony Algorithm Optimization [J]. Computer and Modernization, 2020, 0(12): 32-37.
[11]	LU Ge-hao, YANG Dan-ni. Development Status and Prospect of Blockchain as a Service [J]. Computer and Modernization, 2020, 0(10): 31-35.
[12]	LI Xian-liang1，2, ZHOU Qing-ping2, TAN Chang-geng3, TAN Yan-liang2, XU Ze-yang2. Optimal Location of Urban Sports Facilities Based on Ant Colony Algorithm [J]. Computer and Modernization, 2020, 0(03): 33-.
[13]	YE Jia-qi1, FU Qiang1,2, HE Yi-jia1, YE Hao1 . Ant Colony Algorithm Based on Clustering Integration for Solving Large-scale TSP Problems [J]. Computer and Modernization, 2020, 0(02): 31-.
[14]	SHI Hui1, CHEN En2. Distributed Stage Adaptive Association Rules Mining Algorithm Based on Spark [J]. Computer and Modernization, 2019, 0(12): 31-.
[15]	LIANG Ci1, CHEN Shi-ping2. Packet Drift Strategy Based on Packet Cluster Mapping Architecture [J]. Computer and Modernization, 2019, 0(11): 112-.