障碍空间中基于并行蚁群算法的k近邻查询

郭良敏 朱莹 孙丽萍

摘 要：为解决障碍空间中的k近邻查询问题，提出一种基于改进的并行蚁群算法的k近邻查询方法（PAQ）。首先，利用不同信息素种类的蚁群实现并行查询k近邻;其次，增加时间因素作为路径长短的判断条件，以最直接地呈现蚂蚁的搜索时间;然后，重新定义初始信息素浓度，以避免蚂蚁的盲目搜索;最后，引入可视点将障碍路径分割为多段欧氏路径，选择可视点进行概率转移，并改进启发函数，以促使蚂蚁朝着更为正确的方向搜索，避免算法过早陷入局部最优。与WithGrids相比，当数据点个数小于300时，对于线段障碍，算法运行时间平均缩短约91.5%;对于多边形障碍平均缩短约78.5%。实验结果表明，该方法在数据规模较小时的运行时间具有明显的优势，且可以处理多边形障碍。

关键词：障碍空间;k近邻;蚁群算法;并行化;可视点

中图分类号： TP311

文献标志码：A

文章编号：1001-9081（2019）03-0790-06

Abstract： To solve the problem of k nearest neighbor query in obstacle space， a k nearest neighbor Query method based on improved Parallel Ant colony algorithm （PAQ） was proposed. Firstly， ant colonies with different kinds of pheromones were utilized to search k nearest neighbors in parallel. Secondly， a time factor was added as a condition of judging path length to directly show the searching time of ants. Thirdly， the concentration of initial pheromone was redefined to avoid the blind searching of ants. Finally， visible points were introduced to divide the obstacle path into multiple Euclidean paths， meawhile the heuristic function was improved and the visible points were selected by ants to conduct probability transfer making ants search in more proper direction and prevent the algorithm from falling into local optimum early. Compared to WithGrids method， with number of data points less than 300， the running time for line segment obstacle is averagely reduced by about 91.5%， and the running time for polygonal obstacle is averagely reduced by about 78.5%. The experimental results show that the running time of the proposed method has obvious advantage on small-scale data， and the method can process polygonal obstacles.

Key words： obstacle space; k nearest neighbors; ant colony algorithm; parallelization; visible point

0 引言

近年來，智能设备快速发展，基于位置的服务（Location Based Service， LBS）被人们广泛关注，在生活中也得到了很好的应用。LBS根据用户的位置为用户提供有效的服务，例如：为用户查找最近的电影院、附近的餐厅等。为了高效地从大量数据中挖掘出有用的信息，研究者们设计了许多查询算法，如：最近邻、k近邻、反k近邻、Skyline查询等。由于k近邻的应用范围很广，研究者们对其进行了较多研究，特别是在隐私保护和路网方面[1-2]。Jing等[1]提出了一种有效的路网k近邻查询验证技术，利用网络Voronoi图和邻居来证明查询结果的完整性。Ni等[2]设计了一个新的（s，ε）模型，通过改变s和ε参数来满足用户的查询偏好，能更方便地呈现用户对查询效率的要求。然而，已有的近邻查询研究往往只考虑理想的欧氏空间，而实际地面上移动的物体通常会受到一些地理环境的影响，如：建筑物、河流等。因此，若要准确计算近邻查询中涉及的最短路径，则必须要考虑障碍物因素，从而获得较为准确的k近邻。

经典的求解最短路径的算法有Dijkstra算法、Floyd算法、A*算法等，但它们的搜索效率并不高。近年来，出现了一些新的启发式算法，如遗传算法、粒子群算法和蚁群算法等，提高了搜索效率。蚁群算法[3-8]是继遗传算法之后的又一种全局优化算法，概念简单，优化结果好，已被成功应用于多种NP难组合优化问题：路径优化、信息检索等。目前，人们对蚁群算法收敛速度慢、易于停滞、容易陷入局部最优等不足也作了很多改进，如：夏亚梅等[3]提出了一种多信息素动态更新的蚁群算法，对基本蚁群算法进行了局部优化和全局优化，并将其应用在服务组合优化中。Cao[4]提出一种改进的机器人全局路径规划蚁群算法，从信息素挥发因子、启发函数和信息素更新策略三方面进行优化。Liu等[5]针对蚁群算法的收敛速度，将信息素扩散和几何局部最优化结合，寻找全局最优路径。张志龙等[6]对蚁群算法的启发函数、信息素增量的计算和转移概率进行改进，并将其应用到图像的边缘检测中。上述研究确实优化克服了蚁群算法的诸多不足，但仍有研究者尝试从不同角度对蚁群算法作改进，如并行蚁群算法[8]，解决了算法的可扩展性问题。

本文从一个新的角度对并行蚁群算法作改进，并将改进的并行蚁群算法应用于解决障碍空间中的k近邻查询问题。主要工作如下：

1）通过赋予每个蚁群不同的信息素种类，让多个蚁群同时工作，从而实现蚁群算法的并行化。

2）提出一种改进的并行蚁群算法，用于解决障碍空间中的k近邻查询问题。它通过添加时间因素作为判断路径长度的条件，以更直接地体现路径长度;重新定义初始信息素浓度，并改进转移概率和启发函数，以使蚂蚁朝着更为正确的方向搜索，避免算法过早陷入局部最优。

3）引入可视点[9]作为分割点，将障碍路径分段，无论将障碍物视为线段还是多边形，都可分段计算出障碍距离。

1 相关工作

1.1 障碍距离及障碍空间中的近邻查询

障碍空间中近邻查询的关键是计算障碍距离以获得最短路径。给定一组障碍物，可以通过构建可见图来找源点和目的地点之间的最短路径。Lozano-Pérez等[10]证明了最短路径可以通过任何传统的最短路径算法在可见图中求解。Zhang等[11]提出了计算障碍距离的新方法，查询过程中如有遇到障碍，则LBS服务器将会重复查询最短路径。

关于障碍空间中的近邻查询工作有：Zhang等[12]提出了第一个全面的方法来处理障碍空间中的查询，它首先利用欧氏距离确定最近邻点，然后計算出欧氏最近邻点与查询点之间的障碍距离dol，根据欧氏距离的性质可知，只有障碍距离小于dol的点才可能成为障碍最近邻点，最后作障碍距离dol范围内的障碍最近邻查询，直到求出一个最小的障碍距离点。Xia等[13]提出一种高效的障碍最近邻算法，它只以增量方式处理与查询有关的数据点和障碍物，从而过滤掉大量的点和障碍物，该算法基于R树和最佳优先搜索算法，提高了查询算法的效率。本文研究的障碍空间中的k近邻查询是获取在障碍空间中k个距离查询点q最近的数据点。Gu等[14]提出了一种有效处理障碍空间中k近邻查询的方法，它结合障碍Voronoi图进行离线预处理，并设计了几种剪枝方法来有效查询最近邻。目前已有的障碍空间中的k近邻查询研究还较少，而已有的近邻查询方法大多只考虑线段障碍。本文引入可视点，分段计算障碍距离，并根据求解的障碍距离进行k近邻选取，在面对线段障碍和多边形障碍时，均可以获得较高的查询效率。

1.2 并行蚁群算法

蚁群算法并行化有两种策略：一种是并行独立运行（Parallel Independent Runs， PIR）[15]，每个子蚁群独立搜索路径而不相互通信;另一种是部分异步并行实现（Partial Asynchronous Parallel Implementation， PAPI）[15-18]，每个子蚁群经过一定次数的迭代后，与其他子蚁群周期性交换最佳解，并更新其本地信息。由于PAPI能提高收敛速度，提高和效率，因此，大部分研究工作采用PAPI模型。例如，Manfrin等[16]提出了基于完全连通的拓扑结构的并行策略。在该模型中，一个蚁群作为Master，收集其他k-1个子蚁群发现的最优解决方案，并广播给所有子蚁群。该方法随着问题规模的增大，巡回路径的规模越来越大，成本会越来越高。Randall等[17]提出了一种蚁群算法的通信策略，每个子蚁群间相互通信，这有助于生成多样化的解决方案，从而提高找到高质量解决方案的可能性。但在策略中，主处理器必须负责收集、分类和比较所有子蚁群的解决方案，极大地影响了处理速度。Koshimizu等[18]提出划分子蚁群的搜索空间的方法，让搜索区域只被子蚁群使用。但其生成的多样化解决方案不具有传导性，且由于其固定的交换周期而降低了全局搜索能力。由已有研究可知，影响并行蚁群算法性能的主要因素有连接拓扑结构、通信策略和交换周期。针对这些因素，Yang等[19]提出了一种基于MPI（Message Passing Interface）的随机匹配并行蚁群优化算法，它设计了一种新的互连通信拓扑结构，处理器采用随机匹配的方法进行通信，并提出了一个非固定的交换周期，该算法缩短了执行时间，效率较高。

本文用不同信息素种类区分蚁群以实现并行化，以多信息素的方式代替复杂的拓扑结构，用更简单的方法缩短算法的运行时间，提高性能。

2 相关概念及符号描述

定义1 可视点[9]。若两点间没有被任何障碍物隔开，能直接可达，则称这样的点互为可视点。

如图1所示，在矩形区域中包含三个障碍物{O1，O2，O3}，q为查询点，矩形区域中的实心黑点即为q的可视点，q与其可视点之间用虚线连接。其他空心点和q之间被障碍物隔开，不能直接可达，因此它们不是q的可视点。

定义2 障碍距离[10]。两个不可视的点p1和p2之间的障碍距离为p1绕过障碍物到达p2的最短路径长度。

为了便于描述，表1列出了本文中用到的符号。

3 障碍空间中基于并行蚁群算法的k近邻查询

3.1 k近邻查询的总体框架

障碍空间中基于并行蚁群算法的k近邻查询分为3个步骤：1）查询用户q给LBS服务器发送带有位置信息的k近邻查询请求;2）LBS服务器接收到查询请求后，根据查询用户q的位置，采用改进的并行蚁群算法进行k近邻的选取;3）服务器完成k近邻选取之后，将k个近邻数据点返回给查询用户q。其框架如图2所示。

3.2 基于改进的并行蚁群算法的k近邻选取

本文将查询用户的位置作为食物源，其余数据点为蚂蚁的巢穴，不同巢穴中的蚁群种类不同，在路径上释放的信息素种类也不同。让多个蚁群同时出发，用释放的信息素种类进行区分，实现蚁群算法的并行化，以提高算法的执行速度。蚂蚁移动过程中，假设所有蚂蚁的移动速度相同，在蚂蚁出发的同时开始计时，蚂蚁每经过一个节点，系统都会记录此时的时间。本文主要从如下4个方面改进基本蚁群算法：

1）增加时间因素作为判断条件。当每个蚁群都完成从巢穴到食物源的搜索之后，查看在食物源点记录下的时间，用时最短的蚂蚁即是走的最短路径。

2）信息素初始化。基本蚁群算法中，由于初始信息素浓度相等，导致蚂蚁在刚开始时盲目搜索，致使搜索大量无关路径，对信息素浓度局部更新产生误导。该问题不仅会导致初始搜索时间偏长，并且由于无关路径信息素浓度被加强，还可能影响最短路径搜索，将算法引入局部最优。因此，本文通過初步判断点i与蚂蚁巢穴和食物源之间的距离，对初始信息素浓度给出新的定义，作为蚂蚁开始时搜索的方向性引导，初始信息素的计算如式（1）所示：

3）启发函数。基本蚁群算法的启发函数是以邻近节点路径最短的原理选取下一节点，但若当前点与邻近节点之间的路径差值并不明显，则得到的结果不一定是最优的，并且通过正反馈机制该误差值会进一步放大，导致蚂蚁向错误的方向寻找，影响了整个算法的性能。因此，本文定义的启发函数为：

4）信息素浓度的更新。为了使算法能更快地收敛于最优解，每只蚂蚁完成从点i到点j的移动后，都对分段ij上的信息素作局部信息素浓度更新，所有蚂蚁都完成从蚁群巢穴到食物源的移动之后，对每一分段ij上的信息素作全局信息素浓度更新。对局部信息素浓度和全局信息素浓度的更新方法分别如式（3）和式（4）所示：

障碍空间中基于改进的并行蚁群算法的k近邻选取算法如算法1所示。

把每个巢穴中的所有蚂蚁看作是一个蚁群，每个蚁群携带的信息素种类不同，基于此进行并行搜索。此处，并行实现是利用多线程让多个蚁群同时搜索最优解（一个蚁群对应一个线程）。算法2描述了单个蚁群的搜索过程，具体如下。

算法2 单个蚁群的搜索过程。

3.3 时间复杂度分析

本文方法提出一种基于改进的并行蚁群算法的k近邻查询方法（k nearest neighbor Query method based on improved Parallel Ant colony algorithm， PAQ），在根据概率转移公式选择下一节点时要遍历所有节点，因此时间复杂度较高，为O（Nc*a*（n+m）2+n log n），其中a为各蚁群中的蚂蚁数，Nc为迭代次数，n为数据点个数，m为障碍物的数目。文献[14]方法（WithGrids）的时间复杂度为O（n2+2m2+n log（n+m）+4n log n）。在问题规模较小时，PAQ的运行效率会明显优高于WithGrids;但随着问题规模的增大，PAQ的效率会逐渐降低，会低于WithGrids。

4 实验与结果分析

4.1 实验环境及数据集

由于文献[14]和本文均是解决障碍空间中的k近邻查询问题，因此，为了验证本文方法的有效性，与文献[14]的WithGrids方法进行了算法运行时间的对比。实验的硬件环境：CPU为Intel Core 2.83GHz，内存为4096MB RAM，操作系统为Windows 7旗舰版32位，利用Java进行编程。对于PAQ方法，本文利用多线程模拟多处理机进行仿真。本文利用两个数据集来进行实验：一个数据集是“Greece”[14]，其包含了希腊河流“rivers”和道路“roads”的地理位置;另一个数据集是“Germany”[14]，其包含了德国铁路线“rrlines”的地理位置和地形图数据“hypsogr”。文中用“hypsogr”作为数据点集合，“rrlines”“rivers”和“roads”分别作为障碍物集合，实验中的查询范围是一个自定义的动态矩形。本文所有的实验结果均是程序运行50次取的平均值。

4.2 主要参数值的选取

本文的主要参数值是通过改变因变量进行多次实验选取的经验值[20-22]。参数ρ∈（0，1），在区间（0， 1）内任意取值观察实验的最终结果（如图3），发现在处理线段障碍物时，设置ρ=0.3时，PAQ方法的运行时间最短;在处理多边形障碍物时，设置ρ=0.7时，PAQ方法的运行时间最短。参数α、 β的取值范围设为[0， 5]，同样地，在区间[0， 5]中任意取值测试实验结果，如图4所示。从图4中可以看出，α的取值对PAQ方法运行时间的影响并不太明显，但当β=2时，实验结果相对较好，为使得PAQ的效果最优，设置α=β=2。

为不失一般性，且要体现PAQ方法的优越性，本文对数据点个数、障碍物个数和k采用折中取值的方法，若无特别说明将设置蚁群中蚂蚁数a=5，数据点个数n=100，障碍物个数m=3，k=3[14]。

4.3 结果分析

图5给出了三种不同障碍物下k值对算法运行时间的影响。对于WithGrids方法，它基于网格分区索引对数据点和线段障碍物的信息作预处理，节约了算法搜索信息后再计算障碍距离的时间。而PAQ方法通过设置多个蚁群并行寻找最短路径，另外，给蚁群的初始信息素浓度，让蚂蚁在一开始搜索最短路径时就有导向性，从一定程度上优化了蚁群算法，再利用改进的启发函数，也避免了蚁群算法过早陷入局部最优，及时更新局部信息素浓度和全局信息素浓度也都提高了PAQ方法的正确性，缩短了PAQ方法的运行时间，因此PAQ方法的时间效率更高。从图5中还可看出，PAQ方法的运行时间随着k值的增大也在增长，原因是较高的k值需要较大的搜索空间，因此需要更多的计算时间。而PAQ方法在处理多边形障碍时的运行时间较处理线段障碍的长，原因是多边形障碍顶点个数多，障碍路径的数量增多。经计算，在k值小于15时，在处理线段障碍时，PAQ运行效率较WithGrids平均提高88.9%;在处理多边形障碍时，PAQ运行效率较WithGrids平均提高72.5%。

图6显示了三种不同障碍物下数据点个数对算法运行时间的影响。从图6可以看出，随数据点个数的增加，WithGrids方法的运行时间先减少后趋于平稳，原因是它根据需要在构建网格分区索引的成本和搜索成本之间作权衡，在找到一个平衡点之后运行时间就会保持相对稳定。同样由于多个蚁群的同时搜索以及对搜索方向的引导，PAQ方法的运行时间仍优于WithGrids方法。而PAQ方法在处理多边形障碍时的运行时间仍然比处理线段障碍的长，原因是障碍物顶点个数越多，路径数量就越多，障碍距离的计算量也就越大;但二者的运行时间都会随数据点个数的增加会延长。延长的原因是数据点个数的增加意味着搜索空间的增大，计算量也随之变大，但同时空间中障碍物的比例也会降低。经计算，在数据点个数小于300时，在处理线段障碍时，PAQ运行效率较WithGrids平均提高91.5%;在处理多边形障碍时，PAQ运行效率较WithGrids平均提高78.5%。

图7显示了三种不同障碍物下障碍物个数对算法运行时间的影响。从图7可以看出，随障碍物数量的增加，PAQ方法的运行时间在增长，但仍明显比WithGrids方法的运行时间短。PAQ方法性能更优的主要原因还是实现了并行，并通过对蚂蚁的搜索方向加以修正，从而缩短了搜索时间。PAQ方法的运行时间增长的原因是参与障碍距离计算的障碍物个数的增加使计算开销增大。而PAQ方法在處理多边形障碍时的运行时间增长速度比处理线段障碍的快，原因是处理多边形障碍物所需的可视点要多于处理线段障碍物的，这使障碍路径的分段数增加，障碍距离的计算量增大。经计算，在障碍物个数小于60时，在处理线段障碍时，PAQ运行效率较WithGrids平均提高94.2%;在处理多边形障碍时，PAQ运行效率较WithGrids平均提高72.0%。

PAQ方法中的并行部分是各蚁群同时从各自巢穴出发，独立搜索到食物源的最短路径。从图8中可以看出，随着数据点个数的增多，加速比在缓慢降低，主要原因是随着数据点个数的增多，蚂蚁的数量也在增加，并且蚁群中各蚂蚁仍是串行实现的，运行时间也就随之延长了。

5 结语

本文提出了一种改进的并行蚁群算法来实现障碍空间中的k近邻查询。该方法用不同信息素种类的蚁群来实现蚁群算法的并行化，提高算法的效率。它加入时间因素作为最短路径的判断条件，选择障碍空间中的可视点进行概率转移，并利用重新定义的初始信息素浓度和改进的启发函数来引导和修正蚂蚁的搜索方向，改善蚁群算法的性能。实验结果表明，在小规模数据下，改进的并行蚁群算法对障碍空间中的k近邻查询较WithGrids方法有更短的运行时间，且能处理多边形障碍。下一步，将进一步改进本文算法，以适应k值、数据点个数和障碍物个数较大的情况。

参考文献 （References）

[1] JING Y， HU L， KU W-S， et al. Authentication of k nearest neighbor query on road networks [J]. IEEE Transactions on Knowledge and Data Engineering， 2014， 26（6）： 1494-1506.

[2] NI W， GU M， CHEN X. Location privacy-preserving k nearest neighbor query under user's preference [J]. Knowledge-based Systems， 2016， 103（C）： 19-27.

[3] 夏亚梅，程渤，陈俊亮，等.基于改进蚁群算法的服务组合优化[J].计算机学报，2012，35（2）：270-281.（XIA Y M， CHENG B， CHEN J L， et al. Optimizing services composition based on improved ant colony algorithm [J]. Chinese Journal of Computers， 2012， 35（2）： 270-281.）

[4] CAO J. Robot global path planning based on an improved ant colony algorithm [J]. Journal of Computer and Communications， 2016， 4（2）： 11-19.

[5] LIU J， YANG J， LIU H， et al. An improved ant colony algorithm for robot path planning [J]. Soft Computing， 2017， 21（19）： 5829-5839.

[6] 张志龙，杨卫平，李吉成.一种基于蚁群优化的显著边缘检测算法[J].电子与信息学报，2014，36（9）：2061-2067.（ZHANG Z L， YANG W P， LI J C. A novel salient image edge detection algorithm based on ant colony optimization [J]. Journal of Electronics and Information Technology， 2014， 36（9）： 2061-2067.）

[7] 董毅，赵尚弘，李勇军，等.基于蚁群算法的分布式卫星光网络波长路由分配技术研究[J].电子与信息学报， 2015，37（11）：2650-2656.（DONG Y， ZHAO S H， LI Y J， et al. Research on routing and wavelength assignment based on ant colony optimization in distributed satellite optical network [J]. Journal of Electronics and Information Technology， 2015， 37（11）： 2650-2656.）

[8] DORIGO M， BIRATTARI M， STUTZLE T. Ant colony optimization： artificial ants as a computational intelligence technique [J]. IEEE Computational Intelligence Magazine， 2006， 1（4）： 28-39.

[9] XU J， GTING R H. Querying visible points in large obstructed space [J]. GeoInformatica， 2015， 19（3）： 435-461.

[10] LOZANO-PREZ T， WESLEY M A. An algorithm for planning collision-free paths among polyhedral obstacles [J]. Communications of the ACM， 1979， 22（10）： 560-570.

[11] ZHANG L， LI J， YANG S， et al. Privacy preserving in cloud environment for obstructed shortest path query [J]. Wireless Personal Communications， 2017， 96（2）： 2305-2322.

[12] ZHANG J， PAPADIAS D， MOURATIDIS K， et al. Spatial queries in the presence of obstacles [C]// Proceedings of the 2004 International Conference on Extending Database Technology， LNCS 2992. Berlin： Springer， 2004：366-384.

[13] XIA C， HSU D， TUNG A K H. A fast filter for obstructed nearest neighbor queries [C]// Proceedings of the 2004 British National Conference on Databases， LNCS 3112. Berlin： Springer， 2004： 203-215.

[14] GU Y， YU G， YU X. An efficient method for k nearest neighbor searching in obstructed spatial databases [J]. Journal of Information Science and Engineering， 2014， 30（5）： 1569-1583.

[15] STTZLE T. Parallelization strategies for ant colony optimization [C]// Proceedings of the 1998 International Conference on Parallel Problem Solving from Nature， LNCS 1498. Berlin： Springer， 1998： 722-731.

[16] MANFRIN M， BIRATTARI M， STTZLE T， et al. Parallel ant colony optimization for the traveling salesman problem [C]// Proceedings of the 2006 International Workshop on Ant Colony Optimization and Swarm Intelligence， LNCS 4150. Berlin： Springer， 2006： 224-234.

[17] RANDALL M， LEWIS A. A parallel implementation of ant colony optimization [J]. Journal of Parallel and Distributed Computing， 2002， 62（9）： 1421-1432.

[18] KOSHIMIZU H， SAITO T. Parallel ant colony optimizers with local and global ants [C]// Proceedings of the 2009 International Joint Conference on Neural Networks. Piscataway， NJ： IEEE， 2009： 2707-2711.

[19] YANG Q， FANG L， DUAN X. RMACO： a randomly matched parallel ant colony optimization [J]. World Wide Web， 2016， 19（6）： 1009-1022.

[20] MERKLE D， MIDDENDORF M， SCHMECK H. Ant colony optimization for resource-constrained project scheduling [J]. IEEE Transactions on Evolutionary Computation， 2002， 6（4）： 333-346.

[21] 李琳，應时，赵翀，等.基于蚁群算法的面向服务软件的部署优化方法[J].电子学报，2016，44（1）：123-129.（LI L， YING S， ZHAO C， et al. Deployment optimization of service-oriented software based on ant colony algorithm [J]. Acta Electronica Sinica， 2016， 44（1）： 123-129.）

[22] 曾梦凡，陈思洋，张文茜，等.利用蚁群算法生成覆盖表：探索与挖掘[J].软件学报，2016，27（4）：855-878.（ZENG M F， CHEN S Y， ZHANG W Q， et al. Generating covering arrays using ant colony optimization： exploration and mining [J]. Journal of Software， 2016， 27（4）： 855-878.）