Abstract:

Aiming at the problems that the ant colony algorithm is easy to fall into local optimum and the convergence speed is slow in traveling salesman problem (TSP), dynamic grouping ant colony algorithm combined with cat swarm optimization is proposed. Firstly, the ants are distributed manually in different cities evenly when the population is initialized. Secondly, based on the division of labor in the cat swarm optimization, a dynamic grouping mechanism is introduced into the ant colony system to classify the ants into two types: search ants and tracking ants. Search ants increase the algorithm??s diversity in the early stage by improving the path construction rules, tracking ants use pheromone diffusion mechanism to adaptively update local pheromone to highlight the role of superior sub-paths, and avoid the algorithm falling into local optimum. Finally, the convergence speed is accelerated by the pheromone global update mechanism. Simulation experiments are carried out on multiple sets of instances in TSPLIB through Matlab. The simulation results show that the improved algorithm balances the diversity and conver-gence speed, and effectively imporves the quality of the solutions.

Key words: ant colony optimization (ACO), cat swarm optimization (CSO), traveling salesman problem (TSP), dynamic grouping, adaptive pheromone diffusion

摘要：

针对传统蚁群算法在旅行商问题（TSP）中容易陷入局部最优且收敛速度慢等问题，提出了一种融合猫群算法的动态分组蚁群算法。首先，在种群初始化时，人工地使蚂蚁均匀分布在不同的城市。其次，借鉴猫群算法中的分工思想，在蚁群系统中引入动态分组机制，将蚂蚁分为搜索蚂蚁和跟踪蚂蚁两类：搜索蚂蚁通过路径构建规则的改善使算法在前期多样性增加；跟踪蚂蚁利用信息素扩散机制对局部信息素进行自适应更新，突出较优子路径的作用，避免算法陷入局部最优。最后，通过信息素全局更新机制加快收敛速度。通过Matlab对TSPLIB中的多组案例进行仿真实验，结果表明改进后的算法平衡了多样性和收敛速度，有效提高了解的质量。

关键词: 蚁群算法（ACO）, 猫群算法（CSO）, 旅行商问题（TSP）, 动态分组, 自适应信息素扩散