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

2019-07-31 12:14:01郭良敏朱莹孙丽萍
计算机应用 2019年3期

郭良敏 朱莹 孙丽萍

摘 要:为解决障碍空间中的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图和邻居来证明查询结果的完整性。……

登录APP查看全文