计算机工程与应用 ›› 2019, Vol. 55 ›› Issue (20): 52-57.DOI: 10.3778/j.issn.1002-8331.1807-0058

• 理论与研发 • 上一篇    下一篇

具有全局记忆的LF蚁群聚类算法

王昕宇,罗可   

  1. 1.长沙理工大学 计算机与通信工程学院,长沙 410114
    2.长沙理工大学 综合交通运输大数据智能处理省重点实验室,长沙 410114
  • 出版日期:2019-10-15 发布日期:2019-10-14

LF Ant Colony Clustering Algorithm with Global Memory

WANG Xinyu, LUO Ke   

  1. 1.School of Computer and Communication Engineering, Changsha University of Science and Technology, Changsha 410114, China
    2.Hunan Provincial Key Laboratory of Intelligent Processing of Big Data on Transportation, Changsha University of Science and Technology, Changsha 410114, China
  • Online:2019-10-15 Published:2019-10-14

摘要: 针对传统的LF蚁群聚类算法中存在的收敛速度慢,蚂蚁空载导致的资源浪费以及易陷入局部最优等问题,提出了一种蚁群改进算法。算法初期采用直接分配原则,直接将蚂蚁随机放在数据对象上,并生成随机的全局记忆,在聚类时负载蚂蚁移动受到全局记忆的指导,利用余弦相似度判断最相似的记忆中心,并向该记忆中心移动,全局记忆在一次迭代完成后更新。当蚂蚁拾起数据对象失败时,为了减少蚂蚁再一次的随机移动所带来的资源浪费,采用相异原则将蚂蚁移动到下一个数据对象上。改进的算法在UCI数据集Iris、Wine、Glass和Robotnavigation上进行验证,算法在保证原有算法准确率的基础上明显提高了收敛速度。

关键词: LF蚁群聚类算法, 直接分配, 全局记忆, 余弦相似度, 相异原则

Abstract: The traditional LF ant colony clustering algorithm has been studied, such as slow convergence rate, waste of resources caused by empty ant no-load and easy to get into local optimum. In order to improve the convergence rate, the principle of direct allocation is adopted in the initial stage of the algorithm, putting the ants on the data point at random and generating random global memory. The movement of loaded ants is guided by global memory during clustering, moving to the memory center which is using cosine similarity to determine the most similar. Global memory is updated after an iteration is complete. When the ant failed to pick up the data object, ?the principle of dissimilarity is adopted to move ants to the next data point in order to reduce the resource waste caused by the random movement of ants again. The improved algorithm which improves the convergence speed greatly on the basis of ensuring the accuracy of the original algorithm is validated with Iris, Wine, Glass and Robotnavigation in the UCI data set.

Key words: LF ant colony clustering, direct?distribution, global memory, cosine similarity, principle of dissimilarity