资源描述：
《基于改进蚁群算法的最短路径问题研究及应用_宋锦娟》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、第43卷第3期数学的实践与认识Vol.43,No.32013年2月MATHEMATICSINPRACTICEANDTHEORYFeb.2013基于改进蚁群算法的最短路径问题研究及应用宋锦娟,白艳萍(中北大学理学院,山西太原030051)摘要:蚁群系统作为一种蚁群算法是解决最短路径问题的一种行之有效的方法.然而,它自身也存在着一些缺陷,主要针对基本蚁群算法易陷入局部最优这一缺陷对其进行改进,集中体现在初始信息素求解和信息素更新这两方面.为了进一步了解改进蚁群算法的优点,进行了实验仿真:将改进的蚁群算法应用子模拟医疗救护GIS中,利用GIS的网络分析功能对城市道路网络的最短路
2、径选择算法进行了深入地探讨研究,并以山西省太原市的交通路线作为实例进行研究.计算机仿真结果表明,改进的蚁群算法在解决最短路径问题时较基本蚁群算法的性能好,它具有一定的理论参考价值和现实意义.关键词:蚁群系统;最短路径问题;信息素;城市道路网络1引言最短路径间题l]是交通网络分析中的一个重要间题,也是当今社会研究的一个热点.它与作业车间调度二次分配等问题相似,都属于组合优化间题.解决最短路径问题的算法有很多,传统的算法包括Dijkstra算法A*算法等.近些年来,人们又提出了一些新颖的启发式智能算法,如遗传算法(GA)模拟退火算法(SA)禁忌搜索算法(TSA)蚁群
3、算法等.最短路径问题是图论中的一个经典问题,它一般可分为以下几类[z]:两个指定节点间最短路径所有节点间最短路径K则最短路径和指定必经节点的最短路径问题.由于蚁群算法不仅具有较强的随机搜索寻优能力和自适应性分布等特点,而且它的工作原理与车辆路径选择过程十分相似,于是本文对基本蚁群算法作了改进,并以两个指定点之间的最短路径问题和现实生活中山西省各个市县的地理位置坐标为例进行实验仿真,其结果令人满意.2最短路径问题2.1研究意义随着国民经济的高速发展和城市化进程的加快,城市规模在不断扩大,城市的道路交通网络也越来越庞大和复杂,伴随着城市人口数量和人口密度的增高各种突发性疾
4、病和其它灾害事故造成的伤病人员也随着现代化城市布局的扩大和经济的发展而呈现出复杂化多样化立体化的发展趋势,这使得城市医疗救护系统的重要性越发突出,而其中尤其以该系统中的最短路径选择最为关键.医疗救护贵在及时性,能够在最的时间内把伤病人员从事发位收稿B期:2012一06一26资助项目:2009年山西省自然科学研究基金(2009011015一3)3期宋锦娟,等:基于改进蚁群算法的最短路径问题研究及应用157置送往医院展开抢救,是救护成功的很重要因素.及时性就要求系统的决策效率高,关键是如何选择一条合理的救护路线以使行车时间尽量最短,因而最短路径选择就显得尤为重要,而其中的
5、最短路径算法是核心.2.2两个指定节点间最短路径问题的描述城市道路网la]有道路路线交叉路口等物理属性,同时也具有路线长度通行时间等各种逻辑属性.分别用节点和道路路线来表示城市道路网中的交叉路口和两节点之间连接的边,并将路线的长度通行时间等属性表示为该边的权值,那么就可以把道路网络抽象为一个带权有向图.给定一个带权有向图G为二元组G=(V,{E}),其中v是包含n个节点的集合,E是包含h条边(弧段)的集合,(乞,力是E中从节点葱至J的边,勺是边,力的非负权值.设S,T分别为V中的起始节点和目标节点,则最优路径间题就是指在带权有向图G中,寻找从指点起始节点S到目标
6、节点T的一条具有最小权值总和的路径.2.3TsP问题的描述TsP问题即旅行商问题具体描述如下:给定N个城市,有一旅行商从某一城市出发,访间各城市一次且仅有一次后返回原出发城市,要求找出一条最短的巡回路径其也可以用数学方法描述为:设有N个城市的集合C={c,,c2,cN},每个城市之间的距离为d(,cj)R十,其中氏,cjC(1三乞,j三N).求使目标函数二一艺乞=1d(n(i),n(+小d(n(,),cn(1))达到最小的城市序列{en(l),en(2),en(,)},其中fl(1),1(2),,1(N)是1,2,,N的一个全排列.3蚁群算法的基本
7、原理蚁群算法是通过模拟自然界中真实蚂蚁的觅食行为而由意大利学者DorigoM提出的一种智能仿真进化算法,属于随机搜索算法.在自然界中蚂蚁几乎是看不见的,那么蚂蚁又是靠什么来寻找一条由食物源到蚁穴的最短路径的呢?经过大量的观察和实验,发现蚂蚁个体是借助一种称之为信息素的物质进行交流和协作以完成食物的寻找.蚂蚁在觅食的过程中,能够在它所经过的路径上留下信息素.并且能够感知这种化学物质.大量的蚂蚁共同合作通过信息素浓度的变化来指导其运动方向.一条路径上的信息素浓度越大,对蚂蚁的吸引力就越大,则蚂蚁选择该路径的概率就越大,从而使得该路
