基于信息熵的蚁群聚类改进方法研究

《基于信息熵的蚁群聚类改进方法研究》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第26卷第8期计算机仿真2009年8月文章编号：1006—9348(2009)08—0179—05基于信息熵的蚁群聚类改进方法研究严燕，卢宏涛(上海交通大学，上海200240)摘要：从模仿蚂蚁堆积尸体的基本模型出发，可以实现蚁群聚类算法。研究了实现基本蚁群算法以及基于信息熵的蚁群聚类算法的关键方法，测试并验证了算法的有效性。同时，在比较其性能的基础上，主要针对基于信息熵的蚁群聚类算法收敛速度快，但却容易陷入局部最优的缺陷，从聚类拆分、合并、孤立点处理等几个方面对基于信息熵的蚁群聚类算法进行了改进，从而在利用其收敛速度快的基础上提高聚类

2、的准确性。仿真实验表明：改进后的方法在聚类的准确性和收敛速度方面都得到了很好的结果，对基于信息熵的蚁群居类算法优化提供了比较好的应用改进。关键词：聚类；信息熵；蚁群优化中图分类号：TP391文献标识码：AAnimprovedAntColonyClusteringAlgorithmUsingInformationEntropyYANYan．LUHong—tao(ShanghaiJiaotongUniversity，Shanghai200240，China)ABSTRACT：Antcolonyclusteringalgorithmcanb

3、erealizedonthebasisofthebasicmodelthatimitatestheaggTe—gationofdeadbodiesbyants．ThepapervalidatesLFandentropybasedantcolonyclusteringalgorithmsviapropo—singthekeysimulationmethods．Comparingtheperformanceofthetwoalgorithms，itisshownthatentropybasedantcolonyclusteringalgo

4、rithmhasthedefectofeasilygettinglocaloptimalityalthoughithasbetterconvergencecom—paredwithLF．Thepaperintendstoproposeanimprovedentropybasedantcolonyclusteringalgorithmmainlyforsolvingthatproblemthroughclustersplitting，mergingandhandlingofisolatedobjects．Thecomputational

5、resultsshowthattheclusteringresultandconvergencearebetter山anthatoftheothertwomethods．KEYWORDS：Clustering；Entropy；Antcolonyoptimization收敛速度过慢；而基于信息熵的算法则容易收敛到局部解。1引言文中分析研究了这两种算法的实现方法，通过仿真实验来比近年来，一些学者应用群体智能的思想研究聚类问题。较其性能差别，针对其局限性，从聚类拆分、合并、孤立点处群体智能源于对简单个体组成的群落社会系统的模拟。理等几个方面

6、对基于信息熵的蚁群聚类算法进行了改进，从Denueubourg等首次模拟幼蚁自动分类及蚁尸聚积现象，提而在利用其收敛速度快的基础上提高聚类的准确性。实验出了聚类基本模型⋯。随后Lumer和Faieta改进其基本模结果表明，改进后的方法在聚类的准确性和收敛速度方面都型，提出了LF算法。文献[3][4]提出了基于信息熵的聚得到了很好的结果。类算法。文献[5]又提出了一种基于信息熵的蚁群聚类算法，将信息熵引入到LF算法中，改变了蚂蚁拾起和放下对象2基本蚁群聚类模型与LF算法实现的判定规则。2．1基本蚁群聚类模型在研究中发现，LF本身和基于信

7、息熵的蚁群聚类算法DeneubourgJL等提出的聚类基本模型⋯主要是基于单都有一定的局限性。LF算法需要调节很多参数，参数设置只蚂蚁拾起、放下物体的行为建模。一只任意移动的无负载就有一定难度，对收敛产生了不确定性，同时在复杂问题上的蚂蚁在遇到一个物体的时候，如果周围与该物体相同的物体越少，则拾起该物体的概率越大。蚂蚁拾起一个物体的可收稿日期：2008—05—27修回13期：2008—07—28能性按照如下公式计算：一179—Ppi~k：(㈩同时，一只任意移动的有负载的蚂蚁，如果周围与所背负物体相同的物体越多，则放下这个物体的概率也就

8、越大，该蚂蚁放下一个物体的可能性P按照如下公式计算：Pd(2)这样，可以保证不破坏大堆的物体，并且能够收集小堆的物体。在上面两个公式IIl是蚂蚁周围物体的个数，其中。和都是常数。2．2LF算法Lumer和Faieta将D