计算机应用

作者：郭良敏, 朱莹, 孙丽萍

单位：1. 安徽师范大学 计算机与信息学院, 安徽 芜湖 241003;2. 网络与信息安全安徽省重点实验室(安徽师范大学), 安徽 芜湖 241003

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

基金：国家自然科学基金资助项目（61672039，61602009）；安徽省自然科学基金资助项目（1508085QF133，1608085MF145）。

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

来源：2019年第3期

《计算机应用》期刊编辑部

查看计算机应用杂志2019年第3期