一种复杂地理环境越野通行路径寻优算法 优先出版.doc

《一种复杂地理环境越野通行路径寻优算法 优先出版.doc》由会员分享，可在线阅读，更多相关《一种复杂地理环境越野通行路径寻优算法 优先出版.doc（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第 2017 年 34 卷第 5 期 测 绘 科 学 技 术 学 报 Journal of Geomatics Science and Technology 2017 Vol 34 No 5 文章编号： 1673-6338（ 2017） 05-0525-04 一 种 复 杂 地 理 环 境 越 野 通 行路 径 寻 优 算 法 赵 成 1 ， 张涵斐 2 ， 高 毅 3 ， 吴超辉 4， 5 ， 黄 征 4 （ 1 信息工程大学，河南 郑州 450001； 2 61363 部队，陕西 西安 710054； 3 乌鲁木齐民族干部学院，新疆 乌鲁木齐 830001； 4 68029 部队博士后工作

2、站，甘肃 兰州 730020； 5 68206 部队，甘肃 兰州 731100） 摘要： 设计了基于障碍距离的优化算法 ，解决突发事件应急联动中复杂地理 环境下最 短路径的寻 优求解问 题。在详细分析 地理空间高程、坡度、障碍物等空间信息的基础上，通过计算 搜索空间、搜索方 向和网络弧 段权值构建网络拓扑关系网，并利用遗传算法对最优路径进行寻优求解。 关 键 词： 地理环境； 障碍距离； 最优线 路； 遗传算法； 搜索空间 中图分类号： P 208 文献标识码： A DOI 编码： 10 3969 /j issn 1673-6338 2017 05 017 A Cross-Country Pa

3、ss Path Optimization Algorithm Based on Complexity Geographical Environment ZHAO Cheng ， ZHANG Hanfei ， GAO Yi ， WU Chaohui ， HUANG Zheng 4 （ 1 Information Engineering University， Zhengzhou 450001， China； 2 61363 Troops， Xian 710054， China； 3 Urumqi National Cadre Institute， Urumqi 830001， China； 4

4、68029 Troops Postdoctoral Programme， Lanzhou 730020， China； 5 68206 Troops， Lanzhou 731100， China） Abstract： The optimization algorithm based on distance obstacle is designed to solve the shortest path optimization problem in the emergency linkage and complex geographical environment in this paper T

5、his method is based on the detailed analysis of geographical spatial elevation， slope ， obstacle and other spatial information One kind of topol- ogy net is constructed using the calculation of search space ， search direction and network arc weights Finally， the optimal path is optimized by means of

6、 the genetic algorithm Key words： geographical environment； obstacle distance； optimal route； genetic algorithm； search space 随着我国经济社会的发展，各类突发事件频 GIS 空间分析功能构建特定的算法 ，为突发事件 繁发生。如 果对这些突发事件处理不当就会发展 成大规模的事故，对社会造成巨大的伤害和破坏。 确立正确可行的应急保障路径并进行路径优化可 使灾害应急交通保障得以有效实施，降低灾害的 负面影响和损失。 GIS 系统中，一般通过构建拓 扑关系 ，利用 Dijkst

7、ra、 Floyd 等算法对路径矢量 数据进行最优路线求解 。 目前，栅格数据的最短路径寻优，一般是将数 据经过格网 化转成矢 量数据 。这种栅 格数据 的最短路径寻优，常用于地形起伏不大，较为平缓 的区域，如若地理环境较为复杂，则会产生较大误 差。本文旨 在研 究复 杂地 理环 境下，如何 通过 收稿日期： 2016-12-06； 修回日期： 2017-03-21。 基金项目： 国家自然科学基金项目（ 41071297） 。 的应急保障和非战争军事行动提供决策指导。 1 地表障碍距离 空间距离计 算是空间分析 中的关键 技术之 一，而较为传统、常用的空间距离研究通常不考虑 空间中的路径上是否

8、存在障碍物，这使得解决空 间距离中最佳路径问题存在局限性 。因此，引 入地表障碍距离 d0（ p， q） ，并运用可视图法解决 存在障碍物的地理空间上两 点间距离的问题 其， 中 p、 q 表示任意两点。在综合考虑障碍物、地表坡 度、地表高程等制约通达的要素后， p、 q 之间最短 路径的距离即为对象在两点间通行的实际距离。 作者简介： 赵 成（ 1974） ，男，甘肃宁县人，博士生，主要研究方向为作战指挥学。 E-mail： 2589547188 qq com 通讯作者 吴超辉 男 工程师 ： ， ， 。 E-mail： 15052487 qq com 1 2 3 4， 5 1 2 3 52

9、6 测 绘 科 学 技 术 学 报 计算存在障碍物条件下的地表距离，较为常 障碍区域的确定是其核心手段。 VG （ Visibility Graph） 。 1： 。 2017 年 用的是可 视图法 该方 步骤 离散化处理 本 文所研究的主要是 法是解决多边形障碍物空间中目标间最优路径计 算的方法。可视图定义为 VG （ N， L） ，其中，N 表 示障碍物的节点集； L 表示不与障碍物相交的连 接所有节点的连接弧集。由于顶点仅包含相互间 可视的点，因此 VG（ N， L） 称为 N 的可视图。可视 图法中的节点集合是由障碍物顶点、路径起点和 到达目标点组成的。 “可视 ”的标准是要求任意 3

10、点间连线不穿越障碍物，简单来讲，就是障碍物顶 点连线与障碍物多边形不相 交。可视图法主要有 4 个步骤： 1） 因为实际障碍物在二维平面上可以 看做多边形的集合，因此需要将多边形同一直线 上的点去除，且按顺时针 排列； 2） 从 可视图判断 二维平面上多边形的凹凸性； 3） 若多边形为凸多 边形（ 顶 点到端点 可视） ，则 可计算 各边的 权值 （ 边的长度） ； 若多边形存在凹处，则可将多边形 的凹处通过连接顶点使之变成凸多边后求解； 4） 路径起始点的计算可用 Dijkstra 算法。 如图 1 所示， “障碍物 1”和 “障碍物 2”投射 到二维平面上分别为凸多边形和凹多边 形（ 阴影

11、 部分） ， p 和 q 分别代表路径的起点和终点。从可 视图中可判断多边形的凹凸性，图中加粗线段为 最短障碍距离。 陆域区域，因此在进行离散化处理时，对地图数据 的比例尺要求很高，精度高则离散化处理的数据 量就大。 步骤 2： 综合研判坡度、水系及人文因素等对 机动通行造成的影响。如坡度在 20以下为易通 行、坡度在 20 30为困难通行、坡度在 30以上 为不能通行； 越野机动一般避开居民地； 水系和植 被的影响因素根据实际通行武器装备有着不同的 通行标准。应用单要素叠加法，将障碍区 内的点 （ 障碍物） 建立新的障碍层，并将其矢量数据转化 为二进制（ 0， 1） 的栅格数据，分别用 1

12、和 0 表示 障碍区和通行区。 步骤 3： 地理空间 存在障碍物的最优距离确 定。将步骤 1 和 2 中的基础地形图进行叠加，形 成一 个新的搜索空间，再对此 空间进行格网化。 所形成的若干格网中，有障碍物的不能通行，用 1 表示。如图 2 所示，黑色格网表示障碍格网； S 和 T 分别表示路径的起点和终点，根据障碍层可确 定可通行最优路径。 图 1 地理空间地表障碍距离 2 地理空间存在障碍物的最优距离算法 存在障碍物的空间距离搜索是由地理空间的 图 2 离散化的寻优搜索空间 范围和网格 粒度所决 定的 ， Dijkstra 。如若搜索 空间增 2 2 地表距 离的计算 前文所论述的是处于二

13、维平面中地表距离的 大 那 么传统的 。 算 法的计算时间是非常 ， 计算 ，但是现实中地表是起伏不定的 。 搜索区域 大的 引入启发式算法和遗传算法 其中启发式 ， 离散化就是对地理空间坐标进行等间距划分。因 算法能根据差异选择深度搜索或广度搜索 传算法则能更好地进行盲搜。 算法流程为： 1） 格网划分（ 离散化处理 而遗 ） ； 2） 此进行离散化处理就是对地理空间坐标进行等间 距划分。地形较为复杂的区域，在综合考虑坡度、 坡向、高程等数据的前提下，可计算网格中两点的 确定障碍区或通达区； 3） 确定 节点间的 地表距 地表距 离 5 6 。 离； 4） 遗传算法进行编码； 5） 确定计算

14、所需各种 7 如图 3 所示，利用分段积分的方法，对格网中 数值；6） 2 1 遗传算法进行种群遗传和变异处理 。 任意两点长度进行计算。 通过格网化处理 ，将总 搜索空间的确定 此过程是一个地表离散化处理与空间障碍区 长分为 sp1、 p1 p2 、 p2 p3、p3 p （ i 4 和 p4 t 这 5 个弧段，其 1， 5） 。 。 所对应的坡度角为 i 将欧氏距离 域确定的过程 运用格网的划分在地形图上进行 计算的结果近似为离散化后的两点弧段长度，即 第 34 卷第 = 5 期 + + 赵 成 等 一种复杂地理环境越野通行路径寻优算法， ： + + 527 st sp1 p1 p2 p

15、2 p3 p3p4 4 s t 1 2 3 4 5 5 i = 1 + （ 1） 实数，为使式（ 3） 中分母不为 0，取 （ 0， 1） 。 步骤 4： 遗传算子的确定。对种群进行遗传 计算 ，需要确定选择算子、交叉算子和变异算子。 确定遗传算子新的基因遗传与变异方法见图 4。 式中：表示两点间的弧段长； x 表示格网点的 横坐标； i 表示点号； hi 表示格网点 i 的高程； n 表 示总点数； d 表示格网点的间距。 1） 图 4 基因的遗传与变异操作 ： （ 2） ， 选 择算子 根 据式 计 算适 应度 函数 。 2 3 图 3 地表距离 值 使个体按照适应度成正比的概率向子代繁殖

16、 2） 交叉算子： 以一定的概率随机选择一个除 基于遗传算法的障碍距离寻优 遗传算法是模拟生物进化机制来构造人工系 起始点与目标点以外的点 ， （ 交叉点 ） 。 当交叉点 ， ， 统的一种完整的建模方法。在遗传算法的基础上 对障碍距离进行寻优。具体步骤如下。 多于一个时 操作。 可根据交叉概率进行交叉 否则 不 步骤 1： 搜索空间编码 。 将信息按一定的模 3） 变异算子： 为保证遗传 算法的有效性，与 。 式排列，即进行编码，本文采用的是二进制编码。 选择算子结合进行局部搜索 对路径中不理想的 ， 步骤 2： 个体种群的初始化。在进行空间搜 索最优障碍路径时，应用遗传算法将其抽象为一 定

17、数目的染色体编码。在存在障碍物时，选择可 行路线与可行方向最小的夹角。 路径进行变异以提高算法效率 号进行代替。 3 算例及结果分析 可用一个随机序 步骤 3： 适应度函数的计算 、 。 适应度函数主 ， 设定地理空间中有 8 个位置点，其基本属性 信息如爬坡、涉水、登高等能力已知，地形数据、植 要由路径长度 平滑度和间接度组成 是评判种群 、 。 5 优劣的标准。利用加权 L p 范数，以折中的方法对 被情况 ， 水系分布等空间信息也已知 、 、 、 如图 、 所 距离进行数学描述，即 示 该地理空间由于坡度 高度 水系 植被 人文 r（ z； P， ） = zz * = j= 1 P j

18、* | zj z * j * | 1 /P * （2） 等因素的 “障碍 ”作用而存在障碍点，是具有障碍 约束的地理空间，在 8 个点之间进行越野通行最 短路径寻优计算。 式中 ： z 表示格 网点的弧段长； z = （ z 1 ，z 2 ） 是最 = 优解； P（ 平滑度） 反映应用对象的偏好，当 P 式（ 2） 对所有目标的后悔值进行 计算，当 P = ； 1， ， 。 对单个目标的后悔 值进行计 算 代表间 接度 在运用遗传算法对最优点进行求解时，不能进行 一次性的全局求解，因此局部最优点的计算是必 不可缺少的步骤 。局部最优点计算如下： min min 求解所得值（ 即后悔值） 越小，

19、则可认为越接 近最优值。适应度函数可定义为 max min max 1 p t =n | x x | （ cos +cos 1 + + = 2 2 + i i 1 2 8 1 1 = 2 2 z =min z （ x） | x P 。 r 分别表示最大和最小后悔值； 是不为零的正 （ a） （ c） 对象地理空间植被情况 对象地理空间交通分布 5 （ b） 对象地理空间水系分布 （ d） 人文因素限制通行分布 min 图 障碍要素信息情况图 528 3 1 网络拓扑结构的构建 ， 测 绘 科 学 技 术 学 报 2017 年 应用本文方法 （ 格网粒度为 1 m 对地理空间进行网格化处理 1

20、m） 。根据目 标机动能力确 定存在障碍物的区域，叠加后得到如图 6 所示的 拓扑图。图中空白网格表示易通行区域； 灰色网 格为不 可通行区域； 连线为搜 索点的最优通道。 在已知网络拓扑图基础上，将高程、坡度等数据代 入式（ 1） 可计算节点之间的距离 。 （ c） 目标 2 目标 3 、目标 4、目标 5 寻优过程 （ d） 目标 2 到目标 6、目标 8 与目标 3 到目标 4 寻优 （ e） 目标 3 目标 5、 目标 6、目标 8 寻优 图 6 对象空间格网化、可行空间分布及寻优结果 3 2 目标两两之间最优障碍距离 求解最优障碍距离的必要条件是首先确定网 。 8 络节点之间 的距离

21、 假定计算地理空间上 个两 （f） 目标 4 目标 5、目标 6 与目标 5 目标 8 寻优 两目标的最优路径的结果相同，应用遗传算法，对 其进行 200 次迭代，交叉概率和变异概 率分别为 0 4 和 0 1。此种群的长度为 15 位 距离矩阵为， D= 0 31 414 96 56 91 21 168 98 110 6 337 96 （ g） 目标 5 目标 6、目标 8 与目标 6 目标 8 寻优 0 64 14 0 58 28 122 42 0 132 42 58 28 180 7 280 14 168 98 3 3 图 7 结果分析 应用遗传算法寻优过程 ， 0 综合考虑了地理空间的

22、各种障碍因素 应用 ， 0 遗传算法对存在障碍物的空间距离进行求解 减 最优路径如图 7 所示。 0 少了对最优距离进行搜索的空间范围，缩短了计 算时间。其中适应度函数能快速收敛，且只需计 算到 150 代就能得到理想的路径。 4 结束语 基于遗传算法对地理空间存在障碍物的目标 ， （ a） 目标 1 目标 2、目标 3、目标 4 寻优 之间的最优路径进行求解 该方法在现实中能更 好地对复杂地形下的地理空间两点的距离进行寻 优。地理空间网络拓扑关系的构建，地表距离的 计算，高程、坡度信息的处理使得计算地理空间中 两点之间的距离在数据支撑上更加精确。 9 0 66 56 61 21 143 63

23、 122 42 293 82 227 26 349 68 （ b） 目标 1 目标 5、目标 6、目标 8 寻优 （ 下转第 534 页） 534 测 绘 科 学 技 术 学 报 2017 年 4 5 6 7 8 9 for denoising remote sensing image with gaussian and salt pep- per noise J Acta Geodaetica et Cartographica Sinica， 2010， 39（ 3） ： 283-288 PE ONA P， MALIK J Scale-space and edge detection usi

24、ng anisotropic diffusion J IEEE Trans on Pattern Anal Machine Intell， 1990， 12（ 7） ： 629-639 ALVA EZ L， MO EL J M Formalization and computational aspects of image analysis J Acta Numerica， 1994（ 3） ： 1-59 王锋，张昆帆，孟凡坤，等 一种基于总体变分的自适应图 像 去噪方法 J 测绘科学技术学报， 2014， 31（ 1） ： 49-52 WANG F， ZHANG K F， MENG F K，

25、 et al An adaptive image noise removal method based on total variation J Journal of Geomatic Science and Technology， 2014， 31（ 1） ： 49-52 YOU Y L， KAVEH M Fourth-order partial differential equa- tions for noise removal J IEEE Transactions on Image Pro- cessing， 2000， 9（ 10） ： 1723-1730 林青，秦志远图像处理中的

26、PDE 及其数值解算方法 J 测 绘 科学技术学报， 2011， 28（ 5） ： 360-364 LIN Q， QIN Z Y Numerical calculating methods of PDE in im- age processing J Journal of Geomatic Science and Technolo- gy， 2011， 28（ 5） ： 360-364 BA BU T A nonlinear fourth-order PDE-based image denois- ing technique C The International Conference on

27、Systems， Signals and Image Processing Iwssip， 2016： 234-239 od of PDE based on B-spline wavelet J Microelectronics Computers， 2012， 29（ 2） ： 184-187 11 李 艺珠，沈汀 非下 采样小波 域的四阶 偏微分 SA 图像 去 噪 J 遥感信息， 2016， 31（ 6） ： 95-99 LI Y Z， SHEN T SA image denoising using fourth-order PDE based on NSWT J emote Sensi

28、ng Information， 2016， 31 （ 6） ： 95-99 12 E GEN B Signal and image denoising using wavelet transform M Philippine： InTech， 2012： 496-511 13 KINGSBU Y N G The dual-tree complex wavelet transform： A new efficient tool for image restoration and enhancement C Proceeding of European Signal Processing Conf

29、erence hodes， 1998： 319-322 14 ANJANI J J， THI UVENGADAM S J Dual-tree complex wavelet transform based SA despeckling using interscale de- pendence J IEEE Transactions on Geoscience and emote Sensing， 2010 ， 48（ 6） ： 2723-2731 15 JAYANTHI S， ANGANATHAN H Denoising medical images using Q-shift comple

30、x wavelets J International Journal of Sci- ence and Applied Information Technology， 2014， 3（ 3） ： 36-40 16 MENG X Y， CHE L， LIU Z H， et al Towards a partial differ- ential equation remote sensing image method based on adaptive degradation diffusion parameter J Multimedia Tools Appli- cations， 2015，

31、3（ 3） ： 1-17 10 程东旭，郑玉晖，杨艳 基于 B 样条小 波的偏微 分方程图 像 去噪方法 J 微电子学与计算机， 2012， 29（ 2） ： 184-187 CHENG D X， ZHENG Y H， YANG Y Image de-noising meth- 17 ZHOU W， CON AD B Image quality assessment： From error visibility to structural similarity J IEEE Transactions on Im- age Processing， 2004， 14（ 4） ： 600-612 责

32、任编辑 王 净 檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵 檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵檵 （ 上接第 528 页） 参 考 文 献： 5 葛继科，邱玉辉 遗传算法 研究综述 J 计算机 应用研 究， 汤国安 刘学 军 数字高 程模 型及 地学 分析的 原理 与方 法 北京 科学出版社 TANG G A， LIU X J The principle and method of digital elevation Application esearch of Computers， 2008， 25（ 10） ： 2911-2916 model and geo-science an

33、alysis M Beijing： Science Press， 2005： 189-190 J地球信息科学学报， 2012， 14（ 6 ） ： 719-720 于宏亮 周明全 基于约束 三角网 的 构 建技 术研究 计算机应用与软 件 YU H L， ZHOU M Q Study of the construction of TIN based Journal of Geo-Information Science， 2012 ， 14（ 6） ： 719-720 on constrained D-triangulation J Computer Application and 7 HA I

34、NGTON P Machine learning in action M Greenwich， Software， 2008， 25（ 3） ： 228-229 CT， USA： Manning Publications Company， 2012： 116-133 韩海东 程承旗 基于全球剖分网格的多源数据快速汇集 方 法研究 地理信息世界 HAN H D， CHENG C Q apid collection method of multi- FAN J Y， WANG J Y， XIONG W Method for spatial object i- source data based o

35、n global subdivision grid J Geomatics dentification based on MPPQT J Journal of Geomatics Sci- World， 2014， 21（ 6） ： 6-11 ence and Technology， 2014， 31（ 1） ： 84 -88 王家耀 地图 学原理 与方法 北京 科 学出版 社 1-10 tional geometry， algorithms and applications M 2nd ed WANG J Y Principles and methods in cartography M B

36、ei- Berlin Heidelberd： Springer， 2000： 212-256 jing： Science Press， 2014： 1-10 责任编辑 王 净 2008， 25（ 10） ： 2911-2916 GE J K， QIU Y H Summary of genetic algorithms research J 6 ， ， ， LI M Z， XU Z， LI Z L， et al A hierarchical random graph based selection method for road network generalization J 8 范建永，王家耀，熊伟一种基于 MPPQT 的空间对象标 识编 码方法 J 测绘科学技术学报， 2014， 31（ 1） ： 84-88 9 BE G DE M， K EVELD VAN M， OVE MA S MComputa-