• 地球信息科学理论与方法 •

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

1. 中国科学院大学资源与环境学院,北京 100049
• 收稿日期:2015-08-05 修回日期:2015-12-18 出版日期:2016-08-10 发布日期:2016-08-10
• 作者简介:

作者简介：曲小康（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

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.