关键词: 蚁群算法, 邻域耦合机制, 双边滤波, 基尼不纯度, 旅行商问题（TSP）

Abstract: To overcome the slow convergence and premature stagnation of the ant colony algorithm in solving traveling salesman problem (TSP), a dual ant colony optimization with neighborhood coupling mechanism and bilateral filtering (NBACO) is proposed. Firstly, the ant colony is dynamically divided into soldier ants and commanding ants by the combat power index. The soldier ants are mainly responsible for improving the solution accuracy of the algorithm, and the commander ants are mainly responsible for improving the convergence speed of the algorithm. And these two kinds of ants coordinate together to balance the relationship between the accuracy and convergence speed of the algorithm effectively. Secondly, to increase the choosing possibility of the public path in the algorithm, a neighborhood coupling mechanism is used to disseminate a little pheromone both in the public area and its neighborhood adaptively when the commanding ants visit this area, so that a high convergence speed of the algorithm is achieved, which can increase the probability of ants choosing public area and its neighborhood. Furthermore, while the algorithm falls into a local optimum, a bilateral filtering strategy based on Gini impurity is introduced to dynamically decrease the pheromone of the current optimal path. In this strategy, the pheromone concentration difference between the optimal path and its neighboring paths is reduced, which can greatly help the algorithm get rid of the local optimum and increase the probability of ants choosing other non-optimal paths at the next iteration. Finally, from a large number of TSP instances, the experimental results show that the improved ant colony algorithm can balance the solution accuracy and convergence speed of the algorithm effectively.

Key words: ant colony algorithm, neighborhood coupling mechanism, bilateral filtering, Gini impurity, traveling salesman problem (TSP)