一种进化型蚁群算法及其在TSP问题中的检验

An Evolutional Ant Algorithm and Its Test in TSP Problem

蚁群算法是通过模拟蚂蚁觅食而发展出的一种新的启发算法,其收敛速度一直是人们关心的问题。针对蚁群算法的一些不足,提出基于最小生成树的进化型蚁群算法。它利用了最小生成树与最优路径之间的关系限制了蚂蚁在每一个城市的搜寻范围,进化了寻优策略,节省了在不可能构成最优路径的路段上的计算时间,提高了运算速度,克服了以往蚁群算法的计算时间长、精度低的缺点,使得蚁群算法有了显著的提高。计算机仿真结果表明,该文算法改进了标准蚂蚁群算法的效率和计算结果的质量。

Ant colony algorithm is a new heuristic algorithm inspired by the behaviour of ants＇ searching food. The convergence speed has always been a problem of the ant colony algorithm. Aiming at solving this problem, this paper proposed a kind of evolutional ant colony algorithm based on minimum spanning tree. Utilizing the relationship between the minimum spanning tree and the best route to restrict the searching scope of each ant, the new algorithm improved the searching strategy and consequently saved the computational time on the paths that can not be on the best route. It significantly improved the basic ant colony algorithm by accelerating the convergence speed and improving the precision. The simulation proved that the new algorithm improves beth the efficiency and the quality of results of the standard ant colony algorithm.