蚁群算法的收敛速度分析

被引：72

作者：

黄翰 ^{[1
]}

郝志峰 ^{[1
]}

吴春国 ^{[2
]}

秦勇 ^{[3
]}

机构：

[1] 华南理工大学计算机科学与工程学院

[2] 吉林大学计算机科学与技术学院符号计算与知识工程教育部重点实验室

[3] 茂名学院信息与网络中心

来源：

计算机学报 | 2007年 / 08期

基金：

广东省自然科学基金;

关键词：

蚁群算法; 吸收态Markov过程; 期望收敛时间; ACO-难易问题; 优化路径;

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

摘要：

蚁群算法(ACO)作为一类新型的机器学习技术,已经广泛用于组合优化问题的求解,同时也应用于工业工程的优化设计.相对于遗传算法(GA),蚁群算法的理论研究在国内外均起步较晚,特别是收敛速度的分析理论是该领域急待解决的第一大公开问题.文中的研究内容主要是针对这一公开问题而开展的.根据蚁群算法的特性,该研究基于吸收态Markov过程的数学模型,提出了蚁群算法的收敛速度分析理论.作者给出了估算蚁群算法期望收敛时间的几个理论方法,以分析蚁群算法的收敛速度,并结合著名的ACS算法作了具体的案例研究.基于该文提出的收敛速度分析理论,作者还提出ACO-难和ACO-易两类问题的界定方法;最后,利用ACS算法求解TSP问题的实验数据,验证了文中提出的分析结论,得出了初步的算法设计指导原则.

引用

页码：1344 / 1353

页数：10