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

发布时间：2021-06-18 09:06

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

【文章来源】：计算机应用. 2019,39(03)北大核心CSCD

【文章页数】：6 页

【部分图文】：

近邻查询的框架Fig．2Frameworkofknearestneighborquery表1各变量的含义

ρ值的选取Fig．3Selectionofρvalue

?对蚂蚁的搜索方向加以修正，从而缩短了搜索时间。PAQ方法的运行时间增长的原因是参与障碍距离计算的障碍物个数的增加使计算开销增大。而PAQ方法在处理多边形障碍时的运行时间增长速度比处理线段障碍的快，原因是处理多边形障碍物所需的可视点要多于处理线段障碍物的，这使障碍路径的分段数增加，障碍距离的计算量增大。经计算，在障碍物个数小于60时，在处理线段障碍时，PAQ运行效率较WithGrids平均提高94．2%;在处理多边形障碍时，PAQ运行效率较WithGrids平均提高72．0%。图5k对运行时间的影响Fig．5Effectsofkonrunningtime图6数据点个数对运行时间的影响Fig．6Effectsofnumberofdatapointsonrunningtime图7障碍物个数对运行时间的影响Fig．7EffectsofnumberofobstaclesonrunningtimePAQ方法中的并行部分是各蚁群同时从各自巢穴出发，独立搜索到食物源的最短路径。从图8中可以看出，随着数据点个数的增多，加速比在缓慢降低，主要原因是随着数据点个数的增多，蚂蚁的数量也在增加，并且蚁群中各蚂蚁仍是串行实现的，运行时间也就随之延长了。图8PAQ的加速比Fig．8AccelerationratioofPAQ5结语本文提出了一种改进的并行蚁群算法来实现障碍空间中的k近邻查询。该方法用不同信息素种类的蚁群来实现蚁群算法的并行化，提高算法的效率。它加入时间因素作为最短路径的判断条件，选择障碍空间中的可视点进行概率转移，并利用重新定义的初始信息素浓度和改进的启发函数来引导和修正蚂蚁的搜索方向，改善蚁群算法的性能。实验结果表明，在小规模数据下，改进的并行蚁群算法对障碍空间中的k近邻查询较WithGrids方法有更短的运行时间

【参考文献】：
期刊论文
[1]基于蚁群算法的面向服务软件的部署优化方法[J]. 李琳,应时,赵翀,董波.  电子学报. 2016(01)
[2]利用蚁群算法生成覆盖表:探索与挖掘[J]. 曾梦凡,陈思洋,张文茜,聂长海.  软件学报. 2016(04)
[3]基于蚁群算法的分布式卫星光网络波长路由分配技术研究[J]. 董毅,赵尚弘,李勇军,赵静,邓博于.  电子与信息学报. 2015(11)
[4]一种基于蚁群优化的显著边缘检测算法[J]. 张志龙,杨卫平,李吉成.  电子与信息学报. 2014(09)
[5]基于改进蚁群算法的服务组合优化[J]. 夏亚梅,程渤,陈俊亮,孟祥武,刘栋.  计算机学报. 2012(02)



本文编号：3236382