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

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

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

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.