计算机科学 ›› 2018, Vol. 45 ›› Issue (11A): 138-142.
李俊, 童钊, 王政
LI Jun, TONG Zhao, WANG Zheng
摘要: 针对基本ACS算法模型求解TSP问题的缺陷,对ACS算法添加2-opt邻域搜索策略,增强算法对TSP问题解的构造能力,提高算法对TSP问题的求解精度。同时,根据ACS算法易于并行化的特点,使用并行化ACS算法与算法参数优化混合方案,提高ACS算法求解TSP问题的速度。最终实现了对中等规模TSP问题具有较好求解性能的并行ACS-2-opt算法。实验结果表明,2-opt策略对于提升ACS算法的求解精度具有明显的效果;采用不同参数设定信息素启发因子时,求解时间具有较大差异;在采用节点距离倒数作为期望启发值时,ACS算法模型呈现退化性;在并行条件下,ACS-2-opt算法处理TSP问题时具有良好的并行性能。
中图分类号:
[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 |
|