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

ComputerEngineeringa” ，caf0 计算机工程与应用 2011，47(29) 15l 基于K-Means变异算子的混合遗传算法聚类研究 耿 跃，任军号，吉沛琦 GENG Yue，REN Junhao，JIPeiqi 西北工业大学 自动化学院，西安 710072 College ofAutomation，Northwestern PolytechnicalUniversity，Xi’an 710072，China GENG Yue，REN Junhao，JI Peiqi．Hybrid genetic algorithm clustering analysis based on K-M eans mutation operator． ComputerEngineeringandApplications，2011。47(29)：151-153． Abstract：Genetic algorithm hasbetterglobalsearch capability，buthasthe shortcomings ofpremature convergence and slow end．K-M eansalgorithm hasstrong localsearch ability，butit’Ssensitive to the initialclustercentersand easy to getstuck at locally optimalvalue．To solve such problems，itpresents a hybrid genetic algorithm based on K-M eans mutation operator．It combinesthe locally searching capability oftheK-M eansalgorithm with theglobaloptimization capability ofgenetic algorithm ， and introduces the K-Meansmutation operatorinto the genetic algorithm ．It’S a hybrid algorithm using symbolic coding，adaptive mutation，and optimal individualretention policies．Simulation results show that the algorithm has effectively overcome the slow convergenceofgenetic algorithm and the locality convergence ofK-M eansalgorithm ，in orderto getbetterclustering． Key words：clusteranalysis；K．M eansalgorithm ；K—M eansmutation operator；genetic algorithm 摘 要：遗传算法具有 良好的全局搜索能力，但有过早收敛和过慢结束的缺点。K-Means算法具有很强的局部搜索能力，但算法 有对初始聚类中心敏感而易陷入局部最优解。针对上述问题，提出了基于K—Means变异算子的混合遗传算法聚类，将K-Means 算法的局部搜索能力与遗传算法的全局寻优搜索能力相结合，在遗传算法中引入K-Means变异算予，采用符号编码 、自适应变 异、最优个体保留策略的混合遗传算法。仿真实验表明，该算法有效克服了遗传算法过慢收敛和K-Means算法陷入局部收敛的 问题，从而得到更好的聚类效果。 关键词：聚类分析；K-Means算法；K-Means变异算子；遗传算法 DOI：10．3778~．issn．1002．8331．2011．29．043 文章编号：1002—833l(2011)29—0151．03 文献标识码：A 中图分类号：TP391 l 引言 2 聚类分析的数学模型 聚类分析方法是一个无监督的学习分析过程 ，是指对样 聚类是将样本数据分类到不同的类或者簇这样的一个过 品或指标按其某些属性进行分类，在同一类中的个体具有较