计算机工程与应用 ›› 2022, Vol. 58 ›› Issue (2): 95-101.DOI: 10.3778/j.issn.1002-8331.2012-0569

• 理论与研发 • 上一篇    下一篇

基于信息素初始分配和动态更新的蚁群算法

陈颖杰,高茂庭   

  1. 上海海事大学 信息工程学院,上海 201306
  • 出版日期:2022-01-15 发布日期:2022-01-18

Pheromone Initialization and Dynamic Update Based Ant Colony Algorithm

CHEN Yingjie, GAO Maoting   

  1. College of Information Engineering, Shanghai Maritime University, Shanghai 201306, China
  • Online:2022-01-15 Published:2022-01-18

摘要: 针对蚁群算法搜索初期收敛速度慢和容易陷入局部最优的问题,对蚁群算法进行改进。在初始化阶段,采用贪心策略构造次优路径并增加该路径上的信息素浓度,实现不同路径上信息素的初始分配,使信息素在搜索初期就能发挥指导性作用,让蚂蚁更快地趋向于最优解的附近;在迭代寻优过程中,引入遗传变异操作,对每次迭代后的最优路径作变异操作,尝试寻找一条更优的路径,并用找到的更优路径自适应调整信息素增量;当算法不可避免地陷入局部最优时,运用信息素回滚策略,根据回滚次数动态调整挥发因子,加强搜索能力,使算法更容易跳出局部最优。仿真实验结果表明,改进算法能有效地加快收敛速度和增强跳出局部最优的能力。

关键词: 蚁群算法, 信息素初始化, 信息素增量, 挥发因子, 旅行商问题

Abstract: Aiming at the problems of slow convergence speed and easy to fall into local optimum in the early stage of ant colony algorithm, ant colony algorithm is improved. In the initialization stage, the suboptimal path is constructed by the greedy strategy and the pheromone on it is increased to realize the initial distribution of pheromones on different paths, so that pheromones can play a guiding role in the early stage of search and make ants tend to the optimal solution faster. In the process of iterative optimization, genetic mutation operation is introduced to mutate the optimal path after each iteration and try to find a better path to adjust the pheromone increment adaptively. While the algorithm inevitably falls into local optimization, pheromone rollback strategy is executed to adjust the volatilization factor dynamically according to the number of rollback to enhance the search ability and make the algorithm easier to jump out of local optimum. The simulation experiments show that the improved algorithm can accelerate the convergence speed and enhance the ability to jump out of the local optimum effectively.

Key words: ant colony algorithm, pheromone initialization, pheromone increment, pheromone volatilization, traveling salesman problem