一种基于遗传算法改进的蚁群聚类算法.pdf

《一种基于遗传算法改进的蚁群聚类算法.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、：遇⋯～堡⋯皇⋯壁UJ}ANeOMPUTER一种基于遗传算法改进的蚁群聚类算法秦福高(常州工学院计算机信息工程学院江苏常州213002)【摘要】：基于K—nleans算法改进的蚁群聚类算法需要用户凭借经验事先输入聚类数k。针对此缺点，对该算法进行了改进，提出了一种基于遗传算法改进的蚁群聚类算法，采用启发式搜索自动搜索最佳聚类数k，使聚类数与实际问题相符，以便获得更好的聚类结果。实验结果证明，算法在聚类应用中是可行的、有效的。【关键词】：遗传算法；蚁群算法；聚类数；启发式搜索；准确率1引言度确定的中心点，第一次聚类依据欧几里得度量进文献[1]针对传统K—means聚类算法对

2、初始中行；根据第一次聚类结果更新路径上的信息素并计算心点敏感、常常受到特殊数据如孤立点的干扰而陷入样本到各个聚类中心的转移概率，转移概率超过某个局部最优的缺点，提出了一种行之有效的算法——基设定值时就进行样本归并；第一次聚类后计算适应于K—means算法改进的蚁群聚类算法(AC2ABKA，Ant度，适应度根据类内距计算，依据适应度找到排名前ColonyClusteringAlgorithmBasedonK-meansAlg0一三的精英蚂蚁并且让其变异产生后代；在蚂蚁群体中rithm)。该算法的中心点基本上是确定的，因为初始凝找出精英及相应的路径，同时对各条路径上的信息素聚

3、点是基于距离和密度确定的。这样可以防止随机选进行更新，正反馈本次的最优路径；信息素是下一代择初始聚类中心，最大限度地避免特殊数据的干扰，蚂蚁寻找目的地的依据；停止聚类、输出结果的条件保证聚类结果的稳定性能够符合我们的预期，也能防是精英蚂蚁不再变化。止发生若干个聚类中心同时处于一类导致搜索最优2．2AC2ABKA算法缺点结果时迭代次数增加的不利现象。同时该算法的精英．ACzABKA算法的初始聚类中心是相距最远的、保留机制能够为聚类提供更好的父代，在精英中进行处于高密度区域的k个数据对象，同时把正反馈、精变异操作能够提高优秀后代出现的机率，更新路径上英机制和变异算子引入到蚁群

4、聚类，算法不仅对初始的信息素利用若干精英的信息可以进一步避免特殊数据具有弱依赖性，而且能够提高聚类的准确率，加数据干扰聚类结果的现象发生、提高收敛速度、更快快收敛。但是，该算法的聚类数k是用户凭借经验输地求得最优解。入的，聚类数k的选择是影响聚类质量的一个重要参但是，文献[1]提出的AC2ABKA算法需要用户凭数，如果聚类数设置不合理，聚类结果也不能反应实借经验事先输入要生成的聚类数，使聚类结果过于主际情况。观。如果聚类数设置不合理，聚类结果也不能反应实3改进的聚类算法际情况，聚类精准率就比较低。为了在聚类数未知的3．1启发式搜索情况下能够自动搜索最佳聚类数，获得更高精度

5、的聚最佳聚类数如果采用穷举法搜索，求解效率会比类结果，本文对文献[1]提出的AC2ABKA算法进行了较低，当问题空间比较大时，有时甚至在先进的计算改进，提出了基于遗传算法改进的蚁群聚类算法工具上都无法求解。而启发式搜索在问题空间进行搜(ACEABGA，AntColonyClusteringAlgorithmBasedon索时按照启发式规则对每一个搜索的位置进行评估，GeneticAlgorithm)。得到最好的位置，再从这个位置进行搜索直到目标，2ACaABKA算法思想及其缺点以便省略大量无谓的搜索路径，从而提高效率。2．1ACABKA算法思想遗传算法(GA，Geneti

6、cAlgorithm)是模拟生物在文献[1]提出的ACZABKA算法把n个样本集对自然环境下的遗传和进化过程而形成的一种自适应象分为k个簇，k为参数；初始凝聚点是根据距离和密全局优化概率搜索方法『21。遗传算法在解空间不是盲·96·福建电脑l2014年第6期一⋯一一一⋯⋯⋯麓一目地穷举或完全随机搜索，而是采用种群的方式组织在遗传算法中常常用适应度函数值来评价个体搜索，解空间内的多个区域可以并行搜索，同时可以(即解)的好坏，值越大，解的质量越好。适应度函数是相互交流信息，实现高效启发式搜索[314]。遗传算法进化的动力，是进行“适者生存和优胜劣汰”最佳聚类数采用遗传算法进行

7、搜索时，种群个体自然选择的唯一标准。本文的适应度由类内距、类由编码方案确定，启发式规则由适应度函数确定，个间距和聚类数k根据公式(2)共同决定。体遗传与变异由遗传算子确定。在编码方案、适应度其中l／(32)随着聚类数k增大而减小，适应度厂函数及遗传算子等要素根据要解决的实际问题确定()值变小，类与类之间越松散。类内距越大，l／就后，聚类数搜索由进化演变过程中获得的相关信息自越小，适应度dk)值也相应变小，所以l／一般用来度行组织，聚类过程中引入文献[-13提出的AC2ABKA算量数据的紧凑程度。类与类之间相距越近，类间距离法。