解TSP问题的蚁群算法及其收敛性分析  

Convergence Analysis of the Ant Colony Algorithm for Solving TSP

作　　者：徐强[1] 宋海洲[1] 田朝薇[1] 

机构地区：[1]华侨大学数学科学学院,福建泉州362021

出　　处：《华侨大学学报（自然科学版）》2011年第5期588-591,共4页Journal of Huaqiao University(Natural Science)

基　　金：福建省自然科学基金资助项目(Z0511028)

摘　　要：研究和证明求解旅行商问题(TSP)的蚁群算法收敛性.针对蚁群算法搜索时间长、收敛速度慢、易陷入局部最优等缺陷,改进Dorigo提出的基本蚁群算法.最后,用典型的旅行商问题CHN144进行仿真实验,结果表明,改进蚁群算法在收敛速度及求解能力上都有较大改善.A detailed theoretical research on ant colony algorithm （ACA） is performed, and the convergence of the ACA for solving the traveling salesman problem （TSP） is proved. ACA has the limitations of stagnation and poor convergence, and is easy to fall in local optima, a series of improvement schemes such as roulette strategy and excellent ants release pheromone strategy are proposed. Finally, a typical example of Traveling salesman problem CHN144 is calculated. It is shown that the improved ACA has a satisfied convergence and search ability.

关 键 词：旅行商问题 蚁群算法 收敛性 信息素 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构] O22[自动化与计算机技术—计算机科学与技术]