文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > 计算机软件及应用 > Dijkstra最短路径算法优化策略
侵权投诉

Dijkstra最短路径算法优化策略

数模相关方法

2009年10月 

第35卷第10期北京航空航天大学学报

JournalofBeijingUniversityofAeronauticsandAstronauticsOctober 2009Vol.35 No110

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

刘永强

常 青

熊华钢

(北京航空航天大学电子信息工程学院,北京100191)

  摘   要:给出一种时变网络中蚁群算法的信息素更新策略,使边上残留信息素能够

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

关 键 词:时变网络;最短路径;蚁群算法中图分类号:TP301.6文献标识码:A    文章编号:100125965(2009)1021245204

Improvedantcolonyalpathproblem

enetworks

iuChangQing

XiongHuagang

(SchoolofandIonEngineering,BeijingUniversityofAeronauticsandAstronautics,Beijing100191,China)

Abstract:iprovedpheromoneupdatestrategysuitablefortime2dependentnetworkswasproposed.Underthisstrategy,theresidualpheromoneofeachroadcanaccuratelyreflectthechangeofweightedvalueofeachroad.Animprovedselectionstrategybetweenadjacentcitieswasusedtocomputethecitiesπtransferprobabilities,asaresult,thecalculationofalgorithmwasgreatlyreduced,andthecomputespeedwasgreatlyincreased.Toavoidthealgorithmconvergingtothelocaloptimalresult,theantcolonyalgorithmwascom2binedwithgeneticalgorithm.Inthisway,thesolutionsaftereachtraversalwereusedastheinitialspeciestocarryoutsingle2pointcrossover.Animprovedantcolonyalgorithmfortheshortestpathproblemintime2de2pendentnetworksbasedontheseimprovedstrategieswaspresented.Theresultsofexperimentshowthattheimprovedalgorithmhasgreaterprobabilitytogettheglobaloptimalsolution,andtheconvergencerateofalgo2rithmisbetterthantraditionalantcolonyalgorithm.

Keywords:time2dependentnetworks;shortestpathproblem;antcolonyalgorithm(ACO)

  最短路径算法在许多研究和应用领域中起着重要作用.现有的文献中提出了大量求解最短路

径问题的方法和算法,但这些研究大部分针对固定权值的网络,没有考虑权值随时间变化等时变情况.在实际网络中,如通信系统、智能交通系统等应用领域中,边的权值往往是随时间变化的.因此,研究时变网络中最短路径的求解问题更加具有实用价值.

文献[1]中首次指出传统的最短路径算法不能适用于网络中边属性值为时变随机的情况,必须建立严格的一致性约束条件才能求解某一类动态网络中的最短路径问题.文献[2]提出了一种动态网络模型,并用改进的Dijkstra算法进行求解,但时间复杂度很高.文献[3]采用遗传算法求解动态网络中的最短路径问题,但遗传算法容易过早地收敛,使搜索陷入局部最优解.文献[4]采

 收稿日期:2008210215 基金项目:国家自然科学基金资助项目(60879024,60872062) 作者简介:刘永强(1978-),男,辽宁本溪人,博士生,yongqiangliu@sina.com.

第1页

你可能喜欢

  • Dijkstra算法
  • 弗洛伊德算法
  • Floyd算法
  • 最短路径
  • 消防规划
  • 应急物资调度
  • 蚁群算法

热门文档

相关文档

  • Dijkstra最短路径算法优化策略

    Dijkstra最短路径算法优化策略_其它_高等教育_教育专区 暂无评价0人阅读0次下载举报文档 Dijkstra最短路径算法优化策略_其它_高等教育_教育专区。数模相关方法...

  • Dijkstra最短路径算法的实现及优化

    Dijkstra最短路径算法的实现及优化_IT/计算机_专业资料。基于Dijkstra的算法分析Dijkstra 最短路径算法的实现及优化 施培港 厦门信息港建设发展股份有限公司 厦门市...

  • 快速Dijkstra最短路径优化算法的实现

    快速Dijkstra最短路径优化算法的实现_理学_高等教育_教育专区。运筹学资料测绘信息网www.othermap.com网友测绘人提供 快速 Di jkstra 最短路径优化算法的实现司连...

  • Dijkstra最短路径算法的优化和改进

    Dijkstra最短路径算法的优化和改进_天文/地理_自然科学_专业资料。随着计算机和...算法特点传统Dijkstra算法基于广度优先的搜索策略,从指定节点出发,通过权值迭 代...

  • 快速Dijkstra最短路径优化算法的实现

    、一 最短路径与 Dijkstra 算法 顶点 ( Vertex) 和边 ( Edge ) 为基础 , 采用顶点分区和 记录绝对地址来优化 Dijkst ra 算法的方法 。设 G = ( V , E...

  • Dijkstra最短路径算法优化

    Dijkstra最短路径算法优化_IT/计算机_专业资料。硕士论文 路径优化...算法分析传统 85JC?@&A 算法基于广度优先的搜索策略, 从指定节点出 图 (1 ...

  • 基于Dijkstra的最短路径算法的优化及应用

    基于Dijkstra的最短路径算法的优化及应用_信息与通信_工程科技_专业资料。本科...(四)特点传统Dijkstra算法基于广度优先的搜索策略,从指定节点出发,通过权值迭代...

  • Dijkstra最短路径算法优化

    G 施行优化 Djt 算法 , ,对,isakr则 可得从 到其余各节点的最短路径 , ...算法分析 图1非权图 负值 传统 Djt 算法基于广度优先 的搜索策略, isakr 从...

  • Dijkstra最短路径算法优化

    Dijkstra最短路径算法优化_天文/地理_自然科学_专业资料。Dijkstra最短路径算法,非常适合相关专业的学生。第25卷第 3期 2006年 8月文章编号: 1006 - 4869( ...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email