期刊文献+

改进蚁群算法求解最短路径问题 被引量:35

Solving shortest path problem with modified ant colony algorithm
下载PDF
导出
摘要 针对蚁群算法在求解最短路径问题时存在容易陷入局部最优解的问题,对经典蚁群算法提出三方面改进。首先,在初始化信息素浓度时加入方向引导,加快初始搜索速度;其次,在局部信息素浓度更新过程中采用信息素重分配思想,避免由路径信息素衰减过程导致的最优路径信息素浓度过分减少;最后,在全局信息素更新过程中引入动态因子,使其自适应地更新较优路径信息素浓度,以提高全局搜索能力。仿真实验结果表明,该改进算法可以保证收敛速度,并提高算法搜索到最优路径的几率。 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.
出处 《计算机工程与应用》 CSCD 北大核心 2016年第6期8-12,共5页 Computer Engineering and Applications
关键词 蚁群算法 最短路径 方向引导 信息素 ant colony algorithm shortest path direction guiding pheromone
  • 相关文献

参考文献12

  • 1唐晋韬,王挺,王戟.适合复杂网络分析的最短路径近似算法[J].软件学报,2011,22(10):2279-2290. 被引量:43
  • 2Colorni A,Dorigo M,Maniezzo V.Distributed optimization by ant colonies[C]//Proceedings of the First European Conference on Artificial Life,1991:134-142.
  • 3Dorigo M,Gambardella L M.Ant colony system:a cooperative learning approach to the traveling salesman problem[J].IEEE Transactions on Evolutionary Computation,1997,1(1):53-66.
  • 4Gambardella L M,Dorigo M.Ant-Q:a reinforcement learning approach to the traveling salesman problem[C]//Proceedings of the Twelfth International Conference on Machine Learning,1995:252-260.
  • 5Dorigo M,Gambardella.Solving symmetric and asymmetric TSPs by colonies[C]//Proceedings of the IEEE Conference on Evolutionary Computation,1996:622-627.
  • 6Stutzle,Hoes.MAX-MIN ant system[J].Future Generation Computer System Journal,2000,16(8):889-914.
  • 7毕军,付梦印,张宇河.一种改进的蚁群算法求解最短路径问题[J].计算机工程与应用,2003,39(3):107-109. 被引量:45
  • 8郑卫国,田其冲,张磊.基于信息素强度的改进蚁群算法[J].计算机仿真,2010,27(7):191-193. 被引量:18
  • 9Zakzouk A A A,Zaher H M,El-Deen R A Z.An ant colony optimization approach for solving shortest path problem with fuzzy constraints[C]//2010 The 7th International Conference on Informatics and Systems(INFOS),2010:1-8.
  • 10吴虎发,李学俊,章玉龙.改进的蚁群算法求解最短路径问题[J].计算机仿真,2012,29(8):215-218. 被引量:8

二级参考文献27

  • 1徐野,赵海,苏威积,张文波,张昕.Internet网络的访问直径分析[J].计算机学报,2006,29(5):690-698. 被引量:7
  • 2付宇,肖健梅.动态自适应蚁群算法求解TSP问题[J].计算机辅助工程,2006,15(4):10-13. 被引量:5
  • 3COLORM A,DORIGO M,MINIEZZO V.Distributed optimization by ant colonies[C].Proceeding of the First European Conference on Artificial Life.Paris France:Elsevier Publishing, 1991 : 134-142.
  • 4DORIGO M,GAMBARDELLA L M.Ant colony system: a cooperative learning approach to the traveling salesman problem [J].IEEE Transactions on Evolutionary Computation,1997,1(1): 53-66.
  • 5ZHONGZHEN YANG,BIN YU,CHUNTIAN CHENG. A parallel ant colony algorithm for bus network optimization[J]. Computer-Aid Civil and Infrastructure Engineering, 2007,22(1): 44-55.
  • 6ATTIRATANASUNTHRON NATTAPAT, FAKCHAROENPHOL JITTAT.A running time analysis of an ant colony optimization algorithm for shortest paths in directed acyclic graphs[J].Information Processing Letters,2008,105(3):88-92.
  • 7Wang Ying,Xie Jian-ying.Ant colony optimization for multicast routing[C].Proceedings of the IEEE Asia-Pacific Conference on Circuits and Systems,Piscataway (NJ,USA):IEEE,2000.54-57.
  • 8T Stutzle,H Hoos.MAX-MIN Ant System and Local Search for the Traveling Salesman Problem.Proc[C].IEEE International Conference on Evolutionary Computation,1997-04:309-314.
  • 9S Thomas,H H Holger.Max-Min ant system[J].Future Generation Computer Systems,2000,16(8):889-2914.
  • 10M Dorigo,L M Gambardella.Ant colony system:A cooperative learning approach to the traveling salesman problem[J].IEEE Transactions on Evolutionary Computation,1997,1(1):53-66.

共引文献120

同被引文献313

引证文献35

二级引证文献229

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部