求解TSP问题的改进蚁群算法

An improvement of the ant colony algorithm for solving TSP problems

分析了标准蚁群算法易于出现早熟停滞现象的主要原因,在原有算法基础上引入局部信息激素、最优最差路径信息激素更新策略及变参数策略,扩大了解的搜索空间,有效抑制了收敛过程中的早熟停滞现象,大大提高了算法收敛速度;同时引入局部最优搜索策略,增大了解突变的机率,求解质量得到了极大的改善.对于典型旅行商问题库中旅行商问题的实验及与标准蚁群算法的比较实验验证了该方法的有效性.

As a novel bionic evolutionary algorithm, the ant colony algorithm has been widely applicable to many complicated combinatorial optimization problems. However, the standard any colony algorithm often gets stock into premature stagnation after the iteration process. In this paper, through an analysis of the main reason of the premature stagnation phenomenon in the standard ant colony algorithm, we present a modified version of the algorithm by introducing the local pheromone, modifying the pheromones of the best route and the worst route, as well as making the parameter of the algorithm to be variant during its iteration and searching with a local optimization strategy. Experimental results for solving TSP problems with both the standard ant colony algorithm and the proposed one show that averagely speaking, the proposed method is much better in both the quality of the solution and the speed of convergence compared with the Standard any colony algorithm.