AIPUB归智期刊联盟

微信公众号

网站二维码

2025年4月1日 5:37 星期二
首页 > 过刊浏览>2023年第32卷第3期 >1-14. DOI:10.15888/j.cnki.csa.008976
PDF HTML阅读 XML下载 导出引用 引用提醒
蚁群算法在求解旅行商问题中的应用综述
作者:
基金项目:

河北省物联网监控技术创新中心(21567693H); 青海省物联网重点实验室(2017-ZJ-Y21); 中央高校基本科研业务费(3142021009)


Survey on Ant Colony Optimization for Solving Traveling Salesman Problem
Author:
  • 摘要
    • | |
  • 访问统计
    • |
  • 参考文献 [65]
    • |
  • 相似文献 [20]
    • | | |
  • 文章评论
    摘要:

    旅行商问题作为组合优化研究中最具挑战的问题之一, 自被提出以来就引起了学术界的广泛关注并提出了大量的方法来解决它. 蚁群算法是求解复杂组合优化问题的一种启发式仿生进化算法, 是求解旅行商问题的有效手段. 本文分别介绍蚁群算法中几个有代表性的算法, 综述了蚁群算法的改进、融合和应用的文献研究进展, 以评价近年来不同版本的蚁群算法为解决旅行商问题的发展和研究成果, 并针对改进蚁群算法结构框架、算法参数的设置及优化、信息素优化和混合算法等方面, 对现被提出的改进算法进行了分类综述. 对蚁群算法在未来对旅行商问题及其他不同领域的研究内容和研究热点的进一步发展提供了展望和依据.

    Abstract:

    As one of the most challenging problems in combinatorial optimization, the traveling salesman problem has attracted extensive attention from the academic community since its birth, and a large number of methods have been proposed to solve it. The ant colony optimization (ACO) is a heuristic bionic evolutionary algorithm for solving complex combinatorial optimization problems, which is effective in solving the traveling salesman problem. This study introduces several representative ACOs and makes a literature review of the improvement, fusion, and application progress of ACOs to evaluate the development and research achievements of different versions of ACOs in solving the traveling salesman problem in recent years. Moreover, the improved ACOs are summarized in categories in terms of the framework structure, setting and optimization of algorithm parameters, pheromone optimization, and hybrid algorithms. The research provides an outlook and basis for the ACO application to solve the traveling salesman problem and further develop the research content and focuses of other fields.

    参考文献
    [1] Campbell PJ. The traveling salesman problem: A computational study. Mathematics Magazine, 2007, 80(3): 238.
    [2] Beni G. Swarm intelligence. In: Sotomayor M, Pérez-Castrillo D, Castiglione F, eds. Complex Social and Behavioral Systems: Game Theory and Agent-based Models. New York: Springer, 2020. 791–818.
    [3] Razali NM, Geraghty J. Genetic algorithm performance with different selection strategies in solving TSP. Proceedings of the World Congress on Engineering. London: International Association of Engineers, 2011. 1–6.
    [4] Huang L, Wang GC, Bai T, et al. An improved fruit fly optimization algorithm for solving traveling salesman problem. Frontiers of Information Technology & Electronic Engineering, 2017, 18(10): 1525–1533
    [5] Hatamlou A. Solving travelling salesman problem using black hole algorithm. Soft Computing, 2018, 22(24): 8167–8175.
    [6] Laguna M. Tabu search. In: Martí R, Pardalos PM, Resende MGC, eds. Handbook of Heuristics. Cham: Springer, 2018. 741–758.
    [7] Kennedy J, Eberhart R. Particle swarm optimization. Proceedings of 1995 International Conference on Neural Networks. Perth: IEEE, 1995. 1942–1948.
    [8] Dorigo M, Birattari M, Stutzle T. Ant colony optimization. IEEE Computational Intelligence Magazine, 2006, 1(4): 28–39. [doi: 10.1109/MCI.2006.329691
    [9] Goss S, Aron S, Deneubourg JL, et al. Self-organized shortcuts in the Argentine ant. Naturwissenschaften, 1989, 76(12): 579–581. [doi: 10.1007/BF00462870
    [10] Dorigo M, Maniezzo V, Colorni A. Ant system: Optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 1996, 26(1): 29–41. [doi: 10.1109/3477.484436
    [11] Stützle T, Hoos HH. MAX-MIN ant system. Future Generation Computer Systems, 2000, 16(8): 889–914. [doi: 10.1016/S0167-739X(00)00043-1
    [12] Bullnheimer B, Hartl RF, Strauss C. An improved ant system algorithm for the vehicle routing problem. Annals of Operations Research, 1999, 89: 319–328. [doi: 10.1023/A:1018940026670
    [13] Pendharkar PC. An ant colony optimization heuristic for constrained task allocation problem. Journal of Computational Science, 2015, 7: 37–47.
    [14] Escario JB, Jimenez JF, Giron-Sierra JM. Ant colony extended: Experiments on the travelling salesman problem. Expert Systems with Applications, 2015, 42(1): 390–410. [doi: 10.1016/j.eswa.2014.07.054
    [15] Duan P, Yong AI. Research on an improved ant colony optimization algorithm and its application. International Journal of Hybrid Information Technology, 2016, 9(4): 223–234. [doi: 10.14257/ijhit.2016.9.4.20
    [16] Rokbani N, Kumar R, Abraham A, et al. Bi-heuristic ant colony optimization-based approaches for traveling salesman problem. Soft Computing, 2021, 25(5): 3775–3794. [doi: 10.1007/s00500-020-05406-5
    [17] Mavrovouniotis M, Yang SX. Ant colony optimization with immigrants schemes for the dynamic travelling salesman problem with traffic factors. Applied Soft Computing, 2013, 13(10): 4023–4037. [doi: 10.1016/j.asoc.2013.05.022
    [18] Chowdhury S, Marufuzzaman M, Tunc H, et al. A modified ant colony optimization algorithm to solve a dynamic traveling salesman problem: A case study with drones for wildlife surveillance. Journal of Computational Design and Engineering, 2019, 6(3): 368–386. [doi: 10.1016/j.jcde.2018.10.004
    [19] 王原, 陈名, 邢立宁, 等. 用于求解旅行商问题的深度智慧型蚁群优化算法. 计算机研究与发展, 2021, 58(8): 1586–1598. [doi: 10.7544/issn1000-1239.2021.20210320
    [20] Erol AH, Er M, Bulkan S. Optimizing the ant colony optimization algorithm using neural network for the traveling salesman problem. Proceedings of the 2012 International Conference on Industrial Engineering and Operations Management. Istanbul, 2012. 1695–1701.
    [21] Zhang ZJ, Xu ZX, Luan SY, et al. Opposition-based ant colony optimization algorithm for the traveling salesman problem. Mathematics, 2020, 8(10): 1650. [doi: 10.3390/math8101650
    [22] 吴春明, 陈治, 姜明. 蚁群算法中系统初始化及系统参数的研究. 电子学报, 2006, 34(8): 1530–1533. [doi: 10.3321/j.issn:0372-2112.2006.08.035
    [23] Cheong PY, Aggarwal D, Hanne T, et al. Variation of ant colony optimization parameters for solving the travelling salesman problem. Proceedings of the 2017 IEEE 4th International Conference on Soft Computing & Machine Intelligence (ISCMI). Mauritius: IEEE, 2017. 60–65.
    [24] 向永靖. 蚁群算法中参数设置的研究——以TSP为例. 现代信息科技, 2020, 4(22): 95–98, 102. [doi: 10.19850/j.cnki.2096-4706.2020.22.025
    [25] Gan Y, Lan LW, Li S. Study on parameters configuration for ant colony optimization. Advanced Materials Research, 2011, 279: 371–376. [doi: 10.4028/www.scientific.net/AMR.279.371
    [26] Peker M, Şen B, Kumru PY. An efficient solving of the traveling salesman problem: The ant colony system having parameters optimized by the Taguchi method. Turkish Journal of Electrical Engineering and Computer Sciences, 2013, 21(7): 2015–2036
    [27] Blagoveshchenskaya EA, Mikulik II, Strüngmann LH. Ant colony optimization with parameter update using a genetic algorithm for travelling salesman problem. Models and Methods for Researching Information Systems in Transport 2020, 2020, (1): 20–25.
    [28] Wang Y, Han ZP. Ant colony optimization for traveling salesman problem based on parameters optimization. Applied Soft Computing, 2021, 107: 107439. [doi: 10.1016/j.asoc.2021.107439
    [29] Salem A, Sleit A. Analysis of ant colony optimization algorithm solutions for travelling salesman problem. International Journal of Scientific & Engineering Research, 2018, 9(2): 570–575
    [30] Merkle D, Middendorf M, Schmeck H. Ant colony optimization for resource-constrained project scheduling. IEEE Transactions on Evolutionary Computation, 2002, 6(4): 333–346. [doi: 10.1109/TEVC.2002.802450
    [31] 李万庆, 李彦苍. 求解复杂优化问题的基于信息熵的自适应蚁群算法. 数学的实践与认识, 2005, 35(2): 134–139. [doi: 10.3969/j.issn.1000-0984.2005.02.024
    [32] Cai ZQ, Huang H, Qin Y, et al. Ant colony optimization based on adaptive volatility rate of pheromone trail. International Journal of Communications, 2009, 2(8): 792–796
    [33] Anghinolfi D, Boccalatte A, Paolucci M, et al. Performance evaluation of an adaptive ant colony optimization applied to single machine scheduling. Proceedings of the 7th Asia-Pacific Conference on Simulated Evolution and Learning. Melbourne: Springer, 2008. 411–420.
    [34] 乔东平, 裴杰, 李浩, 等. 改进蚁群算法求解TSP问题研究. 机械设计与制造, 2019, (10): 144–149. [doi: 10.3969/j.issn.1001-3997.2019.10.036
    [35] 陈颖杰, 高茂庭. 基于信息素初始分配和动态更新的蚁群算法. 计算机工程与应用, 2022, 58(2): 95–101. [doi: 10.3778/j.issn.1002-8331.2012-0569
    [36] Ning JX, Zhang Q, Zhang CS, et al. A best-path-updating information-guided ant colony optimization algorithm. Information Sciences, 2018, 433–434: 142–162.
    [37] Luo Q, Wang HB, Zheng Y, et al. Research on path planning of mobile robot based on improved ant colony algorithm. Neural Computing and Applications, 2020, 32(6): 1555–1566. [doi: 10.1007/s00521-019-04172-2
    [38] Fei T, Wu XX, Zhang LY, et al. Research on improved ant colony optimization for traveling salesman problem. Mathematical Biosciences and Engineering, 2022, 19(8): 8152–8186. [doi: 10.3934/mbe.2022381
    [39] Gao W. Modified ant colony optimization with improved tour construction and pheromone updating strategies for traveling salesman problem. Soft Computing, 2021, 25(4): 3263–3289. [doi: 10.1007/s00500-020-05376-8
    [40] 顾竞豪, 王晓丹, 贾琪. 求解大规模TSP问题的带导向信息素蚁群算法. 火力与指挥控制, 2018, 43(8): 111–115. [doi: 10.3969/j.issn.1002-0640.2018.08.023
    [41] Ekmekci D. An ant colony optimization memorizing better solutions (ACO-MBS) for traveling salesman problem. Proceedings of the 2019 3rd International Symposium on Multidisciplinary Studies and Innovative Technologies (ISMSIT). Ankara: IEEE, 2019. 1–5.
    [42] Ye K, Zhang CS, Ning JX, et al. Ant-colony algorithm with a strengthened negative-feedback mechanism for constraint-satisfaction problems. Information Sciences, 2017, 406–407: 29–41.
    [43] Li J, Xia Y, Li B, et al. A pseudo-dynamic search ant colony optimization algorithm with improved negative feedback mechanism. Cognitive Systems Research, 2020, 62: 1–9. [doi: 10.1016/j.cogsys.2020.03.001
    [44] 冯振辉, 肖人彬. 基于混合反馈机制的扩展蚁群算法. 控制与决策, 2022, 37(12): 3160–3170.
    [45] 许凯波, 鲁海燕, 程毕芸, 等. 求解TSP的改进信息素二次更新与局部优化蚁群算法. 计算机应用, 2017, 37(6): 1686–1691. [doi: 10.11772/j.issn.1001-9081.2017.06.1686
    [46] Liang BL, Yang ZM, Qin Y, et al. Ant colony algorithm with gradient descent for solving multi-constrained quality of service routing. Journal of Computer Applications, 2017, 37(3): 722–729
    [47] 马学森, 宫帅, 朱建, 等. 动态凸包引导的偏优规划蚁群算法求解TSP问题. 通信学报, 2018, 39(10): 59–71. [doi: 10.11959/j.issn.1000-436x.2018218
    [48] Aydoğan T, Al-Badri R. A hybrid model of max-min ant system with genetic algorithm for improved to travelling salesman problem. International Journal of Engineering and Technology, 2018, 10(3): 254–258. [doi: 10.7763/IJET.2018.V10.1069
    [49] Chen XY, Dai YH. Research on an improved ant colony algorithm fusion with genetic algorithm for route planning. Proceedings of the 2020 4th IEEE Information Technology, Networking, Electronic and Automation Control Conference (ITNEC). Chongqing: IEEE, 2020. 1273–1278.
    [50] 陶丽华, 马振楠, 史朋涛, 等. 基于TSP问题的动态蚁群遗传算法. 机械设计与制造, 2019, (12): 147–149, 154. [doi: 10.3969/j.issn.1001-3997.2019.12.037
    [51] Mahi M, Baykan ÖK, Kodaz H. A new hybrid method based on particle swarm optimization, ant colony optimization and 3-opt algorithms for traveling salesman problem. Applied Soft Computing, 2015, 30: 484–490. [doi: 10.1016/j.asoc.2015.01.068
    [52] Rokbani N, Kromer P, Twir I, et al. A new hybrid gravitational particle swarm optimization-ACO with local search mechanism, PSOGSA-ACO-Ls for TSP. International Journal of Intelligent Engineering Informatics, 2019, 7(4): 384–398. [doi: 10.1504/IJIEI.2019.101565
    [53] Stodola P, Michenka K, Nohel J, et al. Hybrid algorithm based on ant colony optimization and simulated annealing applied to the dynamic traveling salesman problem. Entropy, 2020, 22(8): 884. [doi: 10.3390/e22080884
    [54] Zhang XX, Shen X, Yu ZQ. A novel hybrid ant colony optimization for a multicast routing problem. Algorithms, 2019, 12(1): 18. [doi: 10.3390/a12010018
    [55] Sheng YF. A computational optimization research on ant colony optimization for the traveling salesman problem. Journal of Physics: Conference Series, 2022, 2258: 012006. [doi: 10.1088/1742-6596/2258/1/012006
    [56] 杜力, 徐光辉, 汪繁荣. 自适应萤火虫算法改进蚁群算法的移动机器人路径规划. 河南理工大学学报(自然科学版), 2022, 41(2): 124–130. [doi: 10.16186/j.cnki.1673-9787.2021010073
    [57] 李志锟, 赵倩楠. 融合人工势场蚁群算法的移动机器人路径规划. 电光与控制, 2022, 29(11): 118–124.
    [58] 张烈平, 何佳洁, 于滟琳, 等. 基于蚁群算法优化的布谷鸟搜索算法. 微电子学与计算机, 2018, 35(12): 21–26. [doi: 10.19304/j.cnki.issn1000-7180.2018.12.005
    [59] Nazif H. Solving job shop scheduling problem using an ant colony algorithm. Journal of Asian Scientific Research, 2015, 5(5): 261–268. [doi: 10.18488/journal.2/2015.5.5/2.5.261.268
    [60] Deepalakshmi P, Shankar K. Role and impacts of ant colony optimization in job shop scheduling problems: A detailed analysis. Evolutionary Computation in Scheduling, 2020: 11–35
    [61] 蒋华伟, 郭陶, 杨震. 车辆路径问题研究进展. 电子学报, 2022, 50(2): 480–492. [doi: 10.12263/DZXB.20201154
    [62] 刘紫玉, 赵丽霞, 薛建越, 等. 面向车辆路径问题的改进蚁群算法研究. 河北科技大学学报, 2022, 43(1): 80–89. [doi: 10.7535/hbkd.2022yx01009
    [63] Miao CW, Chen GZ, Yan CL, et al. Path planning optimization of indoor mobile robot based on adaptive ant colony algorithm. Computers & Industrial Engineering, 2021, 156: 107230
    [64] 孔维立, 王峰, 周平华, 等. 改进蚁群算法的无人机三维路径规划. 电光与控制, 1–8. http://kns.cnki.net/kcms/detail/41.1227.tn.20220517.1822.002.html. [2022-09-06].
    [65] 陈超, 张莉. 基于改进蚁群算法的三维路径规划. 计算机工程与应用, 2019, 55(20): 192–196. [doi: 10.3778/j.issn.1002-8331.1904-0212
    引证文献
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

郭城成,田立勤,武文星.蚁群算法在求解旅行商问题中的应用综述.计算机系统应用,2023,32(3):1-14

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2022-07-29
  • 最后修改日期:2022-09-01
  • 在线发布日期: 2022-12-02
文章二维码
友情链接:中国科学院软件研究所中国计算机学会中国科学院国家自然科学基金委员会软件学报
您是第11117816位访问者
版权所有：中国科学院软件研究所 京ICP备05046678号-3
地址：北京海淀区中关村南四街4号 中科院软件园区 7号楼305房间,邮政编码：100190
电话：010-62661041 传真： Email：csa (a) iscas.ac.cn
技术支持：北京勤云科技发展有限公司

京公网安备 11040202500063号