数模相关方法
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.
Dijkstra最短路径算法优化策略_其它_高等教育_教育专区 暂无评价0人阅读0次下载举报文档 Dijkstra最短路径算法优化策略_其它_高等教育_教育专区。数模相关方法...
Dijkstra最短路径算法的实现及优化_IT/计算机_专业资料。基于Dijkstra的算法分析Dijkstra 最短路径算法的实现及优化 施培港 厦门信息港建设发展股份有限公司 厦门市...
快速Dijkstra最短路径优化算法的实现_理学_高等教育_教育专区。运筹学资料测绘信息网www.othermap.com网友测绘人提供 快速 Di jkstra 最短路径优化算法的实现司连...
Dijkstra最短路径算法的优化和改进_天文/地理_自然科学_专业资料。随着计算机和...算法特点传统Dijkstra算法基于广度优先的搜索策略,从指定节点出发,通过权值迭 代...
、一 最短路径与 Dijkstra 算法 顶点 ( Vertex) 和边 ( Edge ) 为基础 , 采用顶点分区和 记录绝对地址来优化 Dijkst ra 算法的方法 。设 G = ( V , E...
Dijkstra最短路径算法优化_IT/计算机_专业资料。硕士论文 路径优化...算法分析传统 85JC?@&A 算法基于广度优先的搜索策略, 从指定节点出 图 (1 ...
基于Dijkstra的最短路径算法的优化及应用_信息与通信_工程科技_专业资料。本科...(四)特点传统Dijkstra算法基于广度优先的搜索策略,从指定节点出发,通过权值迭代...
G 施行优化 Djt 算法 , ,对,isakr则 可得从 到其余各节点的最短路径 , ...算法分析 图1非权图 负值 传统 Djt 算法基于广度优先 的搜索策略, isakr 从...
Dijkstra最短路径算法优化_天文/地理_自然科学_专业资料。Dijkstra最短路径算法,非常适合相关专业的学生。第25卷第 3期 2006年 8月文章编号: 1006 - 4869( ...
热门文档