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

地球信息科学理论与方法

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

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

中国科学院大学资源与环境学院,北京 100049

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

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

College of Resource and Environment, University of Chinese Academy of Sciences, Beijing 100049, China

通讯作者: *通讯作者：芮小平（1975-）,男,江苏苏州人,博士,副教授,研究方向为地理信息科学理论与应用。E-mail:ruixpsz@163.com

收稿日期: 2015-08-5

修回日期: 2015-12-18

网络出版日期: 2016-08-10

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

作者简介:

作者简介：曲小康（1989-）,男,山东滨州人,硕士生,研究方向为基于地理信息系统的气象预警方法研究。E-mail:qxkang@126.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.

Keywords： raster data model ; cost distance ; ant colony algorithm ; genetic algorithm

PDF (1562KB) 元数据多维度评价相关文章收藏文章

本文引用格式导出 EndNote Ris Bibtex

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

1 引言

基于栅格数据模型的成本距离分析是指使用DEM数据或其他栅格数据（栅格单元值代表成本消耗）,借助某些算法求解2个栅格单元之间的最优成本路径经过的栅格^[1]。基于栅格数据分析具有数据结构简单、无需建立复杂拓扑关系等特点,尤其是随着遥感技术的发展,能够实时获取大范围、高精度的栅格影像数据,并在大区域分析中广泛应用,如基于DEM地形数据的最优路径分析、天然气管线最优铺设线路、山区抢险道路选择,以及针对关键物种保护的生态廊道研究等^[2-4]。Dijkstra算法是经典的成本距离算法,其应用在栅格模型时,需要将每个栅格像元看作一个计算节点,其连接的节点为邻域栅格,通常为八邻域栅格。该算法将产生每个栅格节点到源节点的最优成本,造成了计算冗余,且其时间复杂度为O(N²),N为是栅格单元的数目,当处理大范围的栅格数据时,栅格单元数目会呈几何级增加,算法时间消耗也会急剧增加^[5-6]。目前,针对Dijkstra算法的不足,已有多种改进算法（如A^*算法等）。改进策略包括建立局部搜索矩阵,减少搜索规模,提供运行效率;从源点和终点同时搜索,寻找离两点都比较近的点;运用计算机并行计算的能力,同时对多个源点附近的栅格进行计算等,这些方法在一定程度上提高了算法效率^[7]。

近年来,智能优化算法得到了较大发展。在移动机器人路径规划方面,提出了基于栅格地图的遗传算法路径规划方法^[8-9];在栅格成本计算方面,提出了用改进蜂群算法求解最小成本消耗路径的方法,该方法主要引进了启发式的思想,通过模拟蜂群觅食行为得到较优路径,并对栅格邻域改进从而适合栅格数据模型,但该算法易陷入局部最优^[10]。其A^*算法是引入估值函数f(n)=g(n)+h(n)作为启发因素,提高了算法的效率,但是面对大的栅格数据,效率仍然较低,同时准确性也降低。本文将人工智能启发式思想引入栅格模型成本距离的计算,提出了一种改进的蚁群算法,用以解决大数据量栅格数据的距离成本计算问题,并通过仿真实验与传统的Dijkstra算法及较新的A^*算法比较,能够产生较好的结果,且效率明显高于Dijkstra算法,表明本算法具有可行性和优越性。

2 普通的蚁群算法

蚁群算法最早由M.Dorigo等提出,具有较好的并行及正反馈搜索机制。该算法受蚂蚁觅食行为的启发,把蚂蚁觅食过程看作是寻找路径的行为,通过蚂蚁释放的信息激素进行相互协作,从而找到蚁巢与食物之间最短路径,这与最优成本路径搜索原理相近^[11]。

2.1 栅格模型建立

首先,对所求问题的研究区进行建模,假设存在M行N列的栅格数据,如图1所示。构建一个适合人工智能算法的模型的过程如下。

显示原图| 下载原图ZIP| 生成PPT

图1 栅格地图模型

Fig. 1 Raster map model

（1）设该模型为M行N列矩阵V,其栅格值Value(i,j）表示具有一定实际意义的属性值,本文指通过该栅格消耗的成本（式（1））。

$\begin{matrix} Value (i, j) = \{\begin{matrix} V \begin{matrix} \end{matrix} \\ NoData \end{matrix} \begin{matrix} V \in [0,100] \\ 空值 \end{matrix} i \in [0, M], j \in [0, N] \end{matrix}$ （1）

（2）对每个栅格单元进行编码,栅格S(i,j）序号为C,则有式（2）。

$\begin{matrix} C = S (i, j) = N ∙ i + j (i \in [0, M], j \in [0, N]) \end{matrix}$ （2）

（3）每个栅格S(i, j)中心点（即路径节点）对应的直角坐标为(X, Y)如式（3）所示。

$\begin{matrix} \{\begin{matrix} X = \{\begin{matrix} \mod (C, N) \times a - \frac{a}{2} \begin{matrix} , & 若 \mod (C, N)! = 0 \end{matrix} \\ N \times a - \frac{a}{2} \begin{matrix} \begin{matrix} \begin{matrix} \begin{matrix} , \end{matrix} \end{matrix} \end{matrix} & 其它 \end{matrix} \end{matrix} \\ Y = \{\begin{matrix} Int (C, N) \times a + \frac{a}{2} \begin{matrix} , & 若 \mod (C, N)! = 0 \end{matrix} \\ N \times a - \frac{a}{2} \begin{matrix} \begin{matrix} \begin{matrix} \begin{matrix} , \end{matrix} \end{matrix} \end{matrix} & 其它 \end{matrix} \end{matrix} \end{matrix} \end{matrix}$ （3）

式中：mod为取余;Int为取整;a表示栅格单元的宽度或者高度。

（4）在二维的栅格模型中,每个S(i, j）栅格单元都可作为路径的一个节点,每个节点只有八邻域范围的栅格节点可通行。如图1标注的黄色栅格单元为S(3 , 2),其S(3, 2)可通行的栅格单元集合为{S(2 , 1), S(2 , 2), S(2 , 3), S(3 , 1), S(3, 3), S(4 , 1), S(4 , 2), S(4 , 3)},即为绿色标注的栅格区域。

（5）在计算成本距离时,将两相邻栅格中心点之间的距离作为栅格节点之间的距离,两节点 $\begin{matrix} C_{i} \end{matrix}$ 和 $\begin{matrix} C_{j} \end{matrix}$ 的之间的距离成本如式（4）所示。

$\begin{matrix} COST (C_{i}, C_{j}) = \{\begin{matrix} \frac{Cost (C_{i}) + Cost (C_{j})}{2} (C_{j} 为平行或者垂直节点) \\ \frac{[Cost (C_{i}) + Cost (C_{j})] \times \sqrt[]{2}}{2} (C_{j} 为对角线上节点) \end{matrix} \end{matrix}$ （4）

2.2 状态转移概率选择

在蚂蚁搜寻路径的过程中,会根据轮盘赌的方式选择下一个节点的位置,每个节点被选择的概率由两点路径上信息素浓度 $\begin{matrix} τ_{i, j} (t) \end{matrix}$ 和期望值 $\begin{matrix} η_{i, j} (t) \end{matrix}$ 决定^[12],求解概率的公式如式（5）-（6）所示。

$\begin{matrix} η_{i, j} {(t)}^{β} = \frac{Q}{D_{i, j}} \end{matrix}$ （6）

式中: $\begin{matrix} P_{i, j}^{k} (t) \end{matrix}$ 为状态转移概率。 $\begin{matrix} τ_{ij} (t) \end{matrix}$ 为节点 $\begin{matrix} C_{i} \end{matrix}$ 到节点 $\begin{matrix} C_{j} \end{matrix}$ 信息素,各边的初值为同一常数C。

$\begin{matrix} Allowe d_{k} \end{matrix}$ 为节点 $\begin{matrix} C_{i} \end{matrix}$ 周围8个节点中除了蚂蚁禁忌表节点外的集合,蚂蚁禁忌表节点是指蚂蚁已经走过的节点的集合。α为信息激素的启发因子,值越大表示蚂蚁倾向于其他蚂蚁选择的路径,蚂蚁之间的协作性越强。β为期望值的启发因子,表示期望值在选择概率中的重要性。 $\begin{matrix} η_{ij} (t) \end{matrix}$ 为期望启发函数,表示蚂蚁从节点i到节点j的期望程度,其值如式（6）所示。 $\begin{matrix} D_{i, j} \end{matrix}$ 为该蚂蚁节点 $\begin{matrix} C_{i} \end{matrix}$ 到节点 $\begin{matrix} C_{j} \end{matrix}$ 距离成本消耗,其值如式（4）所示;Q为控制因子。

2.3 信息激素更新

每当所有蚂蚁都完成一次搜素路径时,就要对成功寻到终点的蚂蚁所经过的路径进行信息激素全局更新,过去的信息激素逐渐消逝,增加新的信息激素^[12],其更新规则表达式为式（7）-（9）。

$\begin{matrix} τ_{ij} (k + 1) = (1 - ρ) τ_{ij} (k) + Δ τ_{ij} \end{matrix}$ （7）

$\begin{matrix} Δ τ_{ij} = \overset{N}{\sum_{m = 1}} τ_{ij}^{m} \end{matrix}$ （8）

$\begin{matrix} Δ τ_{i, j}^{m} = \{\begin{matrix} \frac{Q}{L_{m}} 若蚂蚁 m 在本次路径中经过了 (i, j) \\ 0 \end{matrix} \end{matrix}$ （9）

式中： $\begin{matrix} ρ \end{matrix}$ 表示信息素挥发系数; $\begin{matrix} 1 - ρ \end{matrix}$ 信息素残留因子,为防止信息的无限积累; $\begin{matrix} ρ \end{matrix}$ 的取值范围为[0 ,1]; $\begin{matrix} τ_{ij} (k) \end{matrix}$ 表示k时刻节点i,j间的信息素; $\begin{matrix} τ_{ij} (k + 1) \end{matrix}$ 表示为k+1时刻节点i,j间的信息素; $\begin{matrix} Δ τ_{ij} \end{matrix}$ 表示留在 $\begin{matrix} C_{i} \end{matrix}$ 与 $\begin{matrix} C_{j} \end{matrix}$ 之间路径上的信息素量。 $\begin{matrix} Δ τ_{i, j}^{m} \end{matrix}$ 表示第m蚂蚁留在 $\begin{matrix} C_{i} \end{matrix}$ 与 $\begin{matrix} C_{j} \end{matrix}$ 之间路径的上信息素增量; $\begin{matrix} L_{m} \end{matrix}$ 为第m只蚂蚁所寻成功路径的累积距离成本; $\begin{matrix} Q \end{matrix}$ 为常数。

3 改进的蚁群算法

由于普通的蚁群算法易陷入局部最优,当研究对象是较大规模的栅格数据时,会过早陷入局部最优,导致最终结果精度降低,因此需对其进行改进,使其适合较大区域栅格数据模型的路径搜索,得到较好的结果。

3.1 信息素更新

信息素大小直接影响了算法的收敛速度,过大会导致收敛较快,很可能使算法陷入局部最优而不是全局最优,过小则会导致收敛很慢,降低算法效率。信息素更新机制的改进主要引入了信息素最大上限 $\begin{matrix} τ_{\max} \end{matrix}$ 和最小下限 $\begin{matrix} τ_{\min} \end{matrix}$ 参数,信息素将在每次迭代更新后,限制在一定的范围,从而控制了算法的收敛速度。当信息素超过该范围时,将把信息素重置为一定比例的 $\begin{matrix} τ_{\max} \end{matrix}$ 或者 $\begin{matrix} τ_{\min} \end{matrix}$ ,从而改善信息素无限增加和值为零的不利情况,缩小不同路径之间信息素的差距,提高蚂蚁的搜索能力^[13]。另外,引入了全局更新与局部更新结合的更新机制,当每次迭代完成后都将最优路径上信息素进行更新,同时蚂蚁走一步之后,也要对走过的路径进行更新,这样更有利于扩大求解的范围。

3.2 融合遗传算法

遗传算法（Genetic Algorithm）由美国的J.Holland提出,是一种受生物进化启发的优化问题的随机优化方法,它基本求解过程为对解决问题的模型结构和参数进行编码,生成初始种群,再使用选择、交叉和变异等遗传算子操作,进行有组织而又随机的信息交换,从而在现优解的基础上产生更优的解^[14]。

遗传算法在搜索路径的过程中,具有内在的隐并行性和全局寻优能力,但是缺乏反馈机制,而蚁群算法具有反馈机制且效率较高,因此将遗传算法与蚁群算法融合中,充分利用2种算法的优势,可提高求解路径的全局性和高效性^[15-16]。在2种算法融合过程中,引入了遗传算法的选择算子、交叉算子、变异算子和修正算子。

（1）选择算子是复制操作,从父代种群中选择个体并原封不动地传递到子代。在复制的过程中,每一个个体被选中的概率与其适应度成正比,即父代按照一定的概率将父代的种群复制到后代,父代中适应度高的种群被传递到子代中的概率更大,对栅格成本计算,其适应度函数如式（10）-（11）所示。

$\begin{matrix} F = \frac{1}{(1 + \frac{1}{\sqrt[]{N - 1}}) \times Cost} \end{matrix}$ （10）

$\begin{matrix} Cost = \sum Cost (C_{i}, C_{j}) \end{matrix}$ （11）

式中：F为适应度函数;N表示路径所经过的栅格的数目;Cost为该路径所消耗的成本; $\begin{matrix} C_{i} \end{matrix}$ , $\begin{matrix} C_{j} \end{matrix}$ 为路径中所有相邻栅格节点。在式中引入N主要是为了尽量消除算法运行过程中所产生的间断点相距太远的过短路径。

（2）交叉算子即是将父代种群中2个个体随机结合,然后随机将他们的个体部分内容进行交换,从而产生2个新的个体,增加后代个体的多样性。对于栅格模型,交叉算子即是对每条路径栅格节点进行交换,产生新的栅格成本路径。其具体过程如下：蚁群完成一次迭代操作以后,会产生多条路径。将多条路径作为初始种群,对该种群按一定概率选择多条路径与其中最优路径进行交叉操作,从而产生多条新的路径,最后获取交叉之后的最优路径。

如图2所示,红色为染色体1,蓝色为染色体2,黄色为公共部分。2条染色体路径为染色体1（红色）,如图3所示,Cost=64。染色体2（蓝色）如图4所示,Cost=78。

显示原图| 下载原图ZIP| 生成PPT

图2 交叉操作的示意图

Fig. 2 Example of the crossover process

显示原图| 下载原图ZIP| 生成PPT

图3 染色体1

Fig. 3 Illustration of Chromosome 1

显示原图| 下载原图ZIP| 生成PPT

图4 染色体2

Fig. 4 Illustration of Chromosome 2

有2条父代染色体,选择(7,7)位置进行交叉操作,可产生适应度较大的染色体,绿色路线路径其Cost =58.7,该值比没有改进前成本更小,表明引进的遗传算法增加了解的全局性,产生了距离成本更优的解,但是由于遗传算法交叉操作的随机性,也可能产生较差的解,但整体上会优化最终距离成本的解。

（3）变异算子在增加种群多样性方面起关键作用。从结果路径多样性考虑,变异后的路径个体不必优于变异前的个体,依据给定的变异概率,随机选择个体中的一个栅格位置对象,进行变异操作。如图2中的染色体1（红色）,进行变异后可能变成新的染色体3,其路径如图5所示。图5可知原染色体1的位置（4,1）现已变为（3,2）。

显示原图| 下载原图ZIP| 生成PPT

图5 染色体3

Fig. 5 Illustration of Chromosome 3

（4）修正算子包括删除和插入操作。由于初始化的随机性及变异操作的突变性,路径种群的个体中可能会产生不可达栅格序号,并且交叉和变异等操作也可能会导致路径个体产生重复的栅格序号,因此需要将路径中不可达栅格或者重复栅格分别进行插入和删除操作,从而确保成本路径的正确性。可根据式（12）判断染色体中2个栅格( $\begin{matrix} x_{1} \end{matrix}$ , $\begin{matrix} y_{1} \end{matrix}$ ) $\begin{matrix} x_{1} \end{matrix}$ , $\begin{matrix} y_{1} \end{matrix}$ 与（ $\begin{matrix} x_{2} \end{matrix}$ , $\begin{matrix} y_{2} \end{matrix}$ ）相邻性,当 $\begin{matrix} Δ \end{matrix}$ 值大于1时,2个栅格不相邻,需要进行插入操作。

$\begin{matrix} Δ = \max {abs (x_{2} - x_{1}), abs (y_{2} - y_{1})} \end{matrix}$ （12）

如在第（3）步变异操作后,（3,2）与（5,2）之间不相邻,需要插入新的栅格（4,2）。在插入操作后还需要再进行一次重复操作,否则会影响适应度函数的计算。

3.3 改进蚁群算法实现流程

3.3.1 初始化栅格地图模型

获取栅格数据单元值,根据栅格数据的行列值,构建二维的矩阵模型。初始化蚂蚁数量N,最大迭代次数T、起始和终止栅格的位置以及路径上的信息激素初始值等各项全局参数^[17]。

3.3.2 改进后蚁群算法

其具体步骤为：

（1）把蚂蚁m（m= 1,2,…,N）放到初始位置,并把初始位置加入到每个蚂蚁的禁忌表。

（2）根据状态转移概率公式,结合轮盘赌的方式将蚂蚁m移动到下一个节点,修改禁忌表,如此循环,直至蚂蚁没可选节点或找到终止栅格。若成功搜索到终止位置,该蚂蚁的标记为1,若未寻到或陷入无路可走,则蚂蚁标记为2,初始标记为0。每次选择下一节点时,都要进行信息素的局部更新。

（3）若m< N,令m =m +1,继续返回执行步骤（1）,否则执行步骤（2）。

（4）当m = N时,此次迭代完成,然后对所有蚂蚁产生的成功路径进行融合遗传算法的操作（图6）。

显示原图| 下载原图ZIP| 生成PPT

图6 算法流程图

Fig. 6 The flowchart of the algorithm

①将该次迭代产生的成功路径初始化为遗传算法的父代种群,设置交叉概率 $\begin{matrix} P_{c} \end{matrix}$ 和变异概率 $\begin{matrix} P_{m} \end{matrix}$ 值,以及迭代次数N。

②计算父代种群的适应度函数,按照轮盘赌选择的方式,根据累积概率数组,从父代中选择种群个体直接复制到后代种群中,不进行任何操作。

③父代种群依照交叉概率 $\begin{matrix} P_{c} \end{matrix}$ 执行交叉操作,依照变异概率 $\begin{matrix} P_{m} \end{matrix}$ 执行变异操作。

④当交叉和变异完成之后,进行插入和删除操作,直到子代中所有个体都成为可行路径。该子代将作为下一次循环的父代重复步骤②-④,直至达到设定的循环过程。

该遗传算法过程将会产生最优路径,对最优路径进行信息素的全局更新。将这次循环产生的最优路径与全局最优路径进行对比,保留二者之间的最优路径,作为全局最优路径。

（5）若迭代次数k < K,则k=k+1,令蚂蚁的禁忌表为空,且返回初始位置,m =1,执行步骤（2）。

（6）搜索路径结束,输出最优路径及消耗的成本。

3.3.3 路径渲染

根据最优路径的位置描述,运用GIS技术,渲染最优路径经过的栅格并将该路径转换为矢量数据,从而直观的展现最优路径。

4 仿真实验

本文用C#及ArcGIS Engine对Dijkstra算法、A^*算和改进蚁群算法进行了实现。在仿真实验中,采用北极地区AMSR-E的海冰密度产品,其分辨率为6.25 km×6.25 km。探索北极地区的航行成本最小路径时,选取了150×100栅格区域,其海冰密集度越小（即栅格像元值越小）,越易于通行,航行成本也越小（即有利于形成航道）,是航道倾向集中的地方^[16]。

在改进蚁群算法中初始蚂蚁个数及最大迭代次数是算法时间消耗成本的2个主要因素,仿真实现了对2个参数模拟,选出了适合该实验的参数值。结果如图7所示,迭代次数与蚂蚁个数都与成本消耗成反比,而与时间消耗成正比,当蚂蚁个数一定时,随着迭代次数增加,成本消耗显著减小,时间消耗显著增加,但当迭代次数一定时,蚂蚁增加对成本消耗没有显著影响,但时间消耗却显著增加。结合成本和时间曲线,本次仿真实验中初始蚂蚁个数为30,迭代次数为150。

图8为Dijkstra算法、A^*算法和改进蚁群算法生成的路径结果。红色表示Dijkstra算法生成路径,蓝色表示改进蚁群算法生成路径,2条路径的走向相近,表示2者成功实现了路径的求解,而A^*算法（绿色）则与前2种算法前部分比较相近,后半路程的有些偏差,生成效果较差。为了加强成本和时间的对比性,本文又选取了250×200、350×300和500×500不同范围的数据进行测试,结果如图9、10所示。在航行成本消耗方面,3种算法的航行成本比较接近,Dijkstra算法略低于其他的算法航行成本。在时间消耗方面,改进蚁群算法的时间消耗明显低于传统的Dijkstra算法,且比A^*算法有很大的提高,而且随着栅格数量的增加,改进蚁群算法的时间增加较慢,其他2个算法迅速增加,可见改进蚁群算法的时间优势很明显。从算法本身分析,改进蚁群算法的时间复杂度为O(N^*M^*T/2)（N为栅格个数,M为蚂蚁个数,T为迭代次数）,而Dijkstra算法时间复杂度为O(N²)（N为栅格个数）,A^*算法的时间复杂度为O(N^*logN)。当处理范围较大时,栅格数量也急剧增加,对于改进蚁群算法,当固定了M,T参数后,其时间复杂度与N值呈线性关系,但Dijkstra算法时间复杂度与N成幂函数关系,A^*算法的时间复杂度则介于蚁群算法和Dijkstra算法之间,所以改进蚁群算法时间效率明显高于Dijkstra算法及改进后的A^*算法^[18]。由图8也可以看出蚁群算法拐点数目较少,说明改进蚁群算法形成的路径更符合实际路线。

显示原图| 下载原图ZIP| 生成PPT

图7 不同蚂蚁个数和迭代次数下距离成本结果和时间消耗

Fig. 7 Comparison of time and cost consumptions in different conditions

显示原图| 下载原图ZIP| 生成PPT

图8 不同算法的结果注：蓝色表示Dijkstra生成路径;绿色表示A^*算法生成路径;红色表示改进蚁群算法生成路径;蓝色圆点为路径起点;红色圆点为路径终点

Fig. 8 The results of different algorithms

显示原图| 下载原图ZIP| 生成PPT

图9 不同算法的消耗成本对比

Fig. 9 Comparison of cost consumptionin different algorithms

显示原图| 下载原图ZIP| 生成PPT

图10 不同算法的消耗时间对比

Fig. 10 Comparison of time consumptionin different algorithms

5 结论

近年来,随着地理信息技术的发展,基于大尺度的地形、植被等栅格数据的最优路径分析在复杂地形的路线规划、森林火灾蔓延及动物迁移等路径分析中显示出了越来越重要的应用价值。本文针对经典栅格模型成本距离算法时间消耗大的问题,将人工智能算法引入到栅格模型距离成本计算中,提出了一种用蚁群算法计算最优成本的方法;结合遗传算法搜索结果全局性的优势对该算法进行了改进,将遗传算法中的选择、交叉、变异等算子用到了蚁群算法求解路径的过程中^[18-19],并采用北极地区海冰密集度栅格数据对改进算法实现了2点最优路径求解;与Dijkstra算法及A^*算法生成路径进行对比,结果表明该算法具有可行性和高效性。在最优成本路径基本相似的情况下,本算法具有较好的时间效率,并且理论上当处理更大面积的栅格数据时,其时间优势将会更加明显,是用于求解基于栅格模型的最优成本路径的有效方法。

但本文提出的改进蚁群算法采用了启发式思想,是一种智能优化算法,其获取的结果较优,但不是最优,在提升效率同时也会一定程度上降低结果的精确性。当解决实际问题时,需要综合考虑时间成本与结果准确性的关系,改进的蚁群算法在对大尺度的栅格成本计算方面有明显优势,对于北极地区大尺度范围航道规划,实验结果较好。而在路径生成过程中,本文仿真实验只考虑了单一的栅格成本因子,为了增加生成路径的可行性,今后研究中应考虑多种路径影响因素的栅格数据作为距离成本,从而使其更符合实际的情况。

The authors have declared that no competing interests exist.

参考文献

原文顺序

文献年度倒序

文中引用次数倒序

被引期刊影响因子

[1]	秦昆,关泽群. 基于栅格数据的最佳路径分析方法研究 [J].国土资源遥感,2002,14(2):38-41. https://doi.org/10.6046/gtzyyg.2002.02.09 Magsci [本文引用: 1] 摘要讨论了基于栅格数据的最佳路径分析方法。该方法利用Dijikstra算法的基本思想和“节点/联系”模型,首先通过8邻域像元算出每个像元到源像元的最小权距离,然后计算后向连接值,最后根据累积权距离栅格和后向连接栅格计算出最佳路径。本文结合实例讲述了应用Arc/Info的GRID模块进行最佳路径分析的方法和步骤,并提出了改进算法的研究思路。 [ Qin K, Guan Z Q. The best route analysis based on raster data [J]. Remote Sensing for Land & Resources, 2002,14(2):38-41. ] https://doi.org/10.6046/gtzyyg.2002.02.09 Magsci [本文引用: 1] 摘要讨论了基于栅格数据的最佳路径分析方法。该方法利用Dijikstra算法的基本思想和“节点/联系”模型,首先通过8邻域像元算出每个像元到源像元的最小权距离,然后计算后向连接值,最后根据累积权距离栅格和后向连接栅格计算出最佳路径。本文结合实例讲述了应用Arc/Info的GRID模块进行最佳路径分析的方法和步骤,并提出了改进算法的研究思路。
[2]	刘学锋,孟令奎,李少华,等. 基于栅格GIS的最优路径分析及其应用 [J].测绘通报,2004(6):43-45. URL Magsci [本文引用: 1] 摘要最优路径分析是在移动的起点和终点之间寻找最佳的移动线路,对于旅行中的最短路径确定、工程设计中连接两地之间的线状设施(如输电线路、输油气管线等)的最佳布局规划等具有重要意义.阐述基于栅格的最优路径分析的基本原理,提出基于栅格的最优路径分析的一般过程,并以某地天然气管线最佳铺设线路为例说明基于栅格的最优路径分析的具体应用. [ 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. ] URL Magsci [本文引用: 1] 摘要最优路径分析是在移动的起点和终点之间寻找最佳的移动线路,对于旅行中的最短路径确定、工程设计中连接两地之间的线状设施(如输电线路、输油气管线等)的最佳布局规划等具有重要意义.阐述基于栅格的最优路径分析的基本原理,提出基于栅格的最优路径分析的一般过程,并以某地天然气管线最佳铺设线路为例说明基于栅格的最优路径分析的具体应用.
[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. https://doi.org/10.1016/j.eiar.2010.10.003 URL Magsci 摘要 Least-cost path analysis (LCPA) allows designers to find the "cheapest" way to connect two locations within a cost surface, which can be computed by combining multiple criteria, and therefore by accounting for different issues (environmental impact, economic investment, etc.). This procedure can be easily implemented with modern Geographic Information System (GIS) technologies, and consequently it has been widely employed to support planning and design of different types of linear infrastructures, ranging from roads to pipelines. This paper presents an approach based on the integration of multicriteria evaluation (MCE) and LCPA to identify the most suitable route for a 132 kV power line. Criteria such as cost, visibility, population density, and ecosystem naturalness were used for the analysis. Firstly, spatial MCE and LCPA were combined to generate cost surfaces, and to identify alternative paths. Subsequently, MCE was used to compare the alternatives, and rank them according to their overall suitability. Finally, a sensitivity analysis allowed the stability of the results to be tested and the most critical factors of the evaluation to be detected. The study found that small changes in the location of the power line start and end points can result in significantly different paths, and consequently impact levels. This suggested that planners should always consider alternative potential locations of terminals in order to identify the best path. Furthermore, it was shown that the use of different weight scenarios may help making the model adaptable to varying environmental and social contexts. The approach was tested on a real-world case study in north-eastern Italy. (C) 2010 Elsevier Inc. All rights reserved.
[4]	蔡青,曾光明,石林,等. 基于栅格数据和图论算法的生态廊道识别 [J].地理研究,2012,31(8):1523-1534. https://doi.org/10.11821/yj2012080016 URL Magsci [本文引用: 1] 摘要利用图论中最短路算法思想和ArcGIS的空间分析功能,对生境中动物迁徙廊道的识别与构建进行研究。通过对具有不同空间自相关特征的模拟景观进行分析,发现该方法具有较好的适应性,能识别出不同类型模拟景观的廊道。在模拟景观分析的基础上,将该算法应用于长沙市大河西先导区,计算了先导区重要栖息地之间的廊道。研究表明该计算方法提取的生态廊道具有明显的冗余性,充分反映了物种在不同栖息地之间迁徙的需求,具有一定的生态学意义。同时廊道提取结果在一定程度上反映了城市发展对生态系统尤其是生态廊道的胁迫与挤占。通过对廊道空间结构的分析还发现生态廊道存在一定的瓶颈区域,对该区域的生态恢复与重建将对物种多样性的保持起到关键作用。该方法为区域土地管理以及生态环境保护规划提供一定的科学依据。 [ 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. ] https://doi.org/10.11821/yj2012080016 URL Magsci [本文引用: 1] 摘要利用图论中最短路算法思想和ArcGIS的空间分析功能,对生境中动物迁徙廊道的识别与构建进行研究。通过对具有不同空间自相关特征的模拟景观进行分析,发现该方法具有较好的适应性,能识别出不同类型模拟景观的廊道。在模拟景观分析的基础上,将该算法应用于长沙市大河西先导区,计算了先导区重要栖息地之间的廊道。研究表明该计算方法提取的生态廊道具有明显的冗余性,充分反映了物种在不同栖息地之间迁徙的需求,具有一定的生态学意义。同时廊道提取结果在一定程度上反映了城市发展对生态系统尤其是生态廊道的胁迫与挤占。通过对廊道空间结构的分析还发现生态廊道存在一定的瓶颈区域,对该区域的生态恢复与重建将对物种多样性的保持起到关键作用。该方法为区域土地管理以及生态环境保护规划提供一定的科学依据。
[5]	郭金来,胡鹏. 网络最短路径的地图代数栅格算法 [J].测绘科学,2007,32(1):109-111,164. https://doi.org/10.3771/j.issn.1009-2307.2007.01.042 URL [本文引用: 1] 摘要在阐述网络分析和最短路径算法的现状的基础上,以地图代数为理论支撑,介绍了地图代数对于网络元素的表达,探讨另外一种途径的网络最短路径分析—基于栅格数据的最短路径分析,重点讨论了基于地图代数的网络数据模型、栅格路径距离计算方法,在此基础上论述了求取最短路径的栅格方法的具体过程。最后,通过算例证明栅格途径的网络分析有其独特的优势。 [ 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. ] https://doi.org/10.3771/j.issn.1009-2307.2007.01.042 URL [本文引用: 1] 摘要在阐述网络分析和最短路径算法的现状的基础上,以地图代数为理论支撑,介绍了地图代数对于网络元素的表达,探讨另外一种途径的网络最短路径分析—基于栅格数据的最短路径分析,重点讨论了基于地图代数的网络数据模型、栅格路径距离计算方法,在此基础上论述了求取最短路径的栅格方法的具体过程。最后,通过算例证明栅格途径的网络分析有其独特的优势。
[6]	厍向阳,史经俭,罗晓霞. 栅格数据模型中附有条件的最短路径算法 [J].计算机应用,2008,28(4):856-859. URL Magsci [本文引用: 1] 摘要将附有条件的最短路径概括为点约束、边约束和属性约束的最短路径问题。以栅格数据模型为图或网络描述方式，基于贪心算法思想，提出栅格数据模型中附有条件的最短路径算法。最后，通过实例进行了算法测试，结果表明栅格数据模型中附有条件的最短路径算法是完全可行和有效的。 [ 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. ] URL Magsci [本文引用: 1] 摘要将附有条件的最短路径概括为点约束、边约束和属性约束的最短路径问题。以栅格数据模型为图或网络描述方式，基于贪心算法思想，提出栅格数据模型中附有条件的最短路径算法。最后，通过实例进行了算法测试，结果表明栅格数据模型中附有条件的最短路径算法是完全可行和有效的。
[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. https://doi.org/10.3390/ijgi2040996 URL [本文引用: 1] 摘要 Not Available
[8]	李宁宁,刘玉树. 改进的Dijkstra算法在GIS路径规划中的应用 [J].计算机与现代化,2004,109(9):12-14,17. https://doi.org/10.3969/j.issn.1006-2475.2004.09.004 URL [本文引用: 1] 摘要最短路径算法是计算机科学与地理信息科学等领域研究的热点。文章讨论了一种改进的Dijkstra算法,利用本算法根据用户给出的起始结点、必经点序列和目标结点在GIS的交通层网络图基础上进行路径规划,生成满足一定约束条件的最短路径。实际应用分析表明,改进的Dijkstra算法在提高网络系统空间分析效率方面是可行的。 [ 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 ] https://doi.org/10.3969/j.issn.1006-2475.2004.09.004 URL [本文引用: 1] 摘要最短路径算法是计算机科学与地理信息科学等领域研究的热点。文章讨论了一种改进的Dijkstra算法,利用本算法根据用户给出的起始结点、必经点序列和目标结点在GIS的交通层网络图基础上进行路径规划,生成满足一定约束条件的最短路径。实际应用分析表明,改进的Dijkstra算法在提高网络系统空间分析效率方面是可行的。
[9]	陈曦,谭冠政,江斌. 基于免疫遗传算法的移动机器人实时最优路径规划 [J].中南大学学报(自然科学版),2008,39(3):577-583. URL [本文引用: 1] 摘要以具有精英保留的免疫遗传算法(Immune genetic algorithm with elitism,IGAE)和栅格法为基础,提出一种新的移动机器人最优路径规划方法。其步骤为:首先采用栅格法对机器人工作空间进行划分,建立给定环境中移动机器人的自由空间模型;每个栅格用1个序号标识,并以路径上各栅格序号作为机器人路径的编码参数。然后,采用直角坐标和序号混合应用的方法产生初始种群,群体中每1个个体表示1条机器人路径,采用IGAE算法对种群进行优化,最终找出最优路径。为了保持种群初始化和遗传操作过程中个体所对应的路径的连续性和避障要求,在IGAE算法中引入删除、插入算子。计算机仿真实验结果表明,所提出的方法比基于全局收敛型遗传算法的路径规划方法更加快速和有效。 [ 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. ] URL [本文引用: 1] 摘要以具有精英保留的免疫遗传算法(Immune genetic algorithm with elitism,IGAE)和栅格法为基础,提出一种新的移动机器人最优路径规划方法。其步骤为:首先采用栅格法对机器人工作空间进行划分,建立给定环境中移动机器人的自由空间模型;每个栅格用1个序号标识,并以路径上各栅格序号作为机器人路径的编码参数。然后,采用直角坐标和序号混合应用的方法产生初始种群,群体中每1个个体表示1条机器人路径,采用IGAE算法对种群进行优化,最终找出最优路径。为了保持种群初始化和遗传操作过程中个体所对应的路径的连续性和避障要求,在IGAE算法中引入删除、插入算子。计算机仿真实验结果表明,所提出的方法比基于全局收敛型遗传算法的路径规划方法更加快速和有效。
[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. https://doi.org/10.12785/amis/010119 URL [本文引用: 1] 摘要 The computation of least-cost paths over a cost surface is a well-known and widely used capability of raster geographic information systems (GISs). It consists of finding the path with the lowest accumulated cost between two locations in a raster model of a cost surface. This paper presents a modified Artificial Bee Colony (ABC) algorithm for solving least-cost path problem in a raster-based GIS. This modification includes the incorporation of a distinct feature which is not present in the classical ABC. A new component, the direction guidance search method, is used to guide a bee walking toward the final destination more efficiently. In addition, this paper examines how the quality of the raster-based paths can be improved by using larger connectivity patterns. The experimental results show that the performance of the modified ABC model is quite close to Dijkstra’s algorithm while its computational complexity and solution time is much lower than Dijkstra’s algorithm. The results also, indicate that raster-based paths can be improved by using larger connectivity patterns.
[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. https://doi.org/10.7763/IJCTE.2010.V2.178 URL [本文引用: 1] 摘要 Abstract-This paper presents the meta-heuristic method of ant colony optimization (ACO) to find optimal paths on terrain map images. The procedure simulates decision-making process of ant colonies as they forage for food. Modifications have been made to the ACO
[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. https://doi.org/10.1109/3477.484436 URL PMID: 18263004 [本文引用: 2] 摘要 An analogy with the way ant colonies function has suggested the definition of a new computational paradigm, which we call ant system (AS). We propose it as a viable new approach to stochastic combinatorial optimization. The main characteristics of th...
[13]	唐禹. 一种路径规划问题的蚁群算法研究[D] .哈尔滨:哈尔滨工程大学,2013. [本文引用: 1] [ Tang Y. A research on ant colony algorithm for path planning problem[D]. Harbin: Harbin Engineering University, 2013. ] [本文引用: 1]
[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. [本文引用: 1]
[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. https://doi.org/10.1080/13658810802570309 URL [本文引用: 1] 摘要 Conventional methods have difficulties in forming optimal paths when raster data are used and multi-objectives are involved. This paper presents a new method of using ant colony optimization (ACO) for solving optimal path-covering problems on unstructured raster surfaces. The novelty of this proposed ACO includes the incorporation of a couple of distinct features which are not present in classical ACO. A new component, the direction function, is used to represent the 'visibility' in the path exploration. This function is to guide an ant walking toward the final destination more efficiently. Moreover, a utility function is proposed to reflect the multi-objectives in planning applications. Experiments have shown that classical ACO cannot be used to solve this type of path optimization problems. The proposed ACO model can generate near optimal solutions by using hypothetical data in which the optimal solutions are known. This model can also find the near optimal solutions for the real data set with a good convergence rate. It can yield much higher utility values compared with other common conventional models.
[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. [本文引用: 2]
[17]	詹士昌,徐婕,吴俊. 蚁群算法中有关算法参数的最优选择 [J].科技通报,2003(5):381-386. URL Magsci [本文引用: 1] 摘要蚁群算法是一种模拟进化算法,初步的研究表明该算法具有许多优良的性质.本文介绍了蚁群算法基本模型AS(Ant System)的原理、特点、构成和实现方法,对基本蚁群算法参数的合理选取进行了实验分析,给出了算法参数选取的基本原则,有利于蚁群算法在优化问题中的推广和应用. [ 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. ] URL Magsci [本文引用: 1] 摘要蚁群算法是一种模拟进化算法,初步的研究表明该算法具有许多优良的性质.本文介绍了蚁群算法基本模型AS(Ant System)的原理、特点、构成和实现方法,对基本蚁群算法参数的合理选取进行了实验分析,给出了算法参数选取的基本原则,有利于蚁群算法在优化问题中的推广和应用.
[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. https://doi.org/10.1080/1365881031000072645 URL [本文引用: 2] 摘要 Finding a least-cost-path in a raster data format is a useful function in geographical information systems. However, existing algorithms are often inadequate for practical roadway planning. This paper improves conventional algorithms by including the considerations of spatial distances, anisotropic costs and the presence of bridges and tunnels in the paths. This new algorithm is implemented in JAVA to run with actual remote sensing and DEM data. The experimental results show that this approach produces realistic least-cost paths for practical roadway planning.
[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. [本文引用: 1]

基于栅格数据的最佳路径分析方法研究

2002

... 基于栅格数据模型的成本距离分析是指使用DEM数据或其他栅格数据（栅格单元值代表成本消耗）,借助某些算法求解2个栅格单元之间的最优成本路径经过的栅格^[1].基于栅格数据分析具有数据结构简单、无需建立复杂拓扑关系等特点,尤其是随着遥感技术的发展,能够实时获取大范围、高精度的栅格影像数据,并在大区域分析中广泛应用,如基于DEM地形数据的最优路径分析、天然气管线最优铺设线路、山区抢险道路选择,以及针对关键物种保护的生态廊道研究等^[2-4].Dijkstra算法是经典的成本距离算法,其应用在栅格模型时,需要将每个栅格像元看作一个计算节点,其连接的节点为邻域栅格,通常为八邻域栅格.该算法将产生每个栅格节点到源节点的最优成本,造成了计算冗余,且其时间复杂度为O(N²),N为是栅格单元的数目,当处理大范围的栅格数据时,栅格单元数目会呈几何级增加,算法时间消耗也会急剧增加^[5-6].目前,针对Dijkstra算法的不足,已有多种改进算法（如A^*算法等）.改进策略包括建立局部搜索矩阵,减少搜索规模,提供运行效率;从源点和终点同时搜索,寻找离两点都比较近的点;运用计算机并行计算的能力,同时对多个源点附近的栅格进行计算等,这些方法在一定程度上提高了算法效率^[7]. ...

基于栅格数据的最佳路径分析方法研究

2002

基于栅格GIS的最优路径分析及其应用

2004

基于栅格GIS的最优路径分析及其应用

2004

Routing of power lines through least-cost path analysis and multicriteria evaluation to minimise environmental impacts

2011

基于栅格数据和图论算法的生态廊道识别

2012

基于栅格数据和图论算法的生态廊道识别

2012

网络最短路径的地图代数栅格算法

2007

网络最短路径的地图代数栅格算法

2007

栅格数据模型中附有条件的最短路径算法

2008

栅格数据模型中附有条件的最短路径算法

2008

Using the hierarchical path finding A* algorithm in GIS to find paths through rasters with nonuniform traversal cost

2014

改进的Dijkstra算法在GIS路径规划中的应用

2004

... 近年来,智能优化算法得到了较大发展.在移动机器人路径规划方面,提出了基于栅格地图的遗传算法路径规划方法^[8-9];在栅格成本计算方面,提出了用改进蜂群算法求解最小成本消耗路径的方法,该方法主要引进了启发式的思想,通过模拟蜂群觅食行为得到较优路径,并对栅格邻域改进从而适合栅格数据模型,但该算法易陷入局部最优^[10].其A^*算法是引入估值函数f(n)=g(n)+h(n)作为启发因素,提高了算法的效率,但是面对大的栅格数据,效率仍然较低,同时准确性也降低.本文将人工智能启发式思想引入栅格模型成本距离的计算,提出了一种改进的蚁群算法,用以解决大数据量栅格数据的距离成本计算问题,并通过仿真实验与传统的Dijkstra算法及较新的A^*算法比较,能够产生较好的结果,且效率明显高于Dijkstra算法,表明本算法具有可行性和优越性. ...

改进的Dijkstra算法在GIS路径规划中的应用

2004

基于免疫遗传算法的移动机器人实时最优路径规划

2008

基于免疫遗传算法的移动机器人实时最优路径规划

2008

A modified artificial bee colony algorithm for solving least-cost path problem in raster GIS

2015

Finding optimal paths on terrain maps using ant colony algorithm

2010

... 蚁群算法最早由M.Dorigo等提出,具有较好的并行及正反馈搜索机制.该算法受蚂蚁觅食行为的启发,把蚂蚁觅食过程看作是寻找路径的行为,通过蚂蚁释放的信息激素进行相互协作,从而找到蚁巢与食物之间最短路径,这与最优成本路径搜索原理相近^[11]. ...

Ant system: optimization by a colony of cooperating agents

1996

... 在蚂蚁搜寻路径的过程中,会根据轮盘赌的方式选择下一个节点的位置,每个节点被选择的概率由两点路径上信息素浓度

\begin{matrix} τ_{i, j} (t) \end{matrix}

和期望值

\begin{matrix} η_{i, j} (t) \end{matrix}

决定^[12],求解概率的公式如式（5）-（6）所示. ...

... 每当所有蚂蚁都完成一次搜素路径时,就要对成功寻到终点的蚂蚁所经过的路径进行信息激素全局更新,过去的信息激素逐渐消逝,增加新的信息激素^[12],其更新规则表达式为式（7）-（9）. ...

一种路径规划问题的蚁群算法研究[D]

2013

... 信息素大小直接影响了算法的收敛速度,过大会导致收敛较快,很可能使算法陷入局部最优而不是全局最优,过小则会导致收敛很慢,降低算法效率.信息素更新机制的改进主要引入了信息素最大上限

\begin{matrix} τ_{\max} \end{matrix}

和最小下限

\begin{matrix} τ_{\min} \end{matrix}

参数,信息素将在每次迭代更新后,限制在一定的范围,从而控制了算法的收敛速度.当信息素超过该范围时,将把信息素重置为一定比例的

\begin{matrix} τ_{\max} \end{matrix}

或者

\begin{matrix} τ_{\min} \end{matrix}

,从而改善信息素无限增加和值为零的不利情况,缩小不同路径之间信息素的差距,提高蚂蚁的搜索能力^[13].另外,引入了全局更新与局部更新结合的更新机制,当每次迭代完成后都将最优路径上信息素进行更新,同时蚂蚁走一步之后,也要对走过的路径进行更新,这样更有利于扩大求解的范围. ...

一种路径规划问题的蚁群算法研究[D]

2013

\begin{matrix} τ_{\max} \end{matrix}

和最小下限

\begin{matrix} τ_{\min} \end{matrix}

参数,信息素将在每次迭代更新后,限制在一定的范围,从而控制了算法的收敛速度.当信息素超过该范围时,将把信息素重置为一定比例的

\begin{matrix} τ_{\max} \end{matrix}

或者

\begin{matrix} τ_{\min} \end{matrix}

Genetic algorithm to find the shortest path on raster data

2014

... 遗传算法（Genetic Algorithm）由美国的J.Holland提出,是一种受生物进化启发的优化问题的随机优化方法,它基本求解过程为对解决问题的模型结构和参数进行编码,生成初始种群,再使用选择、交叉和变异等遗传算子操作,进行有组织而又随机的信息交换,从而在现优解的基础上产生更优的解^[14]. ...

Ant intelligence for solving optimal path-covering problems with multi-objectives

2009

... 遗传算法在搜索路径的过程中,具有内在的隐并行性和全局寻优能力,但是缺乏反馈机制,而蚁群算法具有反馈机制且效率较高,因此将遗传算法与蚁群算法融合中,充分利用2种算法的优势,可提高求解路径的全局性和高效性^[15-16].在2种算法融合过程中,引入了遗传算法的选择算子、交叉算子、变异算子和修正算子. ...

An efficient genetic algorithm for solving the generalized traveling salesman problem

2010

... 本文用C#及ArcGIS Engine对Dijkstra算法、A^*算和改进蚁群算法进行了实现.在仿真实验中,采用北极地区AMSR-E的海冰密度产品,其分辨率为6.25 km×6.25 km.探索北极地区的航行成本最小路径时,选取了150×100栅格区域,其海冰密集度越小（即栅格像元值越小）,越易于通行,航行成本也越小（即有利于形成航道）,是航道倾向集中的地方^[16]. ...

蚁群算法中有关算法参数的最优选择

2003

... 获取栅格数据单元值,根据栅格数据的行列值,构建二维的矩阵模型.初始化蚂蚁数量N,最大迭代次数T、起始和终止栅格的位置以及路径上的信息激素初始值等各项全局参数^[17]. ...

蚁群算法中有关算法参数的最优选择

2003

Research article: extensions to least-cost path algorithms for roadway planning

2003

... 图8为Dijkstra算法、A^*算法和改进蚁群算法生成的路径结果.红色表示Dijkstra算法生成路径,蓝色表示改进蚁群算法生成路径,2条路径的走向相近,表示2者成功实现了路径的求解,而A^*算法（绿色）则与前2种算法前部分比较相近,后半路程的有些偏差,生成效果较差.为了加强成本和时间的对比性,本文又选取了250×200、350×300和500×500不同范围的数据进行测试,结果如图9、10所示.在航行成本消耗方面,3种算法的航行成本比较接近,Dijkstra算法略低于其他的算法航行成本.在时间消耗方面,改进蚁群算法的时间消耗明显低于传统的Dijkstra算法,且比A^*算法有很大的提高,而且随着栅格数量的增加,改进蚁群算法的时间增加较慢,其他2个算法迅速增加,可见改进蚁群算法的时间优势很明显.从算法本身分析,改进蚁群算法的时间复杂度为O(N^*M^*T/2)（N为栅格个数,M为蚂蚁个数,T为迭代次数）,而Dijkstra算法时间复杂度为O(N²)（N为栅格个数）,A^*算法的时间复杂度为O(N^*logN).当处理范围较大时,栅格数量也急剧增加,对于改进蚁群算法,当固定了M,T参数后,其时间复杂度与N值呈线性关系,但Dijkstra算法时间复杂度与N成幂函数关系,A^*算法的时间复杂度则介于蚁群算法和Dijkstra算法之间,所以改进蚁群算法时间效率明显高于Dijkstra算法及改进后的A^*算法^[18].由图8也可以看出蚁群算法拐点数目较少,说明改进蚁群算法形成的路径更符合实际路线. ...

... 近年来,随着地理信息技术的发展,基于大尺度的地形、植被等栅格数据的最优路径分析在复杂地形的路线规划、森林火灾蔓延及动物迁移等路径分析中显示出了越来越重要的应用价值.本文针对经典栅格模型成本距离算法时间消耗大的问题,将人工智能算法引入到栅格模型距离成本计算中,提出了一种用蚁群算法计算最优成本的方法;结合遗传算法搜索结果全局性的优势对该算法进行了改进,将遗传算法中的选择、交叉、变异等算子用到了蚁群算法求解路径的过程中^[18-19],并采用北极地区海冰密集度栅格数据对改进算法实现了2点最优路径求解;与Dijkstra算法及A^*算法生成路径进行对比,结果表明该算法具有可行性和高效性.在最优成本路径基本相似的情况下,本算法具有较好的时间效率,并且理论上当处理更大面积的栅格数据时,其时间优势将会更加明显,是用于求解基于栅格模型的最优成本路径的有效方法. ...

An effective cost distance calculation based on raster data model improved algorithm

2011

〈

〉

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

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

1 引言

2 普通的蚁群算法

2.1 栅格模型建立

2.2 状态转移概率选择

2.3 信息激素更新

3 改进的蚁群算法

3.1 信息素更新

3.2 融合遗传算法

3.3 改进蚁群算法实现流程

4 仿真实验

5 结论

参考文献 文献选项 原文顺序 文献年度倒序 文中引用次数倒序 被引期刊影响因子

参考文献

原文顺序

文献年度倒序

文中引用次数倒序

被引期刊影响因子