障碍空间中基于并行蚁群算法的k近邻查询
|
摘要
为解决障碍空间中的k近邻查询问题,提出一种基于改进的并行蚁群算法的k近邻查询方法(PAQ)。首先,利用不同信息素种类的蚁群实现并行查询k近邻;其次,增加时间因素作为路径长短的判断条件,以最直接地呈现蚂蚁的搜索时间;然后,重新定义初始信息素浓度,以避免蚂蚁的盲目搜索;最后,引入可视点将障碍路径分割为多段欧氏路径,选择可视点进行概率转移,并改进启发函数,以促使蚂蚁朝着更为正确的方向搜索,避免算法过早陷入局部最优。与WithGrids相比,当数据点个数小于300时,对于线段障碍,算法运行时间平均缩短约91.5%;对于多边形障碍平均缩短约78.5%。实验结果表明,该方法在数据规模较小时的运行时间具有明显的优势,且可以处理多边形障碍。
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.
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.
引文
[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 ZL,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[J].IEEE Computational Intelligence Magazine,2006,1(4):28-39.
[9]XU J,GTING R H.Querying visible points in large obstructed space[J].Geo Informatica,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].IEEETransactions 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,CHENS 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.)
[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 ZL,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[J].IEEE Computational Intelligence Magazine,2006,1(4):28-39.
[9]XU J,GTING R H.Querying visible points in large obstructed space[J].Geo Informatica,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].IEEETransactions 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,CHENS 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.)