一种顾及道路影响的点要素注记配置遗传禁忌搜索算法

李 娟，朱勤东

(福州大学省空间信息工程研究中心,福建 福州 350002)

注记配置的合理性会直接影响地图上文本信息表达的清晰程度[1]，点要素注记配置是国内外学者研究最多、最深入的注记配置问题[2]，研究方法多为启发式搜索算法[3]，如遗传算法[2]、禁忌搜索算法[4]和蚁群算法[5]等。当前研究将智能化方法改进，或将两种或多种方法结合。如文献[6]为解决遗传算法的早熟问题，利用最小生成树聚类对遗传算法进行改进；文献[7]将粒子群优化算法和遗传算法结合，利用变异算子对粒子进行变异操作；文献[8]将点要素注记配置问题看成独立离散问题，结合数学方法改进遗传算法；文献[9]利用整数线性规划，提出了最大独立集扩展模型；文献[10]提出了一种聚类分组的蚁群算法，实现大规模点要素的快速注记；文献[11]提出了基于图论的点要素注记配置模型，将道路周边点要素注记分布的同一性作为附加影响因子;文献[12]将遗传算法和禁忌算法结合，提出了带有自适应机制的改进遗传禁忌混合算法；文献[13]提出了基于分散集中策略的遗传禁忌搜索算法解决TSP路径优化问题；文献[14]利用改进遗传禁忌搜索算法对电力系统的稳定性进行无功化改善。

本文提出利用综合具有全局寻优能力的遗传算法、具有记忆功能和“爬山能力”的禁忌搜索算法的遗传禁忌搜索算法(genetic taboo search algorithm，GTSA)解决点要素注记自动配置问题，利用遗传算法进行前期搜索，利用选择、交叉、变异等操作构造邻域，保证算法的全局搜索能力，再利用禁忌搜索算法的“爬山能力”进行后期寻优，既可提高算法的收敛速度，又可避免陷入局部最优。另外，点要素注记配置的约束条件多为单一地图要素，但在制图过程中，多为两种或两种以上的地图要素，且沿道路分布的点要素数量相对较多，虽然文献[11]中提到道路要素，并未将道路与周边点要素的空间关系纳入注记配置的约束条件中。因此本文在寻找点要素最佳注记位置时，加入道路对点要素注记的影响作为约束条件来寻找最佳注记配置方案，以增强点要素注记配置的合理性与地图的可读性。

1 遗传禁忌搜索算法主要内容

(1) 编码规则：若每个点要素有m个候选注记位置，用0～m-1指代每个候选位置[15]，用二进制对每个位置的指代值进行编码，生成一组染色体。

(2) 遗传算法(GA)操作方法：包括交叉和变异方法[16]。交叉方法采用单点交叉，即随机选择交叉位置，进行染色体交叉变换；变异操作采用冲突位变异，即选择冲突注记点位，随机生成一个注记点位编码，代替原有点位编码[15]。

(3) 选择方法：一般采用轮盘法，但该方法会导致过早收敛和停滞[16]。本文选用锦标赛方法[15]，即从交叉和变异后的群体中选择适配值排名前两位的作为下一代父代染色体。

(4) 禁忌算法(TS)操作方法：主要操作是确定邻域、禁忌表长度和规模、候选解及藐视准则[17]。邻域是在GA选择后的群体中选择定量最优个体；禁忌表存放使搜索出现循环或陷入局部最优的禁忌对象，禁忌长度动态更新；候选解是从当前解的邻域中选择定量最优个体构成；藐视准则是若当前候选解的最优对象位于禁忌表中，其适配值比历史最优解大，则该禁忌对象可代替历史最优解，作为下一次迭代的初始解，并更新禁忌表。

(5) 适配值函数：根据文中的点要素注记配置准则，主要从注记文本最小外接矩形框间是否交叉、是否压盖其他点要素、是否压盖线状要素、注记位置的优先级等因素来构造适配值函数

(1)

M(i,j)=β1M1(i,j)+β2M2(i,j)+β3M3(i,j)+β4M4(i,j)

(2)

约束条件

(3)

式中，n为点要素个数；m表示注记备选位置数；M(i,j)为点要素i在注记位置j时的适配值；αij为开关变量，当点要素i的注记框位于j位置时，αij=1，反之αij=0；β1为点要素i的注记框与其他点要素冲突的权重；β2为点要素注记框位置优先级的权重；β3为点要素i的注记框与其他点要素注记框相交的权重；β4为点要素i的注记框与道路要素相交的权重；M1(i,j)为点要素i注记框在j位置时与其他点要素对应关系的得分值；M2(i,j)为点要素i注记框在j位置对应的得分值；M3(i,j)为点要素i处于j位置的注记框与其他点要素注记框对应关系的得分值；M4(i,j)为点要素i处于j位置的注记框与道路要素对应关系的得分值。式(3)是为了保证点要素注记配置位置的唯一性。

(6) 终止条件：算法达到预设的迭代次数或算法的适配值函数在一定的范围内最优解保持不变，满足其一即可停止计算过程。

2 遗传禁忌搜索算法的点要素注记自动配置

2.1 点要素注记配置的基本原则

(1) 点要素注记备选位置如图1所示，优先级排序为正右、正上、正左、正下、右上、左上、左下、右下[7]。

(2) 不与邻近的其他点要素注记产生冲突，不压盖被注记的点要素和其他邻近点要素。

(3) 不压盖境界、铁路与干线公路等重要线状地物，并与被注记的点要素位于重要线状地物的同侧；尽量不压盖同颜色的机耕路、乡村路、小路等[4]。

2.2 GTSA的实现过程

实现过程如图2所示。

(1) 试验数据预处理。

(2) 给定算法参数，生成初始种群，置空禁忌表。

(3) 判断当前最优解是否满足算法的终止条件，若满足，则终止算法并输出优化结果，否则继续下一步骤。

(4) 利用算法中的选择、交叉和变异操作产生当前解的若干邻域解，并从邻域解中选取当前解的若干候选解。

(5) 判断当前解的候选解是否满足藐视准则，若候选解中最佳候选解满足藐视准则，则替代当前解，成为新的当前最优解，并更新禁忌表，转步骤(3)；若不满足，则判断候选解集中候选解是否均位于禁忌表中，选择非禁忌表中的候选解为新的当前最优解，并更新禁忌表，再转步骤(3)。

3 试验数据预处理

3.1 点要素预处理

在ArcGIS中，利用ArcToolBox的邻域分析工具，以2倍对角线长度为搜索半径，对点要素进行近邻分析，生成距离值和角度值，为遗传禁忌搜索分析做准备。

图3中点要素A的圆形缓冲区中，仅直线L1、L2间的点要素与中心点A的注记会发生冲突，称其为缓冲区H，故对周围点要素搜索时不必遍历除中心点A外的所有点要素，只需遍历缓冲区H内的点要素即可，极大地减少了算法的搜索时间。

3.2 点要素与道路关系的判断

对道路进行平滑处理后将道路分段形成满足多项式插值条件的曲线，并对各段曲线进行编号；再利用Matlab软件中的样条插值求出各段道路曲线的样条曲线函数；然后利用ArcGIS的ArcToolBox中的邻域分析工具，以最小外接矩形的对角线TL为搜索半径，判断点要素与道路的近邻关系。

图4中道路曲线为l，点要素为A、B、C、D，TL为注记框最小外接矩形的对角线，h为道路曲线l上与点要素最接近的一点的切线垂线与点要素最小外接矩形对角线构成直角三角形的一条直边，其中TL必定大于h，故以TL为搜索半径来判断点要素与道路间的关系，完全可以满足条件。

可用两个条件判断注记框与道路是否压盖：①可直接判断最近点是否位于矩形框内；②当最近点不在矩形框内时，选取注记框坐标极值，即Xmax、Ymax、Xmin、Ymin，判断注记极值Ymax、Ymin与邻近道路曲线函数在[Xmin,Xmax]区间上函数值Y的大小关系。

3.3 适配值函数中权重值与得分值

(1) 编码确定：点要素备选注记位置有8个，用0—7指代，每个位置的指代值用三位二进制值进行编码，若假设种群大小为N，则编码长度为3N。

(2) 注记框与点要素对应关系函数M1(i,j)=0.2T+0.4(S-T)，其中S为缓冲区H内的点要素数目(不含点要素i)，T为被点要素i注记框压盖的点要素数目。

(3) 要素注记配置位置得分值M2(i,j)，根据注记备选位置优先级从高到低，得分值M2(i,j)取值分别为0.7、0.6、0.5、0.4、0.3、0.2、0.1、0。

(4) 注记框间对应关系得分值M3(i,j)=0.1T+0.2(S-P)，其中S为缓冲区H内的点要素数目(不含点要素i)，P为与点要素i注记框相交的注记框数目。

(5) 注记框与道路要素对应关系得分值M4(i,j)=0.3L+0.6(F-L)，其中F为缓冲区H内的道路要素数目，L为被注记框压盖的道路要素的数目。

(6) 经过若干试验的验证，当点要素i的适配值函数M(i,j)中的权重值β1、β2、β3、β4分别为0.2、0.1、0.2、0.5时，试验所取得的效果最好。

算法的适配值函数越大，点要素的注记配置效果越好。

4 试验与讨论

4.1 试验环境

本文基于ArcGIS 10.2与Python 2.7，在Windows 7(64位)，Pentium(R) Dual-Core CPU E520@2.5 GHz，8 GB内存环境下实现点要素注记配置的遗传禁忌搜索算法。利用福建省惠安县的乡镇点进行试验，包含325个乡村点和9条乡村道路。按照随机抽样的方式设置点要素的个数为50、100、150、200、250、300，将GTSA、禁忌算法、遗传算法和ArcGIS软件的结果对比，判断本文提出的遗传禁忌搜索算法的计算精度、效率及稳健性。

4.2 试验参数确定

综合其他学者研究的参数设置[18-19]，并结合本文试验验证，参数设置为交叉概率0.8，变异概率0.01，邻域大小int(0.6N)(N≥30)，候选解大小10，禁忌表长度15，禁忌长度9。

4.3 试验结果

4.3.1 算法精度分析

利用ArcGIS中“使用Maplex标注引擎”功能，规定标注位置的优先级、点要素与道路要素之间的关系，按照规定的注记配置规则计算适配值。将ArcGIS得到注记位置的适配值S作为参考值，按照式(4)计算3种方法得出的最佳适配值Di(i=1,2,3)相对于ArcGIS的精度变化率

(4)

当满足算法终止条件时，不同算法的求解结果见表1、表2、表3，当点要素个数在100以内时，GTSA与ArcGIS计算结果间的精度增长在1%以内(GA和TS则是点要素个数在150以内)，随着点要素个数的增加，GTSA、TS、GA的求解质量均优于ArcGIS，GTSA平均提高3.83%，TS平均提高2.3%，GA平均提高1.74%。

表1 算法精度增长率

表2 点要素注记框压盖个数

表3 点要素注记框压盖道路个数

4.3.2 算法效率分析

当满足算法终止条件时，不同算法的运行时间见表4，其中TS的运行时间相对于GTSA和GA的运行时间相对较短，GA算法的运行时间最长。

表4 算法运行时间 s

4.3.3 算法稳健性分析

由于GA和TS均为启发式算法，同一组数据的多次计算结果不一定相同[11]，故可通过同组数据进行多次试验，利用算法的均方差判断算法的稳健性。均方差公式如下

(5)

式中，S为同一组数据所做试验的总次数，默认为50；Mt(t=0,1,…,49)分别表示TS、GA、GTSA每次获得的最佳适配值；μi(i=1,2,3)分别为TS、GA、GTSA在S次试验获得的最佳适配值均值；si(i=1,2,3)分别为TS、GA、GTSA的均方差，均方差越小，算法稳健性越好。

3种算法求得的均方差见表5，GTSA的稳健性高于GA和TS的稳健性，GA的稳健性高于TS的稳健性，且随着点要素个数的增加，算法的稳健性越来越弱；当点要素从200到250时，GA和TS的均方差均从大变小，可能与试验选取的点要素分布位置过于密集且位于道路要素的近邻范围内有关，但是GTSA仍旧不被影响，即相对于TS和GA，GTSA更具稳健性。

表5 算法均方差

4.4 结果展示

对所有的数据进行试验，其结果如图5、图6所示，矩形框框出是注记有冲突的要素。在ArcGIS结果中，注记无冲突的点要素为237，注记与道路要素有冲突的点要素为47；在GTSA结果中，注记无冲突的点要素为261，注记与道路要素有冲突的点要素为26。两者对比可知，GTSA方法的注记无冲突率比ArcGIS高，与道路的冲突数目降低，即GTSA的注记效果更好。

5 结 语

本文提出将综合遗传算法和禁忌搜索算法特性的遗传禁忌搜索算法应用在点要素注记配置中，并将道路对点要素注记配置的影响作为注记配置中的约束条件。与遗传算法、禁忌搜索算法相比，该算法的算法精度和稳健性均有所提高，但是计算效率略低于禁忌算法；与ArcGIS相比，无论是算法精度、运行计算效率还是稳健性都有提高。另外，在该算法的配置结果中点要素注记与点要素、道路的压盖量最少，注记与注记间的交叉量最少，在一定程度上提高了地图的易读性和美观性。但本文选择的仅为单一等级的点、道路要素，在后续的工作中，将进一步把点、道路要素的多等级属性纳入到研究中；同时，对该算法进行并行化改造，以提升算法的运行效率。