计算机科学 ›› 2018, Vol. 45 ›› Issue (11A): 138-142.

• 智能计算 • 上一篇    下一篇

一种并行ACS-2-opt算法处理TSP问题的方法

李俊, 童钊, 王政   

  1. 湖南师范大学数学与计算机科学学院 长沙410006
  • 出版日期:2019-02-26 发布日期:2019-02-26
  • 通讯作者: 童 钊(1985-),男,博士,讲师,CCF会员,主要研究方向为云计算、资源优化,E-mail:tongzhao@hunnu.edu.cn
  • 作者简介:李 俊(1996-),男,主要研究方向为并行处理;童 钊(1985-),男,博士,讲师,CCF会员,主要研究方向为云计算、资源优化,E-mail:tongzhao@hunnu.edu.cn(通信作者);王 政(1996-),男,主要研究方向为并行处理。
  • 基金资助:
    本文受国家自然科学基金项目(61502165),湖南省教育厅一般项目(17C0959),湖南师范大学青年基金项目(11404),湖南师范大学大学生创新性实验项目(201501023)资助。

Approach to Solve TSP with Parallel ACS-2-opt

LI Jun, TONG Zhao, WANG Zheng   

  1. College of Mathematics and Computer Science,Hunan Normal University,Changsha 410006,China
  • Online:2019-02-26 Published:2019-02-26

摘要: 针对基本ACS算法模型求解TSP问题的缺陷,对ACS算法添加2-opt邻域搜索策略,增强算法对TSP问题解的构造能力,提高算法对TSP问题的求解精度。同时,根据ACS算法易于并行化的特点,使用并行化ACS算法与算法参数优化混合方案,提高ACS算法求解TSP问题的速度。最终实现了对中等规模TSP问题具有较好求解性能的并行ACS-2-opt算法。实验结果表明,2-opt策略对于提升ACS算法的求解精度具有明显的效果;采用不同参数设定信息素启发因子时,求解时间具有较大差异;在采用节点距离倒数作为期望启发值时,ACS算法模型呈现退化性;在并行条件下,ACS-2-opt算法处理TSP问题时具有良好的并行性能。

关键词: 2-opt邻域搜索策略, ACS算法, TSP问题, 并行计算

Abstract: According to defects in basic ACS solving TSP,this paper added 2-opt local search strategy to ACS model to improve the computing capacity and accuracy in the process of building the best tour.Moreover,since ACS algorithm is easy to be parallel processed,this paper used multithreaded concurrency and parameter optimization to enhance computing speed of basic ACS.Finally,this paper actualized parallel ACS-2-opt algorithm which has preferable performance in solving the medium TSP.According to the experimental results,2-opt strategy has obvious effect on improving the accuracy of ACS solving TSP.The time cost of ACS solving TSP is distinct with different pheromone heuristic value settings.ACS becomes vestigial when using reciprocal of distance between two nodes as the corresponding heuristic value.Under the circumstance of parallel computation,ACS-2-opt has good parallel computing on solving TSP.

Key words: 2-opt local search strategy, ACS, Parallel computing, TSP

中图分类号: 

  • TP301.6
[1]BEKTAS T.The multiple traveling salesman problem:an overview of formulations and solution procedures [J].Omega,2006,34(3):209-219.
[2]DHAMMPAL R,SANJAY K,PATLE V K.Route optimisation by ant colony optimisationtechnique [J].Procedia Computer Science,2016(92):48-55.
[3]ZHANG Z,YAO Y S,ZHANG J H.Algorithm evolution from traveling salesman problem to vehicle routing problem [J].Applied Mechanics and Materials,2013,411:1872-1875.
[4]SAVURAN H,KARAKAYA M.Efficient route planning for an unmanned air vehicle deployed on a moving carrier [J].Soft Computing,2016,20(7):2905-2920.
[5]GIBSON B,WILKINSON M,KELLY D.Let the pigeon drive the bus:pigeons can plan future routes in a room [J].Animal Cognition,2012,15(3):379-391.
[6]严晨,王直杰.以TSP为代表的组合优化问题研究现状与展望 [J].计算机仿真,2007,24(6):171-174.
[7]HOLLAND J H.Adaption in natural and artificial system[J].Ann Arbor,1975,6(2):126-137.
[8]SHABANPOUR M,YADOLLHI M,HASANI M M.A new method to solve the multi traveling salesman problem with the combination of genetic algorithm and clustering technique[J].International Journal of Computer Science and Network Security,2017,17(5):221-230.
[9]AVSAR B,ALIABADI D E.Parallelized neural network system for solvinge uclidean traveling salesman problem [J].Applied Soft Computing,2015,34(1):862-873.
[10]BALI O,ELLOUMI W,ABRAHAM A,et al.GPU PSO and ACO applied to TSP for vehicle security tracking [J].Journal of Information Assurance and Security,2016,11(6):369-384.
[11]EZUGWU A E S,ADEWUMI A O,FRINCU M E.Simulated annealing based symbiotic organisms search optimization algorithm for traveling salesman problem [J].Expert Systems with Applications,2017,77:189-210.
[12]DORIGO M.Ant Colony Optimization [M].Cambridge:MIT Press,2004.
[13]COLORNI A,DORIGO M,MAFFIOLI F.Heuristics from nature for hard combinatorial optimization problems [J].International Transactions in Operational Research,1996,3(1):1-21.
[14]DORIGO M,GAMBARDELLA L M.Ant colony system:A cooperative learning approach to the traveling salesman problem [J].IEEE Trans. on Evolutionary Computation,1997,1(1):53- 66.
[15]BAI J,YANG G K,CHEN Y W,et al.A model induced max-min ant colony optimization for asymmetric traveling salesman problem [J].Applied Soft Computing,2013,13(3):1365-1375.
[16]DORIGO M,MANIEZZO V,COLORNI A.The ant system:optimization by a colony of cooperating agents [J].IEEE Transactions on Systems,Man,and Cybernettics-Part B,1996,26(1):1-13.
[17]CROES G A.A menthod for solving traveling salesman prob-lems [J].Operations Research,1958,6(6):791-812.
[18]TONG Z,XIAO Z,LI K,et al.Proactive scheduling in distributed computing-A reinforcement learning approach[J].Journal of Parallel and Distributed Computing,2014,74(7):2662-2672.
[19]AlEXANDER L S,LI L H,ERIC W,et al.Pac model-free reinforcement learning [C]∥Proceeding of International Conference on Machine Learning.2006:881-888.
[20]CARLOS R,CSABA S.Q-learning combined with spreading: convergence and results [C]∥Proceedings of the ISRF-IEE International Conference:Intelligent and Cognitive Systems (Neural Networks Symposium).1996:32-36.
[21]黄瀚,郝志峰,吴国春,等.蚁群算法的收敛速度分析 [J].计算机学报,2007,30(8):1344-1353.
[22]REINELT G.TSPLIB-A traveling salesman problem library[J].ORSA Journal on Computing,1991,3(4):376-384.
[1] 陈鑫, 李芳, 丁海昕, 孙唯哲, 刘鑫, 陈德训, 叶跃进, 何香.
面向国产异构众核架构的CFD非结构网格计算并行优化方法
Parallel Optimization Method of Unstructured-grid Computing in CFD for DomesticHeterogeneous Many-core Architecture
计算机科学, 2022, 49(6): 99-107. https://doi.org/10.11896/jsjkx.210400157
[2] 傅天豪, 田鸿运, 金煜阳, 杨章, 翟季冬, 武林平, 徐小文.
一种面向构件化并行应用程序的性能骨架分析方法
Performance Skeleton Analysis Method Towards Component-based Parallel Applications
计算机科学, 2021, 48(6): 1-9. https://doi.org/10.11896/jsjkx.201200115
[3] 何亚茹, 庞建民, 徐金龙, 朱雨, 陶小涵.
基于神威平台的Floyd并行算法的实现和优化
Implementation and Optimization of Floyd Parallel Algorithm Based on Sunway Platform
计算机科学, 2021, 48(6): 34-40. https://doi.org/10.11896/jsjkx.201100051
[4] 冯凯, 马鑫玉.
(n,k)-冒泡排序网络的子网络可靠性
Subnetwork Reliability of (n,k)-bubble-sort Networks
计算机科学, 2021, 48(4): 43-48. https://doi.org/10.11896/jsjkx.201100139
[5] 胡蓉, 阳王东, 王昊天, 罗辉章, 李肯立.
基于GPU加速的并行WMD算法
Parallel WMD Algorithm Based on GPU Acceleration
计算机科学, 2021, 48(12): 24-28. https://doi.org/10.11896/jsjkx.210600213
[6] 马梦宇, 吴烨, 陈荦, 伍江江, 李军, 景宁.
显示导向型的大规模地理矢量实时可视化技术
Display-oriented Data Visualization Technique for Large-scale Geographic Vector Data
计算机科学, 2020, 47(9): 117-122. https://doi.org/10.11896/jsjkx.190800121
[7] 陈国良, 张玉杰.
并行计算学科发展历程
Development of Parallel Computing Subject
计算机科学, 2020, 47(8): 1-4. https://doi.org/10.11896/jsjkx.200600027
[8] 阳王东, 王昊天, 张宇峰, 林圣乐, 蔡沁耘.
异构混合并行计算综述
Survey of Heterogeneous Hybrid Parallel Computing
计算机科学, 2020, 47(8): 5-16. https://doi.org/10.11896/jsjkx.200600045
[9] 冯凯, 李婧.
k元n方体的子网络可靠性研究
Study on Subnetwork Reliability of k-ary n-cubes
计算机科学, 2020, 47(7): 31-36. https://doi.org/10.11896/jsjkx.190700170
[10] 杨宗霖, 李天瑞, 刘胜久, 殷成凤, 贾真, 珠杰.
基于Spark Streaming的流式并行文本校对
Streaming Parallel Text Proofreading Based on Spark Streaming
计算机科学, 2020, 47(4): 36-41. https://doi.org/10.11896/jsjkx.190300070
[11] 邓定胜.
一种改进的DBSCAN算法在Spark平台上的应用
Application of Improved DBSCAN Algorithm on Spark Platform
计算机科学, 2020, 47(11A): 425-429. https://doi.org/10.11896/jsjkx.190700071
[12] 徐传福,王曦,刘舒,陈世钊,林玉.
基于Python的大规模高性能LBM多相流模拟
Large-scale High-performance Lattice Boltzmann Multi-phase Flow Simulations Based on Python
计算机科学, 2020, 47(1): 17-23. https://doi.org/10.11896/jsjkx.190500009
[13] 徐磊, 陈荣亮, 蔡小川.
基于非结构化网格的高可扩展并行有限体积格子
Scalable Parallel Finite Volume Lattice Boltzmann Method Based on Unstructured Grid
计算机科学, 2019, 46(8): 84-88. https://doi.org/10.11896/j.issn.1002-137X.2019.08.013
[14] 舒娜,刘波,林伟伟,李鹏飞.
分布式机器学习平台与算法综述
Survey of Distributed Machine Learning Platforms and Algorithms
计算机科学, 2019, 46(3): 9-18. https://doi.org/10.11896/j.issn.1002-137X.2019.03.002
[15] 李炎, 马俊明, 安博, 曹东刚.
一个基于Web的轻量级大数据处理与可视化工具
Web Based Lightweight Tool for Big Data Processing and Visualization
计算机科学, 2018, 45(9): 60-64. https://doi.org/10.11896/j.issn.1002-137X.2018.09.008
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!