基于Hama并行蚁群算法模型及TSP应用研究

交通运输系统工程与信息 ›› 2016, Vol. 16 ›› Issue (3): 168-173.

基于Hama并行蚁群算法模型及TSP应用研究

马继辉*，余明捷，陈鑫杰，宋翠颖，杨扬

北京交通大学交通运输学院，北京100044

收稿日期:2016-01-26 修回日期:2016-04-22 出版日期:2016-06-25 发布日期:2016-06-27
作者简介:马继辉（1972-），男，辽宁建昌人，副教授，博士.
基金资助:
科技部“863”项目/ Ministry of Science and Technology 863 Plan（2015AA124103）.

Hama-based Parallel Ant Colony Optimization Algorithm Mode and TSP Applied Research

MAJi-hui, XU Ming-jie, CHEN Xin-jie, SONG Cui-ying, YANG Yang

School of Traffic and Transportation, Beijing Jiaotong University, Beijing 100044, China

Received:2016-01-26 Revised:2016-04-22 Online:2016-06-25 Published:2016-06-27

摘要/Abstract

摘要：

Hama 是建立在Hadoop 上的分布式并行计算模型，基于BSP (Bulk Synchronous Parallel, BSP)计算技术的开放式并行计算平台，它的主要功能是支持并行及大数据的科学计算.目前改进传统启发式算法，移植到Hama平台提高算法效率是研究热点之一.蚁群算法是适应性极强的启发式算法，应用广泛，但由于蚁群中个体的随机性，解的收敛速度与解的多样性、稳定性之间存在矛盾.而该矛盾可通过将蚁群算法并行化得到缓解，算法求解性能因此得到提升.本文在Hama 平台上，选择以信息素矩阵进行交互的策略，建立了并行蚁群算法模型，并通过该模型求解多种规模下的旅行商问题.实验表明，本文提出的并行蚁群算法模型可行，并能有效地提高算法性能.

关键词: 信息技术, 蚁群算法, Hama, 并行, TSP, 共享信息素矩阵

Abstract:

Hama is a large-scale parallel computing tools, which works on Hadoop platform and is based on the open parallel computing platform of BSP computing technology. Its main function is to support the scientific calculation of parallel and big data. To enhance the efficiency, many algorithms are transplanted to Hama platform, which becomes an advanced research hotspot. Ant colony algorithm is a highly adaptive heuristic algorithm, which is widely used. Because of the randomness of the individual, there is a contradiction between the convergence speed and the diversity and stability of the solution. But this contradiction can be alleviated by the paralleled ant colony algorithm, and the performance of the algorithm can be improved correspondingly. This paper tries to realize a parallel ant colony algorithm, which based within the framework of Bulk Synchronous Parallel. The experimental results show that the parallel ant colony algorithm is feasible and effectively improves the performance.

Key words: information technology, ant colony optimization algorithm, Hama, parallel, TSP, sharing pheromone matrix

中图分类号:

U495

马继辉，余明捷，陈鑫杰，宋翠颖，杨扬. 基于Hama并行蚁群算法模型及TSP应用研究[J]. 交通运输系统工程与信息, 2016, 16(3): 168-173.

MAJi-hui, XU Ming-jie, CHEN Xin-jie, SONG Cui-ying, YANG Yang. Hama-based Parallel Ant Colony Optimization Algorithm Mode and TSP Applied Research[J]. Journal of Transportation Systems Engineering and Information Technology, 2016, 16(3): 168-173.

导出引用管理器 EndNote|Ris|BibTeX

链接本文: http://www.tseit.org.cn/CN/abstract/abstract19201.shtml

http://www.tseit.org.cn/CN/Y2016/V16/I3/168

参考文献

[1] GASS S I. Traveling salesman problem[M]. Combinatorial Heuristic Algorithms with FORTRAN, Springer Berlin Heidelberg, 1986.

[2] 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.

[3] LU Q, ZHOU X. GPU parallel ant colony algorithm for the dynamic one-dimensional cutting stock problem based on the on-line detection[J]. Yi Qi Yi Biao Xue Bao/Chinese Journal of Scientific Instrument, 2015, 36 (8):1774-1782.

[4] GUERRERO G D, CECILIA J M, LLANES A, et al. Comparative evaluation of platforms for parallel ant colony optimization[J]. Journal of Supercomputing, 2014, 69(1):318-329.

[5] THIRUVADY D, ERNST A T, SINGH G. Parallel ant colony optimization for resource constrained job scheduling[J]. Annals of Operations Research, 2014, 103 (1):1-18.

[6] LI B H, LU M, SHAN Y G, et al. Parallel ant colony optimization for the determination of a point heat source position in a 2-d domain[J]. Journal of the American Chemical Society, 2015, 91(1): 994-1002.

[7] SEO S, YOON E J, KIM J, et al. HAMA: An efficient matrix computation with the mapreduce framework[C]// Cloud Computing Technology and Science (CloudCom), 2010 IEEE Second International Conference on. IEEE, 2010: 721-726.

[8] LUO S, LIU L, WANG H, et al. Implementation of a parallel graph partition algorithm to speed up BSP computing[C]//Fuzzy Systems and Knowledge Discovery (FSKD), 2014 11th International Conference on. IEEE, 2014: 740-744.

[9] 吕强，高彦明，钱培德. 共享信息素矩阵:一种新的并行ACO 方法[J]. 自动化学报, 2007(4): 418-421. [LV Q, GAO Y M, QIAN P D. Sharing one pheromone matrix: A new approach to parallel ACO[J]. Acta Automatica Sinica, 2007(4): 418-421.]

[10] ALIANT L G. Why BSP computers? (bulk-synchronous parallel computers) [C]//Parallel Processing Symposium, 1993, Proceedings of Seventh International. IEEE, 1993: 2-5.

[11] SAMA M, PELLEGRINI P, D’ARIANO A, et al. Ant colony optimization for the real- time train routing selection problem[J]. Transportation Research Part B, 2016(85): 89-108.

[12] TANG Y L, CAI Y G, YANG Q J. Improved ant colony optimization for multi-depot heterogeneous vehicle routing problem with soft time windows[J]. Journal of Southeast University, 2015, 31(1): 94-99.

[13] CAI W J, WANG C Y, BIN Y U, et al. Improved ant colony algorithm for period vehicle routing problem[J]. Operations Research & Management Science, 2014, 23 (5): 70-77.

[14] DIAS J C, MACHADO P, SILVA D C, et al. An inverted ant colony optimization approach to traffic[J]. Engineering Applications of Artificial Intelligence, 2014, 36(C):122-133.

[15] 杨剑峰. 蚁群算法及其应用研究[D]. 杭州：浙江大学, 2007. [YANG J F. The Application and research on ant colony algorithm[D]. Hangzhou: Zhejiang University, 2007.]

[16] STUTZLE T, HOOS H. Max-min ant system and local search for the traveling salesman problem[C]// Evolutionary Computation, 1997, IEEE International Conference on. IEEE, 1997: 309-314.

[17] GERHARD R. Optimal solutions for symmetric TSPs [OB/OL].(2007-05-2)[2007-05-022] http://comopt.ifi. uni-heidelberg.de/software/TSPLIB95/STSP.html.