计算机工程与应用 ›› 2011, Vol. 47 ›› Issue (29): 151-153.

• 数据库、信号与信息处理 • 上一篇    下一篇

基于K-Means变异算子的混合遗传算法聚类研究

耿 跃,任军号,吉沛琦   

  1. 西北工业大学 自动化学院,西安 710072

  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2011-10-11 发布日期:2011-10-11

Hybrid genetic algorithm clustering analysis based on K-Means mutation operator

GENG Yue,REN Junhao,JI Peiqi   

  1. College of Automation,Northwestern Polytechnical University,Xi’an 710072,China
  • Received:1900-01-01 Revised:1900-01-01 Online:2011-10-11 Published:2011-10-11

摘要: 遗传算法具有良好的全局搜索能力,但有过早收敛和过慢结束的缺点。K-Means算法具有很强的局部搜索能力,但算法有对初始聚类中心敏感而易陷入局部最优解。针对上述问题,提出了基于K-Means变异算子的混合遗传算法聚类,将K-Means算法的局部搜索能力与遗传算法的全局寻优搜索能力相结合,在遗传算法中引入K-Means变异算子,采用符号编码、自适应变异、最优个体保留策略的混合遗传算法。仿真实验表明,该算法有效克服了遗传算法过慢收敛和K-Means算法陷入局部收敛的问题,从而得到更好的聚类效果。

关键词: 聚类分析, K-Means算法, K-Means变异算子, 遗传算法

Abstract: Genetic algorithm has better global search capability,but has the shortcomings of premature convergence and slow end.K-Means algorithm has strong local search ability,but it’s sensitive to the initial cluster centers and easy to get stuck at locally optimal value.To solve such problems,it presents a hybrid genetic algorithm based on K-Means mutation operator.It combines the locally searching capability of the K-Means algorithm with the global optimization capability of genetic algorithm,and introduces the K-Means mutation operator into the genetic algorithm.It’s a hybrid algorithm using symbolic coding,adaptive mutation,and optimal individual retention policies.Simulation results show that the algorithm has effectively overcome the slow convergence of genetic algorithm and the locality convergence of K-Means algorithm,in order to get better clustering.

Key words: cluster analysis, K-Means algorithm, K-Means mutation operator, genetic algorithm