地球信息科学学报 ›› 2016, Vol. 18 ›› Issue (8): 1052-1059.doi: 10.3724/SP.J.1047.2016.01052

• 地球信息科学理论与方法 • 上一篇    下一篇

栅格成本距离计算的改进蚁群算法

曲小康(), 芮小平*(), 韩莹, 李祥琛, 伍彬   

  1. 中国科学院大学资源与环境学院,北京 100049
  • 收稿日期:2015-08-05 修回日期:2015-12-18 出版日期:2016-08-10 发布日期:2016-08-10
  • 通讯作者: 芮小平 E-mail:qxkang@126.com;ruixpsz@163.com
  • 作者简介:

    作者简介:曲小康(1989-),男,山东滨州人,硕士生,研究方向为基于地理信息系统的气象预警方法研究。E-mail:qxkang@126.com

  • 基金资助:
    国家海洋局海洋公益性行业科研专项(201205007-03);国家海洋局南北极环境综合考察与评估专项专题(CHINARE2014-02-04)

A Method of Computing Raster Cost Distance Based on the Improved Ant Colony Algorithm

QU Xiaokang(), RUI Xiaoping*(), HAN Ying, LI Xiangchen, WU Bin   

  1. College of Resource and Environment, University of Chinese Academy of Sciences, Beijing 100049, China
  • Received:2015-08-05 Revised:2015-12-18 Online:2016-08-10 Published:2016-08-10
  • Contact: RUI Xiaoping E-mail:qxkang@126.com;ruixpsz@163.com

摘要:

栅格数据模型是地理信息科学领域的主要数据模型,成本距离分析是其重要的应用方向之一。但当栅格数据量较大时,传统的Dijkstra求解效率较低,因此本文提出了一种用改进蚁群算法来求解栅格成本距离的方法。首先,构建了适合人工智能算法的栅格数据模型及编码方法;然后,在此基础上初始化蚁群,采用状态概率选择机制计算相邻栅格单元之间距离成本,以及距离成本路径方向选择,同时利用改进的信息素更新机制加强蚁群之间信息交流,加快算法收敛速度;最后,引入了遗传算法的选择、交叉和变异等算子优化生产的成本距离的解,增加解的全局性。本文以北极地区的海冰密集度栅格数据为基础,求解北极地区适合航行路线的成本距离。实验表明,结合了蚁群算法和遗传算法优势的改进蚁群算法,能够快速有效地求解出基于栅格数据的成本距离。

关键词: 栅格模型, 成本距离, 蚁群算法, 遗传算法

Abstract:

Raster data model is one of the primary data models applied in the geographical information science, and the cost distance analysis is an important application of the raster data model. When applying the traditional Dijkstra's algorithm or A* algorithm to solve the cost distance problems, it will be confronted with a high time complexity and low computational efficient if the data size is huge. In order to avoid the disadvantage of high time consumption, this paper proposed an improved ant colony algorithm (ACA) to compute the cost distance based on the raster data. In this work, firstly, we construct a new raster data model and a coding method, which meets the requirement of artificial intelligence algorithms. Secondly, the number of iterations and the size of ants were initialized, and the transition probability mechanism is used to calculate the cost between raster cells and to choose the direction of cost path. Meanwhile, the ants can associate with each other by adopting the pheromone updating strategy in the iteration process, so as to accelerate the convergence of the algorithm and attain the optimal result. Finally, the crossover operator of the genetic algorithm is introduced to the general ant colony algorithm, which expands the diversity of the solutions, improves the global superiority of the algorithm, and optimizes the result of the cost distance path. The experiment that computes the optimal Arctic sailing route cost, which adopts the Arctic raster data of sea ice concentration, is produced using the improved ant colony algorithm, the traditional Dijkstra's algorithm and the advanced A* algorithm respectively. The results indicate that, by combining the advantages of ant colony algorithm and genetic algorithm, the improved ant colony algorithm can quickly and effectively construct the optimal route and compute the total ice concentration cost of path based on the raster data with an overall better performance.

Key words: raster data model, cost distance, ant colony algorithm, genetic algorithm