蚁群算法的收敛速度分析

摘要：

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

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

所属期刊栏目：30

分类号：TP181(自动化基础理论)

资助基金：国家自然科学基金60433020;10471045;60673023;南京大学软件新技术国家重点实验室项目200603;广东省自然科学基金970472;000463;04020079;05011896;吉林省科技发展计划20050705-2

在线出版日期：2007-10-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共10页

页码：1344-1353