Abstract: In order to overcome the drawbacks of the standard Particle Swarm Optimization（PSO） such as prematurity and easily trapping into local optima, a Ring neighborhood based Chaotic Particle Swarm Optimization（RCPSO） algorithm is proposed and then applied to data clustering problems, and the feasibility and efficiency of the proposed algorithm is validated on four data sets. The experimental results show that when the neighborhood size is set to one third of the population size, the algorithm with statistic ring neighborhood and the one with random ring neighborhood can both achieve overall best results on all the four data sets. RCPSO improves the global searching ability of the swarm by using appropriate size of ring neighborhood, and enhances the diversity of population with chaotic factor so as to avoid premature convergence. Furthermore, the comparison results show that RCPSO outperforms four popular algorithms in the literature（K-means, PSO, K-PSO and CPSO） in terms of error rate, which indicates that RCPSO offers an effective solution method for clustering.

Key words: data clustering, Particle Swarm Optimization（PSO）, chaotic map, ring neighborhood

摘要： 针对标准粒子群优化（PSO）算法早熟收敛及易陷入局部极值的缺点，提出一种基于环形邻域的混沌粒子群优化算法RCPSO，并将其应用于求解数据聚类问题，而且通过在4个数据集上进行仿真实验验证了算法的有效性。实验表明，当邻域大小为整个种群规模的1/3时，基于静态邻域和基于随机邻域的算法在4个数据集上的整体聚类效果均达到最好。RCPSO算法利用适当规模的环形邻域提高了粒子群的全局寻优能力，并利用混沌因子增强了粒子收敛过程中种群的多样性，从而避免算法的早熟收敛。另外，与K-means、PSO、K-PSO及CPSO算法的实验结果进行比较表明，RCPSO算法在错误率方面表现得更好，因此该算法为聚类问题提供了一种切实有效的解决方法。

关键词: 数据聚类, 粒子群优化, 混沌映射, 环形邻域