北京航空航天大学学报 ›› 2009, Vol. 35 ›› Issue (10): 1245-1248.

• 论文 • 上一篇    下一篇

改进蚁群算法求解时变网络中最短路径问题

刘永强, 常 青, 熊华钢   

  1. 北京航空航天大学 电子信息工程学院, 北京 100191
  • 收稿日期:2008-10-15 出版日期:2009-10-31 发布日期:2010-09-16
  • 作者简介:刘永强(1978-),男,辽宁本溪人,博士生,yongqiangliu@sina.com.
  • 基金资助:

    国家自然科学基金资助项目(60879024, 60872062)

Improved ant colony algorithm for shortest path problem in time-dependent networks

Liu Yongqiang, Chang Qing, Xiong Huagang   

  1. School of Electronics and Information Engineering, Beijing University of Aeronautics and Astronautics, Beijing 100191, China
  • Received:2008-10-15 Online:2009-10-31 Published:2010-09-16

摘要: 给出一种时变网络中蚁群算法的信息素更新策略,使边上残留信息素能够正确反映时变网络中边上权值的变化情况;改进了传统蚁群算法的相邻节点选择策略,使蚂蚁只需计算与当前节点存在直接路径的节点的转移概率,降低算法的计算量;将蚁群算法和遗传算法结合,将蚁群算法每次遍历后形成的解作为初始群种进行单点交叉计算,避免陷入局部最优解,提高算法收敛速度.仿真结果表明,改进的蚁群算法能够有效求解时变网络中最短路径问题,比传统蚁群算法得到全局最优解的概率更大,算法的收敛速度更高.

Abstract: An improved pheromone update strategy suitable for time-dependent networks was proposed. Under this strategy, the residual pheromone of each road can accurately reflect the change of weighted value of each road. An improved selection strategy between adjacent cities was used to compute the cities- transfer probabilities, as a result, the calculation of algorithm was greatly reduced, and the compute speed was greatly increased. To avoid the algorithm converging to the local optimal result, the ant colony algorithm was combined with genetic algorithm. In this way, the solutions after each traversal were used as the initial species to carry out single-point crossover. An improved ant colony algorithm for the shortest path problem in time-dependent networks based on these improved strategies was presented. The results of experiment show that the improved algorithm has greater probability to get the global optimal solution, and the convergence rate of algorithm is better than traditional ant colony algorithm.

中图分类号: 


版权所有 © 《北京航空航天大学学报》编辑部
通讯地址:北京市海淀区学院路37号 北京航空航天大学学报编辑部 邮编:100191 E-mail:jbuaa@buaa.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发