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

doi:10.3724/SP.J.1047.2016.01052

摘要/Abstract

摘要：

栅格数据模型是地理信息科学领域的主要数据模型,成本距离分析是其重要的应用方向之一。但当栅格数据量较大时,传统的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

曲小康, 芮小平, 韩莹, 李祥琛, 伍彬. 栅格成本距离计算的改进蚁群算法[J]. 地球信息科学学报, 2016, 18(8): 1052-1059.DOI:10.3724/SP.J.1047.2016.01052

QU Xiaokang,RUI Xiaoping,HAN Ying,LI Xiangchen,WU Bin. A Method of Computing Raster Cost Distance Based on the Improved Ant Colony Algorithm[J]. Journal of Geo-information Science, 2016, 18(8): 1052-1059.DOI:10.3724/SP.J.1047.2016.01052

图/表 10

图1

图2

图3

图4

图5

图6

图7

图8

图9

图10

参考文献 19

[1]	秦昆,关泽群.基于栅格数据的最佳路径分析方法研究[J].国土资源遥感,2002,14(2):38-41. doi: 10.6046/gtzyyg.2002.02.09
	[ Qin K, Guan Z Q.The best route analysis based on raster data[J]. Remote Sensing for Land & Resources, 2002,14(2):38-41. ] doi: 10.6046/gtzyyg.2002.02.09
[2]	刘学锋,孟令奎,李少华,等.基于栅格GIS的最优路径分析及其应用[J].测绘通报,2004(6):43-45.
	[ Liu X F, Meng L K, Li S H, et al.A cheapest route analysis based on raster GIS and its application[J]. Bulletin of Surveying and Mapping, 2004,6:43-45. ]
[3]	Bagli S, Orsi F, Geneletti D.Routing of power lines through least-cost path analysis and multicriteria evaluation to minimise environmental impacts[J]. Environmental Impact Assessment Review, 2011,31(3):234-239. doi: 10.1016/j.eiar.2010.10.003
[4]	蔡青,曾光明,石林,等.基于栅格数据和图论算法的生态廊道识别[J].地理研究,2012,31(8):1523-1534. doi: 10.11821/yj2012080016
	[ Cai Q, Zeng G M, Shi L, et al.Identifying ecological corridors using shortest path algorithm based on raster data[J]. Geographical Research, 2012,31(8):1523-1534. ] doi: 10.11821/yj2012080016
[5]	郭金来,胡鹏.网络最短路径的地图代数栅格算法[J].测绘科学,2007,32(1):109-111,164. doi: 10.3771/j.issn.1009-2307.2007.01.042
	[ Guo J L, Hu P.Algorithms of shortest path for raster network based on map algebra[J]. Science of Surveying and Mapping, 2007,32(1):109-111,164. ] doi: 10.3771/j.issn.1009-2307.2007.01.042
[6]	厍向阳,史经俭,罗晓霞.栅格数据模型中附有条件的最短路径算法[J].计算机应用,2008,28(4):856-859.
	[ She X Y, Shi J J, Luo X X. Shortest path algorithm confined to conditions in grid data model[J]. Journal of Computer Applications, 2008,28(4):856-859. ]
[7]	Harri A.Using the hierarchical path finding A* algorithm in GIS to find paths through rasters with nonuniform traversal cost[J]. ISPRS International Journal of Geo-Information, 2014,2(4):996-1014. doi: 10.3390/ijgi2040996
[8]	李宁宁,刘玉树.改进的Dijkstra算法在GIS路径规划中的应用[J].计算机与现代化,2004,109(9):12-14,17. doi: 10.3969/j.issn.1006-2475.2004.09.004
	[ Li N N, Liu Y S.Application of modified dijkstra algorithm in GIS route planning[J].Computer and Modernization, 2004,109(9):12-14,17 ] doi: 10.3969/j.issn.1006-2475.2004.09.004
[9]	陈曦,谭冠政,江斌.基于免疫遗传算法的移动机器人实时最优路径规划[J].中南大学学报(自然科学版),2008,39(3):577-583.
	[ Chen X, Tan G Z, Jiang B.Real-time optimal path planning for mobile robots based on immune genetic algorithm[J]. Journal of Central South University (Natural Science Edition), 2008,39(3):577-583. ]
[10]	Eldrandaly K A.A modified artificial bee colony algorithm for solving least-cost path problem in raster GIS[J]. Applied Mathematics & Information Sciences, 2015,1:147-154. doi: 10.12785/amis/010119
[11]	Rishiwal V, Yadav M, Arya K V.Finding optimal paths on terrain maps using ant colony algorithm[J]. International Journal of Computer Theory and Engineering, 2010,2(3):416-419. doi: 10.7763/IJCTE.2010.V2.178
[12]	Colorni A, Maniezzo V, Dorigo M.Ant system: optimization by a colony of cooperating agents[J]. IEEE Systems, Man, and Cybernetics Society,1996,26(1):29-41. doi: 10.1109/3477.484436 pmid: 18263004
[13]	唐禹. 一种路径规划问题的蚁群算法研究[D].哈尔滨:哈尔滨工程大学,2013.
	[ Tang Y.A research on ant colony algorithm for path planning problem[D]. Harbin: Harbin Engineering University, 2013. ]
[14]	Sang P K, Yonsei U, Hyong S C.Genetic algorithm to find the shortest path on raster data[C]. 2014 International Conference on Control, Automation and Information Sciences (ICCAIS), 2014:144-147.
[15]	He J Q, Liu X P, Li X.Ant intelligence for solving optimal path-covering problems with multi-objectives[J]. International Journal of Geographical Information Science, 2009,23(7):839-857. doi: 10.1080/13658810802570309
[16]	Matei O, Pop P, Matei O.An efficient genetic algorithm for solving the generalized traveling salesman problem[C]. 2010 IEEE International Conference on Intelligent Computer Communication and Processing (ICCP), 2010:87-92.
[17]	詹士昌,徐婕,吴俊.蚁群算法中有关算法参数的最优选择[J].科技通报,2003(5):381-386.
	[ Zhan S C, Xu J, Wu J.The optimal selection on the parameters of the ant colony algorithm[J]. Bulletin of Science and Technology, 2003,5:381-386. ]
[18]	Yu C Q, Lee J, Mandy J, et al.Research article: extensions to least-cost path algorithms for roadway planning[J]. International Journal of Geographical Information Science, 2003,17(4):361-376. doi: 10.1080/1365881031000072645
[19]	Lu H, Zheng W J, Wang T B.An effective cost distance calculation based on raster data model improved algorithm[C]. 2011 International Conference on Computer Science and Network Technology (ICCSNT), 2011:2214-2218.