一种基于遗传和蚁群算法融合的聚类新方法

1、一种基于遗传和蚁群算法融合的聚类新方法摘要：遗传算法具有快速良好的全局搜索能力，而蚁群聚类算法具有良好的分布式并行性和正反馈能力。将两种算法进行融合，充分利用算法各自的优势和特点，能更有效地进行聚类分析。实验证明这种新组合算法在优化能力和时间性能上比常用的聚类算法有比较明显的优势。关键词：遗传算法; 蚁群算法; 聚类中图分类号：TP311 文献标识码：AA New Clustering Algorithm Based on the Combination of Genetic Algorithm and Ant Colony AlgorithmAbstract: Genetic algorit

2、hm has the ability of doing a global quickly and stochastically. Ant colony clustering algorithm has the ability of distributed parallel processing, and has good feedback capacity. The combination of both the algorithms can make full use of each advantages and character, and make clustering analysis

3、 better. Some experiments proved that the new combination algorithm has obvious advantage in optimization capacity and performance time than some common clustering algorithms.Key words: genetic algorithm; ant colony clustering algorithm; clustering;1 引言聚类就是将整个数据分成不同的组，并使组与组之间的差距尽可能大，组内数据的差异尽可能小。几种典型

4、的聚类方法包括：划分方法k-平均(k-means)和PAM，层次聚类方法AGNES和DIANA，密度聚类方法DBSCAN等等。遗传算法(GA)是由美国密执安大学的JohnHoUmd教授于1975年首先提出的一类仿生型优化算法它是以达尔文的生物进化论“适者生存、优胜劣汰”和孟德尔的遗传变异理论“生物遗传进化主要在染色体上，子代是父代遗传基因在染色体上的有序排列”为基础，模拟生物界进化过程。蚁群算法(ant colony algorithm）是最新发展的一种模拟蚂蚁群体智能行为的仿生优化算法1，由意大利学者Dorigo M于1991年提出。它具有较强的鲁棒性、优良的分布式计算机制、易于与其他方法相

5、结合等优点2,3。基于蚁群算法的聚类方法从原理上可以分为两种：一种是基于蚁堆形成原理来实现数据聚类，另一种是运用蚁群觅食的原理，利用信息素(pheromone)来实现聚类分析15。该文采用第一种方法进行聚类分析。最早在这一领域开展工作的是Deneubourg等6，他们建立了一种基本模型，根据数据对象与其周围对象的相似性，让蚁群随机地移动、拾起或放下数据对象，以达到聚类数据的目的。Lumer E 和Faieta B将该模型推广到数据分析范畴，提出了LF算法7。吴斌等8，Ramos等9,杨燕等10从不同角度对LF算法进行了改进，并取得了一定的成效。Abbattista F等4最早提出了将遗传算法(

6、GA)和蚁群算法相融合的改进策略，并在Oliver30TSP和Eilon50TSP的仿真实验中得到了较好的结果；随后，人们将蚁群算法与GA相融合来解决离散域和连续域中的多种优化问题，并取得了较好的应用效果。丁建立等11将遗传算法和蚂蚁算法的融合应用于解决组合爆炸及NP类问题，无论在优化性能还是时间性能都取得了非常好的效果。本文算法旨在聚类分析，是将遗传算法和蚁群聚类算法融合，利用遗传算法快速随机的群体性全局搜索能力生成数据对象的初始聚类中心，再通过蚁群算法的并行性、正反馈、求精解效率高的特点完善聚类结构。本文组织如下：第2节着重说明遗传算法与蚁群聚类算法的融合，包括基本原理，遗传算法和蚁群聚类

7、算法分析，整体算法描述；第3节是实验结果的对比分析，将本算法的实验结果与标准蚁群聚类算法和模糊蚁群聚类算法14进行比较分析；最后是结论。2 遗传算法与蚁群聚类算法的融合(GA2C2A)21 GA2C2A算法的基本原理和设计思想遗传算法具有大范围的快速全局搜索能力，但当求解到一定程度时，往往作大量的冗余迭代，对于系统中的反馈信息利用不够，求解效率降低；而蚁群聚类算法由于初期数据对象随机散布，蚂蚁“拾起”、“放下” 对象随机运动，形成有效聚类的时间很长，如图1遗传算法与蚁群算法的速度-时间曲线5所示。遗传算法在搜索的初期(t0ta时间段)具有较高收敛速度，但达到ta之后效率明显降低。而蚁群算法在搜

8、索的初期(t0ta时间段)由于数据及自身运动的随机性，使得搜索速度缓慢，但当运动到一定时间后，效果显著提升。遗传算法与蚁群聚类算法融合(genetic algorithm-ant colony clustering algorithm, GA2C2A)的基本思想是：基于遗传算法的快速全局搜索能力和蚁群算法的正反馈收敛机制，初期采用遗传算法过程生成数据对象的初始聚类中心，后期利用蚁群算法正反馈完善聚类结构，优势互补。图1遗传算法与蚁群算法的速度-时间曲线22 GA2C2A中遗传算法的定义与设置221 问题描述设目标函数: (1)其中，聚类中心 (2) (3)为属于r类的样本个数；表示样本属于第r

9、类；N为样本数；P为聚类中心数(2PN-1)222 染色体构造设表示染色体结构，为维行向量，为第位置基因；设N为样本数，则染色体要求如下：1) (4)2) (5)3) 其中 (6)223 适应度函数及遗传算子操作适应度函数F定义为，其中M为一常数，为公式(1)所定义。这样值小的个体，相应的适应度值就高。遗传算子操作包括选择、交叉和变异等过程。1) 选择规则，按照以上选定的适应度函数，使用轮盘策略进行选择，每一代中最好的染色体在下一代中优先选择，每一代同一染色体在下一代被选择的数量不超过2个。2) 交叉规则，交叉规则采用位交叉法控制。采用此方法，有可能出现交叉后染色体不满足条件公式(6)的异常情

10、况。为此，定义允许最大尝试次数W，若超出W则放弃该配对的染色体，重新配对交叉。3) 变异规则，采用逆转变异方法16，例如：，假设区间和区间处发生断裂，断裂片段又以方向顺序插入，于是逆转后的染色体变为：224 GA2C2A中遗传算法整体描述遗传算法整体流程如下：1种群初始化，设置进化代数、交叉率、变异率等初始值；2选择运算，根据以上公式进行计算，按染色体适应度大小按比例进行选择；3交叉运算，任选两个个体进行交叉操作；4变异运算，变异位置随机产生；5得到优化染色体，在每一迭代过程中，计算除每一染色体的适应度函数值，并由此产生新的后代染色体。若达到停止条件，就结束，得到聚类结果；否则，转向2，重复执

11、行迭代过程。23 GA2C2A中蚁群聚类算法的改进与衔接231 标准蚁群聚类算法(SACA)标准蚁群聚类算法(standard ant clustering algorithm, SACA)是由Lumer E 和Faieta B提出的。其基本思想是：假设蚂蚁在一个随机散布了数据对象的二维平面内随机地移动。初始蚂蚁随机选择一个数据对象，根据该对象在局部区域的相似性而得到的概率，决定蚂蚁是否“拾起”或“放下”该对象。经过有限次迭代，平面上的数据对象按其相似性而聚集，最后得到聚类结构和聚类数目。蚂蚁“拾起”对象的概率是由与当前邻域对象的相似度决定的，相似度低，“拾起”概率高，相似度高，“拾起”概率低

12、；蚂蚁“放下”对象的概率则与此相反。1）相似度函数 (7)为对象周围正方形局部区域面积；为相似性参数，常量；2）拾起”、“放下”概率函数 (8) (9) 其中 是阈值常量等于0.1和0.15。，对于，假如，那么；假如，那么。对于，假如，那么；假如，那么蚂蚁放下对象。232改进的SACA文献101213对SACA进行了一些改进，主要表现在采用余弦距离与欧氏距离的线性组合，更好地区分对象；采用对称式Sigmoid函数作为概率转换函数，比SACA的二次函数具有更快的收敛性；通过信息熵增强蚂蚁短期记忆，使蚂蚁充分利用已有信息，提高算法效率；定义蚂蚁放下对象失败次数，当达到阈值时，强行放下数据，以便加快

13、聚类的进程。本文是与遗传算法的融合，通过遗传算法，产生初始聚类中心，将数据对象按照已有规律散布在二维平面，因此，每个单元格可以存放一个，两个或更多的数据对象，同时把两个或两个数据对象的集合称为堆。在文献14研究基础上，定义：堆拥有个对象；堆中两个对象的最大距离：，D为欧氏距离；堆中对象聚类中心：，堆中最具差异对象；堆中对象距离聚类中心距离：；运行方向选择参数，初始化时蚂蚁随机选取方向，随后按照概率判断是继续保持还是随机选择方向。拾起概率，当蚂蚁没有携带任何对象时，按运行方向在周围8个邻居中，寻找可能拾起的对象。蚂蚁可能发现的对象存在三种情况：单一的对象，拥有两个对象的堆或拥有两个以上对象的堆。

14、对应存在三种拾起概率：装载概率，堆破坏概率及对象移除概率。处理流程如下：1. 标识8邻居为”unexplored”；2. 当没有找到时就重复以下操作2.1 搜索下一个标识为”unexplored”的区域，2.2 if 区域不为空 then2.2.1 if 单元格只有一个对象，then按拾起该对象，按公式(8)计算， else2.2.2 if 堆中有两个对象，then按拾起该对象，else2.2.3 if 堆中有多个对象，then 找到最不相似的对象，当时（其中为阈值常数）2.3 标识单元格为”explored”放下概率，当蚂蚁携带有对象时，按运行方向在周围8个邻居中，寻找可能放下的单元格。当单

15、元格为空时，蚂蚁按概率放下所携带对象；当单元格不为空，且有且仅有一个对象时，计算两对象距离与所有对象最大距离的商，若小于概率，则放下对象，创建一个堆；当单元格不止一个对象时，计算所携带对象较堆最不相似对象距堆聚类中心的距离，若小于则放下对象。若蚂蚁所携带对象经W次计算，仍未放下，则可以强行放下该对象，以增强聚类进程。处理流程如下：1. 标识8邻居为”unexplored”；2.若没有找到标识且运算次数<W就重复以下操作2.1搜索下一个标识为”unexplored”的区域，2.1.1 if单元格为空then蚂蚁所携带对象按概率放下，按公式(9)计算else2.1.2 if单元格有一个对象，

16、且，为阈值常数，then放下对象，else2.1.3 if单元格含有一个堆，且，then放下对象2.1.4 计数器累加2.2 标识单元格为”explored”3. if计数器>W then 强行放下233 GA2C2A中蚁群聚类算法整体描述改进后的蚁群聚类算法流程如下：1. 随机将蚂蚁散布在二维平面，将遗传算法产生的初始聚类，按簇散布在平面内，每个单元格一个或多个对象，初始化最大循环次数n，蚂蚁总数ant_number等参数；2. for i=1,2,.,n;3. for j=1,2,ant_number;3.1 移动蚂蚁3.2 if 蚂蚁没有携带对象then if 在蚂蚁周围的8个邻居

17、中存在对象，那么蚂蚁按概率拾起对象3.3 else 通过计算与周围8个邻居的相似度，按概率放下对象4标记聚类模式234遗传算法和蚁群聚类算法的衔接文献11提出了遗传算法与蚁群算法融合的一般性优化问题求解策略，该策略在遗传算法中设置了固定的迭代次数，这样会造成过早或过晚结束遗传算法过程，不能有效保证两者在最佳时机进行融合。在文献16研究的基础上，这里提出的融合策略可以保证最佳融合时机。主要方法如下：1） 根据实际情况设置初始聚类中心数P，该参数决定了遗传聚类在从解的染色体往解的物理值映射过程的复杂度；2） 设置最小和最大遗传迭代次数(Genemin、Genemax)；3） 遗传算法迭代过程中统计

18、子代群体的进化率，并以此设置子代群体的最小进化率Genemin_ratio；4） 在设定的迭代次数范围内，如果子代群体的进化率都小于Genemin_ratio，说明此时遗传算法优化速度较低，因此可以终止，进入蚁群算法。 24 GA2C2A整体框架图 2 GA2C2A整体框架3 仿真实验结果采用了表1中的3个数据集对SACA，模糊蚁群聚类算法14 ，GA2C2A进行了测试。这些数据库自身具备分类表，可以用于最终评价性能。表 1 测试数据集描述数据集实例数量属性个数分类个数Iris15043Wine178133Glass21496本文采用一种常用的外部评价方法：F-measure17。F-meas

19、ure组合了信息检索中查准率与查全率思想。一个聚类j及与此相关的分类i的查准率与查全率定义为： 其中是聚类j中分类i的数目，是聚类j中所有对象的数目，是分类i中所有对象的数目。则分类i的F-measure定义为： (10)对聚类结果p，其总F-measure可由每个分类i的F-measure加权平均得到： (11) 对表1中3个数据集进行了50次测试后的平均总F-measure结果如表2所示。实验结果表明，GA2C2A性能优于SACA，模糊蚁群聚类算法。表2 聚类的平均总F-measur算法IrisWineGlassSACA0.9050.8910.903模糊蚁群聚类算法0.9110.9090.

20、912GA2C2A0.9150.9110.9154 结论遗传算法和蚁群聚类算法的有机融合，正是利用遗传算法的快速全局搜索能力和蚁群算法的正反馈收敛机制，优势互补。从仿真实例来看，该算法比标准蚁群聚类算法以及模糊蚁群聚类算法在优化性能和时间性能上有一定的优势。此算法的瓶颈在于融合的时机把握，虽然目前的解决方案能满足要求，但是仍然需要继续完善。参考文献1 Colorni A, Dorigo M, Maniezzo V, et al. Distributed optimization by ant colonies. Proceedings of the 1st European Conferenc

21、e on Artificial Life, 1991, 134142.2 Dorigo M. Optimization, learning and natural algorithm.Ph.D.Thesis, Department of Electronics, Politecnico diMilano, Italy, 1992.3 Dorigo M, Maniezzo V, Colorni A. Ant system: optimization by a colony of cooperating agents. IEEE Transaction on Systems, Man, and C

22、ybernetics-Part B, 1996, 26(1):2941.4 Abbattista F, Abbattista N, Caponetti L. An evolutionary and cooperative agents model for optimization. Proceedings of the IEEE International Conference on Evolutionary Computation, 1995, 2:668671.5 段海滨. 蚁群算法原理及其应用.北京:科学出版社,2005.6 Deneubourg J L, Goss S, Franks

23、N, et al. The dynamics of collective sorting: robot-like ant and ant-like robotA. In: Meyer J A, Wilson S W ed. Proceedings first conference on simulation of adaptive behavior: from animals to animatsC. Cambridge, MA: MIT Press, 1991. 356-365. 7 Lumer E, Faieta B. Diversity and adaptation in populat

24、ions of clustering antsA. In: Proc. third international conference on simulation of adaptive behavior: from animals to animats 3C. Cambridge, MA: MIT Press, 1994, 499-508. 8 Wu B，Shi Z. A clustering algorithm based on swarm intelligenceA. In: Proceedings IEEE international conferences on info-tech & info-net proceedingC. Beijing, 2001. 58-66.9 Ramos V, Merelo J J. Self-organized stigmergic document maps: environment as a mechanism for context learningA. In: Alba E, Herrera F, Merelo J J, et al., ed. AEB´2002 1st Spanish conference on evolutionary and bio-inspired algorithms