蚁群系统（ACS）及其收敛性证明

计算机工程与应用 ›› 2007, Vol. 43 ›› Issue (5): 67-70.

蚁群系统（ACS）及其收敛性证明

赵霞田恩刚

南京师范大学

收稿日期:2006-03-16 修回日期:1900-01-01 出版日期:2007-02-11 发布日期:2007-02-11
通讯作者: 赵霞

Ant Colony System and Its Convergence

Xia Zhao

Received:2006-03-16 Revised:1900-01-01 Online:2007-02-11 Published:2007-02-11
Contact: Xia Zhao

摘要/Abstract

摘要： 蚁群系统（ACS）是解决旅行商问题（TSP）的最好方法之一，它是在蚂蚁系统的基础上作了许多改进之后得到的一种优化算法。这些改进在一定程度上避免了过早停滞现象的发生，是一种较好的协作式搜索算法。通过与蚂蚁系统的比较，本文系统的介绍了蚁群系统（ACS）所做出的种种改进，并且在理论上证明了该算法的收敛性。

关键词: 收敛性, 信息素, 蚁群优化算法, 蚁群系统

Abstract: Ant Colony System is one of the best approaches in resolving the Traveling Salesman Problem. It makes many improvements based on Ant System, and these improvements can avoid the premature convergence in a way. And Ant Colony System is also a good cooperating searching algorithm. Compared with the Ant System, this paper introduced Ant Colony System systemically and proved its convergence theoretically.

Key words: convergence, pheromone, Ant Colony Optimization Algorithm, Ant Colony System

赵霞田恩刚. 蚁群系统（ACS）及其收敛性证明[J]. 计算机工程与应用, 2007, 43(5): 67-70.

Xia Zhao. Ant Colony System and Its Convergence[J]. Computer Engineering and Applications, 2007, 43(5): 67-70.

[1]	刘双双, 黄宜庆. 多策略蚁群算法在机器人路径规划中的应用[J]. 计算机工程与应用, 2022, 58(6): 278-286.
[2]	陈颖杰, 高茂庭. 基于信息素初始分配和动态更新的蚁群算法[J]. 计算机工程与应用, 2022, 58(2): 95-101.
[3]	张松灿，普杰信，司彦娜，孙力帆. 基于种群相似度的自适应改进蚁群算法及应用[J]. 计算机工程与应用, 2021, 57(8): 70-77.
[4]	陈雷，尹钧圣. 高斯差分变异和对数惯性权重优化的鲸群算法[J]. 计算机工程与应用, 2021, 57(2): 77-90.
[5]	张铭，邓文瀚，林娟，钟一文. 改进蚁群优化算法求解折扣{0-1}背包问题[J]. 计算机工程与应用, 2021, 57(13): 85-95.
[6]	张松灿，普杰信，司彦娜，孙力帆. 蚁群算法在移动机器人路径规划中的应用综述[J]. 计算机工程与应用, 2020, 56(8): 10-19.
[7]	张海南，游晓明，刘升，刘中强. 交互式学习的布谷鸟搜索算法[J]. 计算机工程与应用, 2020, 56(7): 147-154.
[8]	张晓莉，杨亚新，谢永成. 改进的蚁群算法在机器人路径规划上的应用[J]. 计算机工程与应用, 2020, 56(2): 29-34.
[9]	马倩茹，冶继民. FastICA算法的收敛性与一致性分析[J]. 计算机工程与应用, 2020, 56(2): 35-41.
[10]	魏江，王建军，王健，秦春霞，梅少辉. 基于改进蚁群算法的三维航迹规划[J]. 计算机工程与应用, 2020, 56(17): 217-223.
[11]	李顺东，游晓明，刘升. 结合ABC算法动态分级的双蚁态蚁群算法[J]. 计算机工程与应用, 2020, 56(12): 37-46.
[12]	闫旭，叶春明. 混合蝗虫优化算法求解作业车间调度问题[J]. 计算机工程与应用, 2019, 55(6): 257-264.
[13]	李理，李鸿，单宁波. 多启发因素改进蚁群算法的路径规划[J]. 计算机工程与应用, 2019, 55(5): 219-225.
[14]	薛文艳，赵江，郝崇清，刘慧贤. 基于信息素负反馈的超启发式蚁群优化算法[J]. 计算机工程与应用, 2019, 55(4): 163-172.
[15]	刘明霞1，游晓明1，刘升2. 基于聚度的自适应动态混沌蚁群算法[J]. 计算机工程与应用, 2019, 55(3): 15-22.