蚁群算法在GIS最短路径求解中应用的初步研究.pdfVIP

58 城 　市 　勘 　测 2009年 文章编号 : 1672 - 8262 (2009) 03 - 58 - 04　　　　　　　　　中图分类号 : P208　　　　　　　　文献标识码 : A 　　 蚁群算法在 GIS最短路径求解中应用的初步研究 刘晓亮 (辽宁工程技术大学 测绘与地理科学学院 ,辽宁 阜新 　123000) 摘 　要 :最短路径的求解是 GIS应用中的主要问题之一 。在传统的最短路径求解算法中 , D ijk stra算法和启发式有哪些信誉好的足球投注网站 算法 - A 算法具有较好的效果 ,得到了广泛的应用 。蚁群算法是由意大利学者 Dorigo 等人于 20 世纪 90 年代初期 通过模拟自然界中蚂蚁集体寻径的行为而提出的一种基于种群的启发式仿生进化系统 。蚁群算法最早成功应用于 解决著名的旅行商问题 ,该算法采用了分布式正反馈并行计算机制 ,易于与其他方法结合 ,而且具有较强的鲁棒性 ,是 一种很有前途的仿生优化算法 。本文将对该算法应用于 GIS中最短路径的求解方面的问题进行初步的研究 。 关键词 :最短路径 ;蚁群算法 ;应用研究 1　引　言 息不断调整 自身结构 。在协作阶段 ,候选解之间通过 随着计算机软硬件技术的飞速进步 ,地理信息系 信息交流 , 以期望产生性能更好的解 ,这类似于学习自 统得到了快速的发展 。网络分析作为地理信息系统 动机的学习机制 。蚁群算法最早成功应用于解决著名 ( ) ( ) 的旅行商问题 traveling sale sm an p rob lem , TSP ,该算 G IS 最主要的功能之一 ,在导航 、交通 、旅游 、城市规 划以及电力 、通讯等各个方面中发挥了重要的作用 。 法采用了分布式正反馈并行计算机制 , 易于与其他方 ( ) 网络分析要解决的问题中有两个是和最短路径相关 法结合 ,而且具有较强的鲁棒性 robu stne ss 。蚁群算 的。一个是最佳路径选择 , 比如由 A 地前往 B 地 ,选 法创立十多年来 ,无论在算法理论还是在算法应用方 择怎样的路线才是最佳的。另一个是资源分配的问 面都取得了很多突破性研究进展 。作为一个前沿性的 题 ,它是关于资源调送的问题 ,广泛应用于消防站点分 热点研究领域 ,蚁群算法已引起越来越多国内外研究 者的关注 ,近 5 年内其研究人员和研究成果均成几何 布 ,选址 ,物资分配 ,供水供电等方面 。最短路径不仅 级数增长 。其应用范围几乎涉及各个优化领域 ,而且 仅指一般地理意义上的距离最短 ,还包括其他的方面 , 还出现了蚁群算法仿生硬件 ,可见这种新兴的仿生优 如最短的时间、最少的费用等 。所以,最短路径问题其 [ 1 ] 化算法 已经显示 出强大 的生命力和广 阔的发展前 实是最佳路径问题 、最低费用等的问题 。传统的最 景 [ 2 ] 。尽管人们对蚁群算法的研究时间不长 ,在这一 短路径求解算法 - D ijk stra 算法是 目前多数系统解决