Abstract:

When solving traveling salesman problem (TSP), the ant colony algorithm is easy to fall into local optimum and convergence speed is slow, a double-type ant colony algorithm considering dynamic guidance and neighborhood interaction is proposed. Firstly, the algorithm combines the dynamic guidance strategy to increase the dynamic pheromone belonging to the path of the largest spanning tree in the early iteration, thereby effectively increasing the diversity of the population; adding the dynamic pheromone belonging to the path of the minimum spanning tree in the late iteration to accelerate the convergence speed. Furthermore, the ants are divided into two categories, which are integrated into the neighborhood interaction strategy, and the second type of ants improve the state transition and the local pheromone update formula through the attraction factors, and use the MMAS (max-min ant system) pheromone restriction strategy, which not only improves the convergence, but also prevents the algorithm from early stagnation. The experimental results of solving the TSP test set and compared with other improved ant colony algorithms show that the improved algorithm can effectively accelerate the convergence speed and avoid falling into local optimum, thus obtaining a more accurate solution, especially in the case of large-scale TSP problems, the effect is more significant.

Key words: ant colony algorithm, maximal spanning tree, minimum spanning tree, attraction factor, traveling salesman problem (TSP)

摘要：

针对蚁群算法在求解旅行商问题（TSP）时，易出现陷入局部最优和收敛速度较慢的问题，提出了考虑动态导向与邻域交互的双蚁型算法。首先，结合动态导向策略，在迭代前期增加属于最大生成树路径上的动态信息素，从而有效增加种群多样性；在迭代后期增加属于最小生成树路径上的动态信息素，使其加快收敛速度。进一步，将蚂蚁分为两类，融入邻域交互策略，第二类蚂蚁通过吸引因子改进状态转移和局部信息素更新公式，并运用最大-最小蚂蚁系统（MMAS）信息素限制策略，使其不仅提高了收敛性，又能防止算法过早停滞。求解TSP测试集及与其他改进蚁群算法对比的实验结果表明，改进后的算法既能有效加快收敛速度，又能避免陷入局部最优，从而获得更精确的解，尤其在针对大规模TSP问题时效果更为显著。

关键词: 蚁群算法, 最大生成树, 最小生成树, 吸引因子, 旅行商问题（TSP）