改进蚁群算法求解最短路径问题

Solving shortest path problem with modified ant colony algorithm

针对蚁群算法在求解最短路径问题时存在容易陷入局部最优解的问题,对经典蚁群算法提出三方面改进。首先,在初始化信息素浓度时加入方向引导,加快初始搜索速度;其次,在局部信息素浓度更新过程中采用信息素重分配思想,避免由路径信息素衰减过程导致的最优路径信息素浓度过分减少;最后,在全局信息素更新过程中引入动态因子,使其自适应地更新较优路径信息素浓度,以提高全局搜索能力。仿真实验结果表明,该改进算法可以保证收敛速度,并提高算法搜索到最优路径的几率。

To solve the problem that the ant colony algorithm is easy to fall into local optimal solutions in solving the shortest path problem, improvements on the classical ant colony algorithm are provided in three aspects. Firstly, direction guiding is utilized in the initial pheromone concentration to speed up the initial convergence; secondly, the idea of pheromone redistribution is added to the pheromone partial renewal process in order to prevent the optimal path pheromone concentration from being over-damped by the path pheromone decay process; finally, a dynamic factor is invited to the global renewal process to adaptively update the pheromone concentration on the optimal path. In this way the global searching ability is improved. The results of the simulation experiment show that this modified algorithm can greatly increase the probability of finding the optimal path while guaranteeing the convergence speed.