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

• 作者: 孙丽萍 朱莹 郭良敏
• 来源期刊: 计算机应用
• 学科: 工学
• 关键词: 障碍空间 k近邻 蚁群算法 并行化 可视点
• 年，卷（期）: 2019,（3）
• 所属期刊栏目: 先进计算
• 页码范围: 790-795
• 页数: 6页
• 分类号: TP311
• 字数: 7414字
• 语种: 中文
• DOI: 10.11772/j.issn.1001-9081.2018081647

摘要

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