基于改进蚁群算法的最短路径问题研究

《基于改进蚁群算法的最短路径问题研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、无忧文档无忧文档可免积分在线阅读和下载文档包括资格考试、应用文书等大量word文档免费下载基于改进蚁群算法的最短路径问题研究[搜索文档]·无忧文档·高等教育·高中教育·初中教育·小学教育·外语考试·资格考试·工作范文·求职职场·党团工作·表格模板·总结汇报·经管营销·教学研究您的位置：无忧文档所有分类基于改进蚁群算法的最短路径问题研究基于改进蚁群算法的最短路径问题研究《自动化技术与应用》２００９年第２８卷第６期控制理论与应用ControlTheoryandApplications基于改进蚁群算法的最短路

2、径问题研究*张学敏,张航（中南大学信息科学与工程学院,湖南长沙410075）摘要:最短路径问题是智能交通:交通网络分析中的一个重要问题。文章分析了基本蚁群算法在求解交通网络两点之间最短路径时所出现的问题,并针对这些问题,在方向引导及信息素更新等方面对算法进行了改进。实验证明,改进后的方法较基本蚁群算法能准确快速地找到交通路网中两点间的最短路径,是切实可行的。关键词:智能交通;最短路径;蚁群算法中图分类号:TP301.6文献标识码:A文章编号:1003-7241(2009)06-0004-04Resear

3、chAnImprovedAntColonyAlgorithmoftheOptimalRoutingProblemZHANGXue-min,ZHANGHang(SchoolofInformationScienceandEngineering,CentralSouthUniversity,Changsha410075China)Abstract:SearchfortheshortestpathintransportationnetworkisoneofthemostimportantproblemofITS

4、.Thispaperanalyzesthebasicantcolonyalgorithmandpresentsanimprovedalgorithmontheheuristicdirectioninformationandrenewalofpheromone.Theresultsoftheexperimentationprovedthattheimprovedalgorithmcouldfindtheshortestpathmoreaccuratelyandquicklythanthebasicalgo

5、rithm,andit’sfeasible.Keywords:intelligenttransportsystem(ITS);shortestpath;antcolonyalgorithm1引言最短路径问题是智能交通中交通网络分析中的一个重要问题,也是一个研究热点。它是资源分配、路线设计及分析等优化问题的基础,具有重要理论意义和实际应用价值。有许多研究者曾对最短路径算法进行了大量的研究,并取得了很大的进展,提出了很多解决这类问题的方法。其中传统的算法有,Dijkstra算法、A*算法及其改进算法等等;还

6、有近几十年来,通过模拟或揭示某些自然现象而产生了一些新颖的启发式智能算法,如遗传算法、模拟退火算法、禁忌搜索算法、蚁群算法等。城市道路网中的交叉路口,连接两节点之间的边表示道路路线,并将路线的长度、通行时间、路况等属性表示为该边的权值,那么就可以把道路网络抽象为一个带权有向图。给定一个带权有向图G为二元组G=(V,{E}),其中V是包含n个节点的集合,E是包含h条边(弧段)的集合,是E中从节点i至j的边,wij是边的非负权值。设S,T分别为V中的起始节点和目标节点,则最优路径问题就是

7、指在带权有向图G中,寻找从指定起始节点到目标节点的一条具有最小权值总和的路径。2交通最短路径问题描述城市道路网有道路路线、交叉路口等物理属性,同时也具有路线长度、通行时间、路况等各种其它逻辑属性。用节点来表示3蚁群算法的基本原理及存在的问题蚁群算法就是受蚂蚁觅食行为的启发,以人工蚂蚁模拟真实蚂蚁行为来求解组合优化问题的方法。在20世纪90年代初期,由意大利学者DorigoMacro等首先提出[1]。其原理在于[5],蚂＊基金项目：湖南省科学技术与科技计划（编号２００６ＧＫ３１３０）；湖南省自然科学基金奖

8、资助项目（编号０５ＪＪ３０１２１）收稿日期：２００８－１１－１０T蚁在所经过的路径上留下一种称为信息素的挥发性分泌物,在觅食过程中蚂蚁能够感知这种物质的存在及其强度,并以此来指导第1页下一页Word文档免费下载：基于改进蚁群算法的最短路径问题研究（共4页，当前第1页）你可能喜欢·蚁群算法matlab程序·蚁群算法求解TSP问题·数学最短路径问题·最短路径动态规划·最短路径问题·最短路径算法改进·物流配送路径优化·matlab实例教程·蚁群算