蚁群聚类介绍.txt

各类人工智能算法源代码哦

蚁群算法以及基于蚁群的聚类的简单介绍
关键词： 蚁群算法    聚类                                           

1 蚁群算法简介


蚁群算法是意大利学者Dorigo M等于1991年在法国巴黎召开的第一届欧洲人工生命会议上提出的。1996年，Dorigo M等发表了“The ant system: optimization by a colony of cooperating agents”一文，此文不但系统地阐述了蚁群算法的基本原理和数学模型，还将其与遗传算法、忌禁搜索算法、模拟退火算法、爬山法等进行了仿真实验比较，这样使得蚁群算法逐渐引起了世界许多国家研究者的关注，其应用领域也得到了迅速拓宽。目前人们对蚁群算法的研究已经由当初单一的TSP领域渗透到了多个领域，如车间作业调度问题，车辆路径问题，控制参数优化，聚类分析，图像处理等领域，在解决许多复杂优化问题方面已经展现出其优异的性能和巨大的发展潜力。


1.1 蚁群算法原理


自然界中的蚂蚁几乎是瞎子，但是由蚂蚁组成的群体，却体现出了高度机构化的社会组织，在许多情况下能完成远远超过单个蚂蚁个体能力的复杂任务。以蚂蚁觅食为例，看一下蚂蚁群体间是如何通过合作以找到一条从蚁巢到食物源最近的道路的。

图1显示了在蚁巢（N）和食物源（F）之间，蚂蚁已经找到了一条最短的道路。图2显示了当这条道路上出现了一个障碍物之后，蚂蚁会以等概率的方式从障碍物的两侧A、B通过。图3显示了经过一定时间之后，蚂蚁就会找到一条最短的道路（经过A侧）。这是因为蚂蚁在行进的过程中，会分泌一种化学刺激物——信息素留在道路上，而且能够感知这种物质的存在及其强度，并以此来指导自己运动的方向，倾向于信息素浓度较高的方向移动。


 
 
 
图1
 图2
 图3
 

1.2蚁群算法描述


以TSP问题为例，蚁群算法描述如下：

1）  将m只蚂蚁随机分配到n个城市中去；

2）  位于城市c上的蚂蚁k以概率Pk(c,s)选择一条从城市c到城市s的道路，其中


Jk(c)表示蚂蚁k还没有访问的城市列表； 表示边（c，s）上的信息素浓度； ，启发函数 ，这两个参数反映了信息素和启发函数的相对重要性。

3）  当所有蚂蚁完成环游，按下述公式进行信息素更新


是信息素挥发因子，其中


Lk是第k只蚂蚁的环游长度。

4）  看是否满足结束条件，如不满足则转到第二步。


基于蚁群算法的聚类（提要）
蚁群聚类算法

目的：考虑将Rn空间中的N个对象，分为K个类。

算法思路：将数据和类别之间建立一个对应图，形成一个N*K的矩阵，每一只蚂蚁都对所有的数据分类，然后根据分类结果去更新矩阵中的值，作为下一次分类的依据。

每一只蚂蚁都有一个长度为N的字符串S，用来表示找到的一个解。比如N=8 ，K=3 ，那么

2
 1
 3
 2
 2
 3
 2
 1
 

就代表了一种分类方式。第一个对象分到了第二类，第二个对象分到了第一类，等等。

信息素矩阵式一个N*K的矩阵，其中aij表示了对象i 属于类j 的信息素表达。具体算法如下：

1、  初始化。每一个蚂蚁都有一个S串，开始为空。信息素矩阵初始化为一个固定的值。

2、  在t时刻，采用下述策略产生新的S：

a)         根据S的长度，生成一个0，1之间的均匀分布的随机数，比如

0.69
 0.79
 0.986
 0.988
 0.23
 0.967
 0.091
 0.345
 

对每一个数，与事先给定的概率q0（0<q0<1，此处取q0=0.98）比较，如果小于q0，那么，这个对象的分类依据是看其信息素矩阵中哪一个对应最大，分到哪一类中。比如当前信息素矩阵如下所示（N=8，K=3），那么


1属于第二类，2属于第二类，3不参与分类，4不参与分类，5属于第二类，6属于第三类，7属于第二类，8属于第一类。对于3、4，采用下面的策略分类

b)        根据下式所用的概率进行分类


也就是哪一条边上的信息素多，它属于哪一条边的概率就大。

3、  根据得到的一组解，计算这个蚂蚁所得到的解的适应值。此处的适应值函数采取的是计算每一个对象与它所在的聚类中心的欧氏距离的平方和。假如给定一个含有N个对象的集合{x1，x2，……，xN}，现在要把它们分成K类，那么它的适应值函数是：


其中，xiv是第i个对象的第v个属性值，m是聚类中心，mjv是聚类j中的第v个属性的平均值， 是一个N*K的矩阵， 定义为


4、  有了一组解之后，进行局部搜索。策略如下：

a)         根据蚂蚁的适应值按升序排序，取前L个，记它们的解为Sk，k=1，……，L

b)        k=1

c)        St（i）=Sk（i），i=1，……， N，此处St是一个临时变量

d)        对于St中的每一个元素，根据概率pls（此处取0.01），让它的类别变成一个与原来不一样的随机的类别，比如原来的St(2)=3，那么如果需要变化（由概率pls来决定），则St(2)变为1，或者2

e)         根据St计算新的适应值Ft，如果新的适应值Ft比原来的Fk小，那么Sk=St，Fk=Ft；

f)         k=k+1；如果k≤L，转到第c步

5、  按照下述公式，进行信息素的更新。


此处ρ是信息素的挥发系数，其值为[0，1]，