融合猫群算法的动态分组蚁群算法  

Dynamic Grouping Ant Colony Algorithm Combined with Cat Swarm Optimization

作　　者：张德惠 游晓明[1] 刘升[2] ZHANG Dehui;YOU Xiaoming;LIU Sheng(School of Electronic and Electrical Engineering,Shanghai University of Engineering Science,Shanghai 201620,China;School of Management,Shanghai University of Engineering Science,Shanghai 201620,China)

机构地区：[1]上海工程技术大学电子电气学院,上海201620 [2]上海工程技术大学管理学院,上海201620

出　　处：《计算机科学与探索》2020年第5期880-891,共12页Journal of Frontiers of Computer Science and Technology

基　　金：国家自然科学基金Nos.61673258,61075115。

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

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

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]