基于蚁群算法的道路选取模型研究

钟 东，郭庆胜，林 青，靳家宝

(武汉大学 资源与环境科学学院，湖北 武汉 430070)

基于蚁群算法的道路选取模型研究

钟 东，郭庆胜，林 青，靳家宝

(武汉大学 资源与环境科学学院，湖北 武汉 430070)

在制图综合中，道路选取是非常重要的内容之一，研究道路选取的智能化方法是非常必要的。文中在研究道路语义、几何特征、拓扑关系和结构特征的基础上，充分考虑居民点对道路选取过程的影响，建立道路选取的蚁群算法模型。通过实验证明该模型算法的可行性和有效性。

制图综合;道路;选取;蚁群算法

在道路网综合中，道路的选取是最根本的一步，是在化简、移位等操作之前的首要步骤。针对道路网选取的研究有很多，依据是否采用智能化算法可以将现有研究分为两类：非智能选取模型和智能化选取模型[1]。

非智能选取模型分为三类：基于道路语义的选取方法，基于图论研究和基于Stroke的选取方法[2]。基于语义的道路选取是最早也是最常见的选取方法。用道路属性信息描述道路重要性，如道路名称、等级、路宽、车道数、路面类型等，将各个属性按照一定规则赋予权值，计算每条道路的总权值并按从大到小顺序进行排序，从权值最大的道路开始选取直到选取数目达到预定值[3]。图论方法是将道路网看成图，以图的节点代表道路交点，图的边代表路段，通过拓扑关系、网眼、最短路径等概念来设计算法。Thomson等[4]根据人类视觉感知原理和良好关联性(Good Continuation)提出构建Stroke对道路进行选取。Stroke被称为“路划”，是综合考虑道路本身的属性信息和感知重要性所提取的道路网中的一部分道路。基于Stroke的选取方法将道路网分成多个Stroke，每一条路段都属于某个Stroke，对路段的选取变成对Stroke的选取。

基于智能化的道路选取模型主要有：基于遗传算法的选取[5]、基于知识的选取[6]等。基于遗传算法选取道路的基本原理：首先生成道路数据的拓扑关系和几何分布特性，再根据道路的几何分布特性生成M种染色体，接下来根据适应度函数进行经济实用价值的评估，最后利用遗传算法的各种遗传算子，不断遗传，获取在空间分布特性和经济实用价值上保持良好的结果[5]。基于知识进行选取道路的研究较多，其中钱海忠提出了一种基于自动综合链来进行自动综合过程控制的模型，实现了自动综合的智能控制[6]。

本文综合考虑道路选取的多种原则和约束，研究道路选取的蚁群算法模型。

1 道路选取约束

道路选取的约束可以分为几何约束、拓扑约束和结构约束[7-10]。几何约束是要保持道路网的几何特征，过短的路段要舍去，足够长的路段必须选取。拓扑约束要保持道路的拓扑连通性以及与居民点的联系，即本来连通的道路选取后不能断开，也不应该有新的不合理的悬挂路段产生，道路网的选取要和居民点相适应。结构约束要保证道路网密度不能过大，要保证不同区域的密度对比，保持道路网的整体结构。

针对道路选取的蚁群算法模型，具体的道路选取约束会有所不同。本文主要考虑数量约束、等级约束、密度约束、连通性约束和居民点约束。

1.1 数量约束

大比例尺地图综合到小比例尺地图上时，道路的数量要减少到一定的值，这个值就是小比例尺地图上道路选取的总数，用N表示，本文把这种约束称为数量约束。确定N的方法主要有资格法和定额法[11]。资格法是以一定的数量或质量标志作为选取的标准(资格)而进行选取的方法。定额法是规定出单位面积内应选取的制图物体的数量而进行选取的方法。这两种方法各有优缺点，可以互补。本文先采用资格法确定道路选取的总数量，将在下文采用定额法确定优先选取的数量。使用定额法常常给出一个临界指标，即规定一个高指标和一个低指标[11]。通俗的讲，也就是N可以有一定的区间，即N±n。n值的大小并没有特定的要求，可根据实际情况给出，本文需要给定n，使用道路蚂蚁选取路段，判断居民点给定缓冲区内是否有路段被选取，若没有，则需要将居民点连到选定的路段上，这种情况主要出现在小比例尺上，选取的路段比较稀少时。由于没有特定的标准，并且n依赖于具体的情况，假定：

n=N×10%.

使用定额法确定N时，采用德国制图学家特普菲尔的中方根模型[11]：

式中：N为小比例尺地图上要选取的道路总数；Na为原地图的道路条数；Ma为原地图的比例尺分母；Mb为小比例尺地图的比例尺分母；x是地图符号和地物重要性的影响系数。

1.2 等级约束

道路选取时，可以依据道路的等级[11]来确定道路的优先级。道路可以依据等级从高到低分为高速公路、国道、省道、县道、乡道、农村硬化道路和机耕道[11]，将这些等级用1～7的整数表示，等级对道路选取的约束定义为等级约束。《国家基本比例尺地图编绘规范》[12]对道路选取的等级问题有明确的规定。例如，1∶5万和1∶10万的地形图(本文以这两种比例尺为例)，高速、国、省、县、乡等城际间的各等级公路均应选取。这样，蚁群算法只是针对农村硬化道路和机耕路进行选取的。

1.3 几何约束

假设l表示路段长度，δmax和δmin均表示长度阈值，根据上文所述，几何约束要求道路选取时必须选取l≥δmax的路段和删除l≤δmin的路段，但是δmax和δmin的值并没有直接给出。《国家基本比例尺地图编绘规范》规定，对于1∶5万和1∶10万的地形图，图上长度不足1 cm的乡村路、机耕道应酌情删去。但是有些路段虽然长度不足，但是位于Stroke上，这些路段不能删除。另外，非城市地区的道路长度普遍偏短，可根据实际情况降低阈值。至于δmax可以根据实际情况取图上长度1 cm的倍数。得到δmax和δmin的计算式：

δmax=μ1×M/100，

δmin=μ2×M/100.

式中：μ1为倍数，μ1> 1；μ2为阈值降低的倍数，μ2< 1；M为地形图比例尺的分母。

本文可以把l≥δmax的路段定义为必须删除的路段，把l≤δmin且不在Stroke上的路段定义为必须选取的路段。另外，为了便于下文描述，定义以下变量：

Nselect1：农村硬化道路中必须选取的路段数；

Nselect2：机耕道中必须选取的路段数；

Ndelete1：农村硬化道路中必须删除的路段数；

Ndelete2：机耕道中必须删除的路段数；

Nrest1：农村硬化道路中还可以选取的路段数；

Nrest2：机耕道中还可以选取的路段数；

N2：由几何约束选取的道路总和，N2=Nselect1+Nselect2。

1.4 密度约束

道路选取要求保持不同地区道路密度的对比，同时道路选取的结果本身不能过密。为保证此选取原则，本文采用Chen.J(2009)提出的网眼密度[13]作为标准，在不同比例尺下，不同等级路段组成的网眼密度阈值不同，由阈值来判断网眼是否过密。

1.5 连通性约束

在使用蚁群算法时，为了保证连通的道路网不能断开，蚂蚁在走到某一节点处，若没有路段可以选取而需要跳转时，就规定只能跳转到已被选取的路段所对应的节点上，以保证道路网的连通。

1.6 居民点约束

道路的取舍必须与居民点的取舍相适应，非城市区域中，道路选取的决定性因素之一就是居民点之间的最短路径[14]。在文献[6]中利用遗传算法进行道路选取时，采用居民点之间的最短路径作为目标函数。但是，智能算法每次选择的道路是随机的，若将所有居民点之间的最短路径设为目标函数，蚂蚁每选取一次就需要计算居民点之间的最短路径，计算量过大。本文的做法是在执行道路蚂蚁选取路段后，判断在各个居民点的一定范围内是否有路段被选取，若没有，则需要使用居民点蚂蚁将居民点连入道路网。具体方式：从距离居民点最近的路段出发，用最短的路程找到已经被选取的道路。

以上约束的优先级可能不同，例如，等级约束需要在密度约束之前考虑；而且，某一种约束并不都是先于或者后于另一种约束的，例如，1～5等级的道路需要全部选取，这时等级约束先于几何约束，但是对于6和7等级的道路，长度大于一定阈值的必须选取，长度小于一定阈值的必须删除，这时的几何约束就先于等级约束。

2 道路选取的蚁群算法模型

2.1 基本蚁群算法原理

蚁群算法模型是模拟现实中蚂蚁总能够在巢穴和食物之间找到最短路径的现象，从而求解实际问题的一种智能化算法。其基本思想是：如果一只蚂蚁要在某个路口选择多条路径，那么那些蚂蚁先行蚂蚁大量选择的路径(也就是信息素留存较浓的路径)被选中的概率就最大，较多的信息素意味着较短的路径。

著名的旅行商问题(TSP)：一个商人到M个城市卖商品，已知每两个城市之间的距离，如何选取一条路径使得商人走遍所有城市并回到原点且路程最短。旅行商人问题可以用图论中的无向加权图G=(M，E)来表示。M代表城市节点，E代表所有城市之间的道路，两个城市i，j之间分配权值dij表示城市i和城市j之间的距离。借用TSP问题描述蚁群算法的步骤:

1)初始化，设置时间、循环次数，将X只蚂蚁放到Y个城市中，设置好各个参数。

2)循环次数加1，禁忌表即蚂蚁走过的路段加上对应索引号码，已经行进的蚂蚁数量加1。

3)单个蚂蚁根据已经设置好的概率转移函数计算所有可以前进的城市概率，根据轮盘算法等概率选择算法选取并移动到一个城市，将其加入禁忌表。判断是否经过了所有城市，若没有则重复本步骤，直到遍历完所有城市，进入下一步。

4)更新信息素，在蚂蚁完成对所有城市的访问后，更新道路上的信息素浓度，包括原来信息素的挥发以及本次循环新加入的信息素。

5)判断算法是否停止，若满足设置好的结束条件或者循环次数到达上限，则停止。否则清空禁忌表转到第二步。

2.2 道路选取的蚁群算法模型

模仿TSP问题，能够容易的将道路选取问题用蚁群算法来建模。道路网是由众多的路段和交点组成的，因此使用图论能够很好的模拟道路网。用图来模拟道路网，可以从图中知道每个节点连接哪些路段，每条路段的始末节点是什么。蚁群算法解决的是组合优化问题，组合优化问题的核心概念是找到一组离散变量的合理组合，使得所设定的目标函数的解达到最优。对应到道路选取，即找到所有路段的合理组合，选取哪些路段，舍弃哪些路段使选取结果最符合所设定的原则与约束。

本文在蚁群算法模型中设计两类蚂蚁：道路蚂蚁和居民点蚂蚁。道路蚂蚁用于在优先选取N1+N2条道路后选取另外的Nroad条路段，Nroad=N-N1-N2；居民点蚂蚁用于将未连入所选取的道路网的居民点连入道路网，设居民点蚂蚁选取的道路数为Npoi。

目标函数是蚁群算法的实现目标，是不确定但是要尽量达到的目标。由于本算法中两类蚂蚁，因此对应的目标函数也有两个：

L1=R1+R2+ …+Ri+ …+Ra，

L2=R1+R2+ …+Rj+ …+Rb.

式中：L1为道路蚂蚁选取的路段总长度；L2为居民点蚂蚁选取的路段总长度；Ri为道路蚂蚁走过的某一路段；Rj为居民点蚂蚁走过的某一路段；a的值为Nroad；b的值为Npoi。

2.3 启发函数

启发函数是为了尽快达到目标而人为设置的函数。蚂蚁选取路段的随机性太大，当蚂蚁走到道路节点有几条路段可以选取时，通过启发函数可以令蚂蚁选取重要路段的可能性更大。目标函数为道路长度，那么启发函数也一定和道路长度相关，而且越长越好，这样才会令目标函数在尽可能短的时间内达到最优。经过对地图的研究，采用路段本身长度与路段所在Stroke长度相结合的方式设置启发函数。若某条Storke足够长，则表示组成Stroke的路段很重要，这些路段需要优先选取。启发函数式：

fη=L+Ls.

式中：fη为启发函数，L在路段长度，Ls为路段所在Stroke长度。

2.4 信息素相关函数

蚁群算法一次迭代完毕后，将完成目标函数最优的蚂蚁记录下来，同时要更新信息素。每条路段的信息素总量为残留的信息素与本次蚂蚁新生成的信息素。信息素函数为

τx(t+1)=τx(t)×ρ+Δτx.

式中：τ为信息素含量，t为时刻，t+1为新一次迭代完毕的时刻，ρ为挥发因子，x为某一路段，Δτ为本次迭代中蚁群算法产生的新信息素，Δτ的形式类似目标函数，需要考虑Stroke因素。具体表现形式：

其中，Q为常量，会影响生成信息素的量。

已知信息素函数和启发函数，可以得到随机模型。当蚂蚁走到节点处有多条路段可以选择时，由随机模型决定该条路段被选取的概率。随机模型的函数为

3 实 验

使用蚁群算法模型进行道路选取的基本策略：

1)根据使用蚁群算法模型选取道路的相应要求，对道路网和居民点数据进行预处理。首先进行拓扑检查，改正拓扑错误，创建拓扑关系。然后，明确节点连接的路段，每条路段的始末节点和左右网眼，每个网眼的组成路段。最后需构建道路Stroke，并建立居民点位置点图层。

2)按等级约束，将选取全部等级为1～5的路段，选取数量为N1。

3)道路等级为6和7的道路必须删除。

4)针对道路等级为6和7的道路选取必须选取的路段，选取数量为N2。

5)使用道路蚂蚁选取路段。如果N1+N2+Nrest1≥N，则只需在等级为6的农村硬化道路上使用道路蚂蚁进行选取，否则就在农村硬化道路和机耕道上进行选取，选取的路段数为Nroad。

6)检查密度约束。当道路蚂蚁每完成一次路径的访问，提取所有被选取的路段，重建拓扑关系，找出密度过大的网眼，舍弃网眼的一条路段，舍弃的原则：①舍弃等级最低的路段；②若等级最低的路段有多条，舍弃所在Stroke最短的路段，若Stroke长度相同，舍弃自身长度最短的路段；③若所在Stroke足够长，则此Stroke上的所有选取的路段都要保留。

7)居民点约束处理。当道路蚂蚁选取结束后，判断居民点是否都已经接入道路网，若没有，则执行居民点蚂蚁。

当Npoi>n，说明有很多居民点都没有连入道路网，则需要调整Nroad，Nroad=Nroad-n，重新执行⑤～⑦步。算法的整体流程如图1所示。

图1 算法流程

在理论基础上，进行蚁群算法模型的道路选取实验。该实验基于Visual Studio2012和AE10.2平，使用空间数据库GDB文件存储的实验数据(如图2所示)，实验数据包含道路数据(各等级的道路数见表1)和居民点数据，区域为非城市地区，比例尺为1∶1万。

表1 每个等级的道路数量

由于该数据所代表的区域是非城市地区，包含短路段，所以取中方根模型中的x=2，用来平衡选取的路段数，这样，对1∶5万地形图进行道路选取时算得N=84。再由表1得到因等级约束优先选取的路段数为N1=1+0+2+1+30=34条。取μ1=2，μ2=0.8，M=50 000，δmax=1 000 m，δmin=400 m，另外得到Nselect1=8，Ndelete1=145，Nrest1=27，Nselect2=4，Ndelete2=156，Nrest2=44，所以N2=8+4=12，N1+N2+Nrest1

同理针对1∶10万的地形图，取x=2，算得N=42，N1=34，取μ1=2，μ2=0.8，M=100 000，δmax=2 000 m，δmin=800 m，另外统计得到Nselect1=2，Ndelete1=162，Nrest1=16，Nselect2=0，Ndelete2=182，Nrest2=22，所以N2=2，N1+N2+Nrest1>N，也就是说只需在农村硬化道路中剩下的16条道路中使用蚁群算法选取6条，机耕道中的路段均不选取。

从图3实验结果和图2原始数据的对比可以看出：原始数据中具有大量的短路段，在1∶5万和1∶10万选取的地形图中均未选取，只选取了主要的道路。另外，本文所指的道路条数并不是图上直观看到的道路条数，这是因为有些道路由多个路段组成，这些路段在一个Stroke上，删除这条道路的分支后，直观的看起来就是一条道路，而实际上是由多个路段组成的。

图2 原始数据

图3 实验结果

4 结束语

本文讨论道路选取的策略，并将蚁群算法模型应用于道路选取。设计了基于蚁群算法的道路选取模型，将蚂蚁分为道路蚂蚁和居民点蚂蚁两类，道路蚂蚁进行初步选取，使用居民点蚂蚁将居民点连接到道路网内部。选取结果可以满足道路选取的原则和约束。

当然，本文也存在一定的不足，最主要的不足是阈值的确定，如道路网密度阈值，n,δmax,δmin的取值。这主要是因为这些阈值的确定带有很多的经验因素，并且受具体的环境影响较大，所以难以确定。

[1] 郭敏, 钱海忠, 黄智深,等. 采用案例归纳推理进行道路网智能选取[J]. 中国图像图形学报, 2013, 18(10):1343-1353.

[2] LIU Y，MOLENAAR M，AI T，et al. Categorical database generalization[J]. GeoSpatial Information Science，2003，6：1-9.

[3] 李晓轩.面向制图综合的道路信息表达研究与实践[D].郑州:信息工程大学，2010.

[4] THOMSON R C，RICHARDSON D E. The “good continuation” principle of perceptual organization applied to the generalization of road network[J]. Proceedings of the 19th International Cartographic Conference [C]. Ottawa: [s. n.]，1999：1215-1223.

[5] 邓红艳. 基于遗传算法的制图综合研究[D]. 郑州：信息工程大学, 2003.

[6] 钱海忠, 武芳, 王家耀. 自动制图综合链与综合过程控制模型[J]. 中国矿业大学学报, 2006, 35(6):787-791.

[7] 王家耀.地图学与地理信息工程研究[M]. 北京：科学出版社,2005.

[8] 王家耀，李志林，武芳.数字地图综合发展[M].北京：科学出版社,2011.

[9] 商其亚.道路自动综合算法的比较与应用研究[D]. 兰州：兰州交通大学，2013.

[10] 田茂义，李鹏飞，俞家勇，等.格网邻域滤波在车载激光点云道路边线提取中的方法研究[J].测绘与空间地理信息，2016,39(5)：8-10，16.

[11] 祝国瑞. 地图学[M]. 武汉：武汉大学出版社，2004.

[责任编辑：李铭娜]

Research of ant colony algorithm model of road selection

ZHONG Dong，GUO Qingsheng，LIN Qing，JIN Jiabao

(School of Resource and Environmental Science, Wuhan University, Wuhan 430070,China)

In cartographic generalization,roads selection is one of the most important aspects,and it is very necessary to study the intelligent methods of roads selection.In this paper,based on the semantic,geometry features,topology relationships,and structure features of roads,an ant colony algorithm is proposed for the road selection before considering the effect of settlement places in roads selection.At the end,the result of a test proves the practicability and effectiveness of the given algorithm.

cartographic generalization; road; selection; ant colony algorithm

引用著录：钟东，郭庆胜，林青,等.基于蚁群算法的道路选取模型研究[J].测绘工程，2017，26(4)：47-52.

10.19349/j.cnki.issn1006-7949.2017.04.009

2016-05-03

国家自然科学基金资助项目(41471384)

钟 东(1992-)，男，硕士研究生.

TP273.4

A

1006-7949(2017)04-0047-06