Abstract: An improved heuristic ant colony algorithm has been proposed in this paper to solve the TSP problem in Ant Colony System（ACS）, which can easily be trapped in local optimization and low convergence rate. Firstly, the threshold value of pseudo random factor is given in the early stage of iteration, so that ants can select roulette method to complete the solution construction with a high probability, and expand the range of searching for solution. At the same time, the iterative optimal ant is introduced to update the global pheromone to further increase the diversity of solution, so that the algorithm can avoid involving local extremum. Secondly, as the variation range of pseudo-random factor parameter is accelerated in the late iteration, the optimal ant is used to replace the iterative optimal ant so as to accelerate the search process to converge to the optimal solution quickly and accelerate the convergence speed. At last, the experimental results indicate that the improved algorithm can effectively skip the local optimum in the early stage, and can obviously improve the convergence speed in the later stage.

Key words: ant colony system, heuristic ant colony algorithm, global pheromone updates, iterative optimal ant, optimal ant so far

摘要： 针对蚁群系统（ACS）在解决TSP问题上存在易陷入局部最优和收敛速度较慢的问题，提出了一种改进的启发式蚁群算法。在迭代前期赋予伪随机因子较小的阈值，从而使蚂蚁能以较大的概率选择轮盘赌方式完成解的构建，扩大了解的搜索范围；同时通过引入迭代最优蚂蚁进行全局信息素更新，来进一步增加了解的多样性，使算法避免陷入局部最优。在迭代后期随着伪随机因子参数值变化幅度的加快，则用至今最优蚂蚁来取代迭代最优蚂蚁，以促进搜索进程很快的向最优解附近收敛，加快了收敛的速度。实验仿真结果表明改进后的算法在前期能够有效地跳出局部最优，并且在后期能够明显提升收敛速度。

关键词: 蚁群系统, 启发式蚁群算法, 全局信息素更新, 迭代最优蚂蚁, 至今最优蚂蚁