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

Convergence Analysis of the Ant Colony Algorithm for Solving TSP

研究和证明求解旅行商问题(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.