基于GIS和遗传算法的最短路径研究
开篇：润墨网以专业的文秘视角，为您筛选了一篇基于GIS和遗传算法的最短路径研究范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘要：地理信息系统（GIS）为智能道路交通管理提供了基本数据库，也是进行道路交通网络分析的有力工具。对廊坊道路交通网络进行数据建模，构建了廊坊道路交通地理数据库，研究了遗传算法在求解交通网络最短路径中遇到的问题，以廊坊道路交通地理信息系统为数据平台，对基本遗传算法在种群初始化、交叉和变异算子上做了改进，实现了两点间最短路径的求解。
关键词：GIS 遗传算法 最短路径
1 概述
随着经济的不断发展，人们的生活水平逐渐提高，汽车作为代步工具走进了普通家庭。人们在享受私家车带来便利的同时，也受到交通阻塞、驾车出行难的困扰。虽然最近几年来国家对城市道路建设进程有所加快，但由于资金和空间的限制，单纯依靠道路基础设施的扩建和完善是无法很好地解决日益严重的交通问题的，因此人们驾车出行时，首要解决的问题是选择合适道路。
所谓地理信息系统GIS（Geographic Information System）是对地理空间的数据进行分析和处理，其功能是将抽象的地图数据转化为可视的画面。借助GIS可以对道路选择机制进行完善，在一定程度上避开道路的拥挤，进而寻找一条合理的出行线路。
如果把城市交通网看作网络图，那么搜索两个地点之间的最短路径问题就是网络图中节点之间的最短路径问题。经典的Dijkstra 算法是一种静态的局部最优算法。该算法简单、易于实现，但在网络节点和路径较多的情况下，搜索效率会大大降低。近年来，遗传算法因为其强大的并行搜索能力，能够解决复杂的和非线性的问题而被用来求解最短路径问题。本文将遗传算法应用于廊坊实际的道路交通网络，在染色体的构造、适应度函数的设计上，引入实时变化的交通信息，在初始种群、选择、交叉和变异算子上加以改进，求解出满足驾驶者要求的最短路径。
2 廊坊道路交通地理信息系统数据库的构建
2.1 系统处理的数据
结合廊坊道路交通的特点，采用空间数据模型Geodatabase，将廊坊道路网抽象为包含点、线、面的空间信息和不包含空间信息的对象类。道路信号灯、信号指示牌、路标等附属设施、道路上桥梁、隧道、涵洞、交叉口等构造物，以及将路段的路面状况设成线性参考和动态分段中的事件。根据要素类和对象类具有的属性、行为和规则，要素类之间、要素类与对象类之间、对象类之间借助关系类进行关联。
2.2 数据来源
①空间数据：空间数据由河北省测绘局提供，该数据为1：25万地形图上的境界、水系、道路、居民地、地名等。
②属性数据：属性数据从廊坊交通局收集，主要包括路线概况集、路基集、路面集、主要构造物集、沿线设施集、交通量集、沿线环境集、年报数据集。
2.3 数据组织
如图1所示，本系统将整个地理数据库分为基础地图层、交通网络层、线路和事件层以及应用层。将上述各层叠置在一起，就构成一张路网图，它是公路网信息的总和。进行空间分析与处理时，可以提取有关的若干数据层叠加而得到所需数据层。
3 采用遗传算法求解交通网络中的最短路径
3.1 基本遗传算法在求解交通网络最短路径中的问题
基本遗传算法用于交通网络中最短路径搜索时存在的问题：一是基本遗传算法中，初始种群的随机产生方法易于产生断路，环路以及重复顶点等不可行的解。二是在真实的路网中，不能用基本遗传算法的交叉算子和变异算子来表达道路是单向通行，禁止通行、禁止左转等交通限制条件。因此本文在种群的初始化、交叉和变异算子上做了改进。
3.2 改进的遗传算法
3.2.1 染色体的编码。本文要求解的是交通网络中从源点到目标点的一条最短搜索路径，网络中节点编号的排列顺序正好组成一条搜索路径，因此采用不等长可变染色体实数编码方案。源节点是染色体的第一个基因，目标节点是最后一个基因位置。如果网络节点总数为N，那么染色体的长度在2和N之间，通常情况下，染色体长度是可变的，但最大长度不能超过N，原因是一条搜索路径不会出现回路，节点总数不会超过N，并且从源点到目标点有很多路径，这些路径经过的节点数目不同，如果采用固定长度的染色体编码，搜索空间增大，算法效率无法保证。
3.2.2 种群的初始化。基本遗传算法的种群初始化是随机产生的，这是为了保证初始种群的多样性。在交通网络中，如果按照染色体的编码方案随机产生种群，有可能根本构不成一条从源点到终点的搜索路径，因为有些节点可能产生断路或回路。
交通网络节点的邻接表中按权值（综合考虑两节点之间的距离、路况、节点延迟得到权值）排序。以源点作为染色体第一个基因，从该节点邻接表中找出权值最小的节点作为路径的第二个基因，并标记该节点，从第二个基因的邻接表中找出权值最小的节点（未标记）作为路径的第二个基因，并标记它，依次类推，直到目标节点，得到一条初始染色体，按照算法中指定的种群规模（如N=100），按照此方法产生100条染色体，完成了种群的初始化。
3.2.3 适应度函数的确定。根据构造的染色体，本文建立如下适应度函数
， 该函数表示从源节点到目标节点经过的弧段和节点的耗费期望值之和的倒数，适应度函数的值越大，表示从源点到目标点的耗费越少，相应个体也越优质。
3.2.4 遗传算子。①选择：在选择过程中，使用轮赌法，结合精英保留策略，保留上一代较优的个体，保证算法的收敛。进行选择时，产生一个随机数，当该随机数大于个体的选择概率且不大于该个体的累计选择概率，将该个体选中送入池。操作过程：保存当前群体中适应度函数值最低的个体，在选择、交叉、变异产生的下一代个体中，检查父代的最佳个体是否存在，为保持群体规模不变，将子代个体中适应度函数值最高的个体淘汰。
②交叉：采用改进的单点交叉。按一定的交叉概率Pc从父体中挑选出若干个染色体进行杂交，如果挑选数目是奇数，则或从父体中随机地再挑选一个，或从已挑选的染色体中删除一个，这样共挑选出偶数个染色体，再将这些染色体随机地两两配对进行杂交，产生两个后代个体。改进的单点交叉过程如下：
本文种群初始化时得到的染色体第一个基因和最后一个基因是源节点和目标节点，都相同，进行选择交叉操作时两个父代染色体将出现两种情况，一是两个父染色体除源节点和目标节点外没有相同的节点，二是两个父染色体除源节点和目标节点外还有相同的节点。对于第一种情况，随机产生一个整数作为交叉位置进行交叉操作，但交叉操作后产生的个体有可能形成断路或回路，此时要对子代个体中非法的个体进行修正，按照前边种群初始化时介绍的启发式方法补充相应节点使该子代个体成为一条有效搜索路径。对于第二种情况，在两个父染色体中相同节点处进行交叉，如果相同节点多于1个，则从相同节点中随机选择一个作为交叉位置。
③变异：变异算子的目的在于引入种群中染色体的多样性，防止算法的过早收敛。变异算子以某一预定的概率Pm对种群中染色体的每个基因进行变异。当染色体的某一位基因被选择进行变异时，还要考虑到随机变异后的染色体可能不再是一条从源点到目标点的搜索路径，变异后的基因可能形成断路。改进方法：变异基因连接前后的两基因组成一条子路径（起点为变异基因前一个基因，终点为变异基因后一个基因），采用种群初始化时的启发式方法（利用邻接表）用另一条子路径（起点和终点不变）替换此子路径，这样就保证变异后的染色体仍然是一个没有断路或回路的搜索路径。
4 实验步骤和结果分析
4.1 开发环境
GIS和二次开发平台：ArcGIS 10.0，ArcEngine10.0，Microsoft Visual c++6.0。
数据库管理系统：MS SQL Server 2005标准版 空间数据库引擎：ArcSDE10.0。
4.2 求最短路径实验步骤
①用户在最短路径搜索模块中输入要查询的源节点和目标节点，地理信息系统接收输入，借助ArcGIS 10可以生成一个交通网络图。
②根据数据源，读取数据库中线图层数据，提取节点信息，建立要搜索的交通网络图中节点之间的邻接关系表。
③设置遗传参数：种群数量N=100，交叉概率Pc=0.85，变异概率Pm=0.02，最大遗传代数Maxgen=200。
④初始化种群。
⑤计算个体的适应度函数值。
⑥种群中全部个体按照适应度进行排序，结合给定的交叉和变异概率按照改进的交叉和变异算子，生成新一代的群体。
⑦计算新一代群体中个体的适应度。
⑧是否达到最大遗传代数，如是结束，就将结果输出，否则跳到⑤继续执行。
4.3 分析实验结果
在廊坊交通网上进行实验，此网络由3867条路段和2352个节点组成。上午7：00-8：30被选定为研究时间区域。在交通网中随机选取了5对源点到目标节点，每对源-目标节点选取不同的初始种群计算了3次，实验结果如表1所示。实验计算结果都能收敛。从表1的试验结果中可以看到算法计算到最短路径的平均计算时间2.5s，说明算法有很高的效率。
参考文献：
[1]梁循.数据挖掘算法与应用[M].北京大学出版社，2006.
[2]廉晚祥，朱参世.改进遗传算法在应急救援物资运输中的应用[J].中国安全科学学报，2013（5）：172-176.
[3]侯树军.地理信息系统在求解公路交通规划中最短路径问题的应用[J].内蒙古公路与运输，2013（1）：15-17.
[4]王，李仁旺，倪夏静，陈昆昌，莫灿林.基于遗传算法的服装配送路径优化策略[J]. 浙江理工大学学报，2013.30（2）：178-183.
基金项目：本文由河北省教育厅自然科学项目资助，课题编号是Z2006420。
作者简介：张艳肖（1972-），女，河北晋州人，河北经贸大学计算机中心，副教授，硕士，研究方向：数据挖掘和人工智能。
周芸（1969-），女，河北保定人，河北交通职业技术学院，副教授，硕士，研究方向：网络和人工智能。