摘要
广泛应用于经典NP难问题即旅行商问题(Traveling Salesman Problem,TSP)的蚁群优化(Ant Colony Optimization,ACO)算法存在容易陷入局部最优、收敛速度慢等问题,但其采用正反馈机制并具备较强的鲁棒性,适合与其他算法相融合从而改进优化。基于此,引入人工蜂群的分级思想,提出了一种多级蚁态的蚁群改进(Multistage State Ant Colony Optimization,MSACO)算法。通过引入适应度算子将传统单蚁态蚁群划分为王蚁、被雇佣蚁和非雇佣蚁,并且在每次迭代后重新分配身份以动态维持多级蚁态。王蚁寻找最优路径即最优食物源,被雇佣蚁负责路径构建,非雇佣蚁进行局部优化。为了使非雇佣蚁更有效地获得优质解,提出了一种固定邻域优化算法。实验结果表明,在TSPLIB库的7个数据集中,MSACO均可以达到理论最优解程度,较其他改进算法的最优解迭代次数与运行时间可以减少约40%与50%。
The Ant Colony Optimization(ACO)algorithm,which is widely used in the classical NP-hard problem,i.e.,the Traveling Salesman Problem(TSP),suffers from problems such as easy to fall into local optimum and slow convergence,but its positive feedback mechanism and strong robustness make it suitable for integration with other algorithms to improve optimization.Based on this,a dynamic Multistage Stage Ant Colony Optimization(MSACO)is proposed by introducing the classification idea of artificial bee colony,which divides the traditional single-state ant colony into king ants,employed ants and non-employed ants by introducing the fitness operator,and reassigns the identity after each iteration to dynamically maintain the multistage ant state.The king ants find the optimal path,i.e.,the optimal food source,the employed ants are responsible for path construction,and the non-employed ants perform local optimization.A fixed-neighborhood optimization algorithm is also proposed to enable the non-employed ants to obtain high-quality solutions more efficiently.The experimental results show that MSACO can reach the theoretical optimal solution degree in all seven datasets of TSPLIB library,and the number of iterations of the optimal solution can be reduced by about 40%and 50%compared with other improved algorithms in terms of iteration and running time.
作者
刘书勇
刘峰
LIU Shuyong;LIU Feng(College of Computer Science and Technology,Harbin Engineering University,Harbin 150001,China)
出处
《无线电工程》
2024年第2期463-472,共10页
Radio Engineering
基金
黑龙江省自然科学基金(JJ2019LH2160)。
关键词
人工蜂群
蚁群优化算法
动态多级
适应度算子
固定邻域
artificial bee colony
ant colony optimization algorithm
dynamic multistage
fitness operator
fixed neighborhood
