求解TSP问题的自适应模拟退火蚁群算法

ADAPTIVE SIMULATED ANNEALING ANT COLONY ALGORITHM FOR SOLVING TSP PROBLEM

针对蚁群算法易陷入局部最优,收敛速度较慢的问题,在最大-最小蚁群算法的基础上,提出一种自适应模拟退火蚁群算法。在高温阶段以一定概率接受次优解,优化每次迭代后的路径,增加算法的全局搜索能力,并采用一种自适应的信息素更新策略,前期增加算法的全局搜索能力,后期加快算法的收敛速度;在低温阶段通过降温系数的取值,加快算法收敛速度,在温度机制上采用了回火机制,避免局部最优,使解的质量得到了提高。同时在算法中结合了3opt进一步优化了算法解的质量。实验结果表明该算法的收敛速度以及求解质量得到了一定程度的改善,较好地平衡了种群多样性以及收敛速度的关系。

Aiming at the problem that the ant colony algorithm is easy to fall into the local optimum and the convergence speed is slow,an adaptive simulated annealing ant colony algorithm was proposed based on the maximumminimum ant colony algorithm. The algorithm accepted the difference solution with a certain probability at a high temperature. The path was optimized after each iteration. The global search ability of the algorithm was increased,and an adaptive pheromone updating strategy was adopted. The global search ability of the algorithm was increased in the early stage and accelerated the convergence speed of the algorithm in the later stage. In the low temperature stage,the speed of the algorithm was accelerated by the value of the temperature coefficient,and then the tempering mechanism was adopted to avoid the local optimum. The quality of the solution was improved. At the same time,the 3 opt algorithm was used to further optimize the quality of the algorithm. The experimental results showed that the convergence speed and the solution quality of the proposed algorithm had been improved to a certain extent,and it could balance the relationship between population diversity and convergence rate.