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

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