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)

摘要： 针对蚁群算法在求解旅行商问题（TSP）中收敛速度慢且易陷入局部最优等问题，提出一种结合邻域耦合机制与双边滤波的双蚁群算法（NBACO）。首先，算法通过战斗力指数将蚁群动态分成士兵蚁与指挥蚁，士兵蚁主要负责提高算法的求解精度，指挥蚁主要负责提高算法的收敛速度，两类蚂蚁分工合作从而有效平衡算法的求解精度与收敛速度。其次，采用邻域耦合机制，当指挥蚁经过公共区间时，在公共区间及其邻域动态散布微量的信息素，以增大对蚂蚁的吸引力，增加蚂蚁选择公共区间及其邻域的概率，从而提高算法的收敛速度。进一步，当算法陷入局部最优时，引入基于基尼不纯度的双边滤波策略，动态削弱当前最优路径上的信息素浓度，进而缩小最优路径与其邻域路径的信息素浓度差，在下一次迭代时增大蚂蚁选择其他非最优路径的概率，从而帮助算法摆脱局部最优。最后，对大量TSP实例进行仿真，实验结果表明改进后的蚁群算法有效平衡了算法求解精度和收敛速度。

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