蚁群聚类算法综述

计算机工程与应用2006.16

引言

聚类分析是数据挖掘领域中的一个重要分支[1],是人们认

和探索事物之间内在联系的有效手段,它既可以用作独立的

据挖掘工具,来发现数据库中数据分布的一些深入信息,也

以作为其他数据挖掘算法的预处理步骤。所谓聚类(clus- ring)就是将数据对象分组成为多个类或簇(cluster),在同一

簇中的对象之间具有较高的相似度,而不同簇中的对象差别大。传统的聚类算法主要分为四类[2,3]:划分方法,层次方法, 于密度方法和基于网格方法。

受生物进化机理的启发,科学家提出许多用以解决复杂优

问题的新方法,如遗传算法、进化策略等。1991年意大利学A.Dorigo等提出蚁群算法,它是一种新型的优化方法[4]。该算不依赖于具体问题的数学描述,具有全局优化能力。随后他

其他学者[5～7]提出一系列有关蚁群的算法并应用于复杂的组优化问题的求解中,如旅行商问题(TSP)、调度问题等,取得

著的成效。后来其他科学家根据自然界真实蚂蚁群堆积尸体分工行为,提出基于蚂蚁的聚类算法[8,9],利用简单的智能体

仿蚂蚁在给定的环境中随意移动。这些算法的基本原理简单懂[10],已经应用到电路设计、文本挖掘等领域。本文详细地讨现有蚁群聚类算法的基本原理与性能,在归纳总结的基础上

出需要完善的地方,以推动蚁群聚类算法在更广阔的领域内

到应用。

2聚类概念及蚁群聚类算法

一个簇是一组数据对象的集合,在同一个簇中的对象彼此

类似,而不同簇中的对象彼此相异。将一组物理或抽象对象分组为类似对象组成的多个簇的过程被称为聚类。它根据数据的内在特性将数据对象划分到不同组(或簇)中。聚类的质量是基于对象相异度来评估的,相异度是根据描述对象的属性值来计算的,距离是经常采用的度量方式。聚类可用数学形式化描述为:设给定数据集X={x

1

,x

2

,…,x

n

},!i∈{1,2,…,n},x

i

={x

i1

,x

i2

,

…,x

ip

}是X的一个对象,!l∈{1,2,…,p},x

il

是x

i

对象的一个

属性。根据数据的内在特性将X分解成C={C

1

,C

2

,…,C

k

}。其

中#

k

i=1

C

i

=X,!i,j∈{1,2,…,k},C

i

≠!,C

j

≠!,且(C

i

∧C

j

=!)

(i≠j)。K={X,C}称为一个聚类空间,C

i

称为聚类空间的第类

(簇)。

在数据挖掘中,聚类是一个活跃的研究领域[11],涉及的范

围从社会学、心理学、生物学到计算机科学。存在多种聚类方

法,这些方法不仅算法原理(决定运行时间及可测量性)不同,

而且许多基本特性也不相同,例如处理的数据对象,有关簇形

状的设想,最终划分的形式或必须提供的参数等。

计算机科学家通过模仿生物行为已经提出一系列解决问

题的新颖的成功方法。1991年Deneubour等介绍了基于蚂蚁

的聚类和分类[9]方法,当时主要用于机器人作业调度中。后来

Lumer等[8]修改了这个算法并将之应用于对数字数据分析上。

者简介:张建华(1978-),男,硕士生,主要研究领域为聚类分析,算法分析与设计。江贺(1980-),男,博士,讲师,主要研究领域为分布式算法设

计,无线传感器网络路由,数据挖掘等。张宪超(1971-),男,博士,副教授,主要研究领域为组合优化,算法分析与设计,并行分布式计算等。

蚁群聚类算法综述

张建华1,2江贺1张宪超1

1

(大连理工大学软件学院,大连116621)

2

(阜阳师范学院计算机系,安徽阜阳236032)

E-mail:jianhuazhang2008@https://www.doczj.com/doc/4511234490.html,

摘要数据聚类是重要的数据挖掘技术,在工程和技术等领域具有广泛的应用背景。蚁群算法作为一种新型的优化方

法,具有很强的鲁棒性和适应性。文章着重介绍蚁群聚类算法的研究情况,阐述当今流行的蚁群聚类算法的基本原理及

其特性,旨在为蚁群聚类算法的发展提供引导作用。

关键词数据挖掘蚁群算法聚类

文章编号1002-8331-(2006)16-0171-04文献标识码A中图分类号TP301

Survey of Ant Colony Clustering Algorithms

Zhang Jianhua1,2 Jiang He1 Zhang Xianchao1

1

(School of Software,Dalian University of Technology,Dalian 116621)

2

(Department of Computer,Fuyang Normal College,Fuyang,Anhui 236032)

Abstract:Clustering is an important technique of data mining.It is widely used in fields of engineering and technology.

Ant colony algorithms are robust and adaptable as novel optimization methods.This paper emphatically introduces the

research of ant colony clustering algorithms,and describes the basic principle and characteristics of existing popular ant

colony clustering algorithms.It affords direction for the future work of ant colony clustering algorithms.

Keywords:data mining,ant colony algorithm,clustering

1712006.16计算机工程与应用

来应用于数据挖掘[12],图像分割[13]和文本挖掘中[14]。2002年

broche等提出基于蚂蚁化学识别系统的聚类方法。总的说

,基于蚁群算法的聚类方法从原理上可以分为四种:(1)运用

蚁觅食的原理,利用信息素来实现聚类[15];(2)利用蚂蚁自我

集行为聚类;(3)基于蚂蚁堆的形成原理实现数据聚类;(4)运

蚁巢分类模型,利用蚂蚁化学识别系统进行聚类的。

算法分析

.1基于蚂蚁觅食的聚类算法

蚂蚁的觅食过程可以分为搜索食物和搬运食物两个环节[16]。

个蚂蚁在运动过程中都会在其经过的路径上释放信息素,并

够感知信息素及其强度。经过蚂蚁越多的路径其信息素越

,同时信息素自身也会随着时间的流逝而挥发。蚂蚁倾向于

息素强度高的方向移动,某一路径上走过的蚂蚁越多,后来

蚂蚁选择该路径的概率就越大,整个蚁群的行为表现出信息

反馈现象。基于蚂蚁信息素痕迹的聚类分析基本思想如下: 将数据视为具有不同属性的蚂蚁,聚类中心是蚂蚁所要寻

的“食物源”,那么数据聚类过程就可以看作蚂蚁寻找食物源过程[17]。假设数据对象为:X={X|X

i

=(x

i1

,x

i2

,…,x

im

),i=1,2,

,N},算法首先进行初始化,将各个路径的信息素置为0,即

j(0)=0,设置簇的半径为r,统计误差为"等参数。计算对象

到X

j

之间的加权欧氏距离d

ij

,计算各路径上的信息素

j(t):

!ij(t)=

1 d

ij

≤r

0 d

ij

>

"

r(

1)

对象X

i

合并到X

j

的概率为:

p

ij

(t)=

!

#

ij

(t)$

%

ij

(t)

s∈S

$!

#

sj

(t)$

%

sj

(t)

(2)

其中S={X

s

|d

sj

≤r,s=1,2,…,j,j+1,…,N}。如果p

ij

(t)大于

值p

,就将X

i

合并到X

j

的领域内。这里$

ij

是d

ij

的倒数,称它

能见度。#,%为调节因子[18],起到既防止所有蚂蚁均沿相同路得到相同结果所产生的停滞搜索,又再现了经典的贪心算法想。

该聚类方法中的#,%的选择对算法运行效率和聚类结果

响较大,选择不当将影响算法执行效率和效果,所需时间增

等缺点[19]。可以根据情况尝试不同的方法避免算法陷于局部优。算法虽然不需要预先指定簇的数目,但是由于簇的半径

预置的,所以聚类的规模受到限制。另外在实际计算中,在给

循环次数的条件下很难找到最优解。再者信息素分配策略、径搜索策略、最优解保留策略等方面均带有经验性和直觉

,导致算法的求解效率不高,收敛性差。

.2基于蚂蚁自我聚集行为的聚类算法

蚂蚁能够通过自我聚集行为构建一个树状结构,称之为蚂

树(AntTree)[20]。用蚂蚁表示数据并代表该树的节点,初始时蚁放在一个称为支点的固定点上,这个点相当于树根。蚂蚁

这棵树上或已经固定在树上的蚂蚁身上移动,来寻找适合自

的位置。假设蚂蚁能够到达树的任何地方并能粘在该结构的何位置,不过在结构树形成的过程中受对象间的作用,蚂蚁

趋于固定在树枝的末端[21,22]。树的局部结构及蚂蚁表示的数之间的相似性引导它的移动,当所有蚂蚁都在树上固定下来后,算法结束,获得对数据集的划分。

为了更好描述算法过程,采用蚂蚁表示的数据代表树中的

每个节点,用欧氏距离作为相似度尺度,用Sim(i,j)表示。相似度公式为:

Sim(i,j)=1-1

M

M

k=1

$(vik-vjk)

2

%

(3)

其中M表示每个数据对象的属性值,v

ik

表示数据对象i的

第k个属性。每对数据(d

i

,d

j

),i∈[1,N],j∈[1,N]的相似度值

Sim(i,j)在[0,1]之间(N表示数据集内的对象数),意味着d

i

,d

j

完全不同,表示它们相同。AntTree主要原理如下:

节点a

表示树根,蚂蚁逐步连接到这个初始节点上或连

接到固定在该节点的蚂蚁上,直到所有的蚂蚁均连接到结构上(蚂蚁树的停止标准)。移动的蚂蚁a

i

根据Sim(i,j)值和它的局

部邻居决定自身的位置。每只蚂蚁a

i

只有一个父亲结点,最多

有L

max

个孩子结点。对每只蚂蚁a

i

都定义一个相似度阀值T

Sim(a

i

)

和相异度阀值T

Dissim(a

i

)

,并且由a

i

进行局部更新,用来判断蚂蚁

a

i

表示的数据d

i

与其它蚂蚁表示的数据的相似或相异程度。蚂蚁的局部行为:第一只蚂蚁直接连接到a 0

上,对后来的

蚂蚁a

i

要考虑两种情况:第一种情况是a

i

在支点上。设a

+

为支

点上且与a

i

最相似的蚂蚁,如果a

i

和a

+

足够相似Sim(a

i

,a

+

)≥

T

Sim(a

i

)

,那么a

i

向a

+

移动,使它们能尽可能的聚集在同一子树

上,即在同一个簇内。否则(如a

i

与a

+

不相似)如果a

i

与a

+

足够

相异Sim(a

i

,a

+

)

Dissim(a

i

)

,那么它就连接在支点上,意味着创建

了一棵新子树,该子树上的蚂蚁将尽可能的与以a 0

为根的其

他子树上的蚂蚁不同。如果a

已经有L

max

孩子结点,那么a

i

向

a

+

移动。假如a

i

和a

+

既不足够相似也不足够相异,则用T

Sim(a

i

)

←

T

Sim(a

i

)

*#和TDissim(a

i

)

←T

Dissim(a

i

)

+%来更新阀值,增加a

i

下次连接

的概率。#,%为调节因子,实验中通常选择0.9与0.01,因为它能提供更好的结果[11]。由于分布的相似性,相似性阀值的减少速度明显高于相异性阀值的增加速度。

第二种情况a

i

在蚂蚁a

pos

上移动(a

+

表示a

pos

上与a

i

最相似

的蚂蚁)。如果a

pos

的孩子结点少于L

max

且a

i

与a

pos

足够相似

(Sim(a

i

,a

pos

)≥T

Sim(a

i

)

),与a

pos

上其他蚂蚁足够相异(ie.Sim(a

i

,

a

+

)

Dissim(a

i

)

),那么a

i

就连接在a

pos

上,否则蚂蚁a

i

随机地向a

pos

的邻居移动。根据需要按前面的方式更新阀值,寻找合适的位置,当所有蚂蚁都连接好时算法结束。

利用该算法得到的簇更接近于数据的真实分类,并且当蚂

蚁连接上以后就不再移动,所以平均执行时间相当低。但是算法的初始化(a

的选取)很重要,它影响整个算法的质量。此外

对阀值的更新策略也是影响该算法的最重要并且最难确定的因素。

3.3基于蚂蚁堆形成原理实现聚类

蚁堆聚类方法的基本机制是工蚁堆积蚂蚁尸体过程,小蚁

堆不断吸引工蚁堆积更多的死蚂蚁,通过正反馈导致蚁堆逐渐增大。基于这种模型主要有下面几种算法:

3.3.1基于智能体模型的算法

1991年Deneubourg[23]等提出基于智能体(人工蚂蚁)的模

72计算机工程与应用2006.16

来模仿蚂蚁行为对数据进行聚类,人工蚂蚁沿着网格单元移,每个单元只含一个对象。没有搬运数据对象的蚂蚁碰到对时就会以某个概率拾起它,这个概率依赖对该对象周围的相对象密度的评估,如果密度高则拾起的概率就低;携带对象

蚂蚁遇到空单元或搬运的对象与邻近的对象相似时就会以

个概率放下它,放下的概率也依赖对周围对象类型密度的评,如果密度大时放下的概率就高,结果相同类型的对象都被

集在一起。数据对象在空间的分布状态将影响聚类结果,其本思想如下。

假设所有的数据对象都随机地分布在二维的与数据集成

例伸缩地网格空间[24]。处于网格中的两个对象o

i

j

之间的

离(相似度)d(o

i

,o

j

)是它们的欧氏距离,如果o

i

和o

j

是同一

对象(即o

i

和o

j

相似),则d(o

i

,o

j

)=0,反之d(o

i

,o

j

)=1,从而

到二进制的相似度矩阵。设若干个蚂蚁在二维网格上不断运并反复执行拾起或放下对象操作,蚂蚁某时刻在r位置发现象o

i

,则它的局部密度可以由下面的公式来计算:

f(o

i

)=

1

s

2

∑

o

j

[1-d

(o

i

,o

j

2]

if f>0

0 otherwis

"

$

$

$

#

$

$

$

%

e

(4)

其中f(o

i

)为相似度密度,o

j

∈Grid

(s×s)

(r),单元r的邻域面

为s×s,!为相异度因子。蚂蚁在运动过程中拾起对象的概率(o

i

)和放下对象的概率p

d

(o

i

)分别为:

p

p

(o

i

)=(k

1

k

1

+f(o

i

))

2

(5)

p

(o

i

)=2

f(o

i

)if f(o

i

)

2

1 if f(o

i

)≥k

2

(

(6)

其中k

1

,k

2

都是阀值常量。

该算法实际上是一种基于网格和密度的聚类方法[16]。为了于处理髙维数据空间,首先将其映射到某一低维网格空间, 射要确保簇内距离小于簇间距离,同时网格的精细度将会影聚类质量。蚂蚁拾起或放下对象受局部相似度密度f(o

i

)的

响,局部相似度密度大,拾起的概率p

p

(o

i

)小,数据不易从该

中移走,同时放下的概率p

d

(o

i

)大,对象倾向于留在该簇中,

之亦然。该算法不必预先指定簇的数目,并能构造任意形状簇。

3.2基于蚂蚁的聚类

基于蚂蚁的聚类(ANT-BASED CLUSTERING)[25]也是受蚁分类启发的,实际上是对上述算法的改进,主要过程与前面似。主要修改了几个重要的特性,首先修改了局部相似度密,此处的邻域密度函数为f

(o

i

):

f

*

(o

i

)=

1

s

2

∑

o

j

[1-d

(o

i

,o

j

)

2]

if t=true 0 otherwis )

$

$

$

#

$

$

$

%

e

(7)

其中:

t=f

*

(o

i

)>0∧+

o

j

(1-d

i

,o

j

)

2)

>0(8)

这样拾起或放下的概率公式变为: p

p

(o

i

)=

1.0 if f

*

(o

i

)≤1.0

1

f(o

i

)

2

otherwis

)

$

$

$$

#

$

$

$$

%

e(

9)

p

d

(o

i

)=1

.0 if f

*

(o

i

)≥1.0

f

*

(o

i

)

4

otherwis

-

e

(10)

从(4)和(7)可以看出它对网格单元进行了处理,这样有助

于对象形成的簇更加紧凑。此外约束条件+o

i

(1-d(o

i

,o

j

)/!)>

0)能处理带有非常高的相异点的邻居,它增大了两个簇的分离空间。

其次,用了一个短期寄存器记下前面放下对象的位置,当

拾起一个对象时可以参考寄存器来指导它移动,这样能向最近放下相似对象的位置移动,降低时间复杂度。再次,在计算f

*

(o

i

)

时考虑增加感知半径来扩大邻域,把一些小簇合并成一个大簇。最后,对相异度因子!作适当的修改。适当的选择相异度因子很重要,选择太小的!就不能形成簇,太大时会导致过多的

簇合并,极限情况下所有对象聚集在一个簇中。选择适当的!

主要依靠同一个簇中每对对象间的相异度,因为!影响蚂蚁的

拾起/放下行为,所以可以通过跟踪蚂蚁的行为获得自动适应

的!,从而调整!的值。

3.3.3混合聚类方法

上面虽然对邻域密度函数进行了修改,但最终聚类的数目

往往太高,而且收敛很慢。于是2000年Monmarche建议一个单元可以放置多个对象,每个拥有物品的单元相当于一个簇。每只蚂蚁a

i

具有的承载能力为c(a

i

),代替过去一只蚂蚁一次只

能搬运一个对象的情况。概率性的从一个堆上最多拾起对象为c(a

i

),并且往堆上丢下对象时要根据堆的特性,如堆中对象间

的平均相异度。当蚂蚁决定拾起对象时,挑选与堆中心相异度最大的对象。此时蚂蚁a

i

的运载能力c(a

i

)有两种情况c(a

i

)=1或

c(a

i

)=∞,即可以搬运一个对象,也可以是整个堆。Monmarche

建议结合K-means方法进行聚类,主要过程如下:

最初同样利用基于蚂蚁算法来形成初始的簇。由于划分时

间太长,所以在算法收敛之前就终止了算法,致使创建的划分

存在错误划分,所以使用k-means算法除去小的分类错误,并

分配“自由”对象,即算法停止时仍然有单独存在单元上的对象或蚂蚁仍在搬运的对象。这虽然能除去分类中的错误,但是k- means算法是局部优化算法,不能得到高质量的簇,所以需要

再次利用基于蚂蚁的算法。

这次是对对象堆上而不是单个对象运用算法。前面基于蚂

蚁的算法同样适用于堆,这些堆可以像单个对象那样再次被拾起或放下,再次构成新的簇。但像前面那样仍然有未分配的堆, 因而再次使用k-means算法来获得最终的划分。这次因为提供给k-means的输入已经很接近最佳了,所以输出的结果质量很高。与这个方法相似的另一种是与模糊c-means相结合的方法[24]

,基于相对简单智能体直接或间接的反馈完成聚类。

3.4基于蚂蚁化学识别系统的聚类方法

现实中的蚂蚁为了保护自己的巢穴不被敌人或食客攻击

破坏,必须具有区别伙伴和敌方的能力,它是靠识别群体间的

气味来实现的。当两只蚂蚁相遇时分别检查对方表皮所散发的气味(也叫标签),并与自身的模板比较。模板是蚂蚁在幼年时

期获得的,并在成长过程中不断更新。标签是由蚂蚁基因及蚂蚁间不断交换化学物质决定的。同伴间通过不断交换化学物质建立群体气味,该气味可以被每个伙伴识别,不同群体具有不

同的气味,同一群体分享相同的气味,这就是所谓的“群体圈”, 也是化学识别系统的基本原理。

1732006.16计算机工程与应用

2002年Labroche等提出叫做蚂蚁簇(AntClust)的聚类方

,主要是利用化学识别系统原理来聚类的。为了更好地说明

个方法,给每只蚂蚁a

i

定义如下参数:由蚂蚁巢穴的属性决

的标签Label

i

,可以代表巢,开始蚂蚁不受任何巢穴的影响,

以Label

i

=0,随后标签不断变换直到蚂蚁找到最好的巢为

。模板是由蚂蚁的基因Genetic

i

和接受阀值Template

i

组成

,前者对应于数据集的对象且在算法过程中不断变化,后者在初始化阶段获得的,它是蚂蚁与其它蚂蚁相遇期间观察到最大相似度Max(Sim(i,.))和平均相似度Sim(i,.)的函数,它动态的,蚂蚁每次和其它蚂蚁相会后对它进行修改。Template

i

←

Sim(i,.)+Max(Sim(i,.))

2(

11)

评价因子M

i

反映蚂蚁间的相遇情况。相同标签的蚂蚁相

M

i

增加,反之M

i

减少,开始时M

i

=0,它反映蚂蚁a

i

所在巢穴

规模。M

+

i

表示蚂蚁被接受程度,如果具有相同标签的蚂蚁相

或两只蚂蚁彼此接受对方,M

+

i

增加,否则蚂蚁不接受时减少。

蚁接受与否可根据下面公式判断,设a

i

,a

j

分别表示两只蚂

,则:

Accept an ce(a

i

,a

j

)"(Sim(a

i

,a

j

)>Template

i

)∧

(Sim(a

i

,a

j

)>Template

j

)(12)

蚂蚁簇算法主要是反复随机选择两只蚂蚁并模仿它们相

过程:

(1)当两只都没有巢的蚂蚁相遇并彼此接受时将创建一个

的巢(初始簇),并作为“种子”聚集相似蚂蚁以便产生最终簇;

(2)当有巢的蚂蚁遇到可以接受没有巢的蚂蚁时,没有巢

蚂蚁加入该巢内,通过加入相似蚂蚁来扩大现存的簇;

(3)属于同一个巢的蚂蚁在接受的情况下增加评价因子和,

巢变得更健壮;

(4)当两个同伴相遇且不能彼此接受,则整体最差的蚂蚁

从巢中被驱除出去,这样通过除去不理想的蚂蚁,使巢变得

完美;

(5)不同巢的蚂蚁相遇且彼此接受时,合并它们的巢,即合

相似的簇,小簇被大簇吸收。算法结束时蚂蚁集中在有限数的巢内,巢就是期望得到的划分。

反复利用这些过程,能得到最终想要的划分。该算法能处

任意类型的数据,具有很好的鲁棒性和适应性。但是如何确迭代次数保证算法收敛有待进一步研究。另外巢的删除阀值接影响到聚类结果的稳定性,目前此阀值的设定尚未有效的决,尽管有些文献对这作了修改,但没有足够的理论依据,不

靠。

总结

本文分析了现在流行的有关蚁群的聚类算法,针对每种方

分别从它的基本思想、聚类原理及主要步骤上进行了论述与

析。它们的不同之处主要在蚂蚁个体间的通信介质不同,有

是根据气味有的完全避开气味。根据气味通信的又分为两

:(1)根据其所经路径上留下的信息素,如基于蚂蚁觅食的聚

方法;(2)根据蚂蚁自身携带的气味,如基于蚂蚁化学识别系

的聚类方法。另外是根据对象的空间分布状态指导蚂蚁间的

相互作用完成聚类的,如基于蚂蚁堆的形成原理的聚类方法都

是根据对象在网格上的分布情况实现的;其中基于蚂蚁的混合

聚类方法,交替使用蚁群聚类方法和k-means算法,加速算法

收敛并提高了聚类质量。蚁群聚类方法具有许多特有的特性,

如灵活性、健壮性、分布性和自组织性等,这些特性使其非常适

合本质上是分布、动态及又要交错的问题求解中,能解决无人

监督的聚类问题,具有广阔的前景。但仍存在很多问题需要解

决,有待进一步研究。(收稿日期:2005年9月)

参考文献

1.Chen MS.Data mining:an overview from a database perspective[J]. IEEE Trans on Knowledge and data engineering,1996;8(6):866～883

2.P Berkhin.Survey of clustering data mining techniques[R].Technical report,Accure Software,San Jose,CA,2002

3.钱卫宁等.从多角度分析聚类算法[J].软件学报,2002;13(8)

4.A Dorigo,M Dorigo,V Maniezzo.Distributed optimization by ant colo- nies[C].In:European Conference on Artificial Life,1991:134～142

5.M Dorigo et al.Ant system:optimization by a colony of cooperating agents[J].IEEE Transactions on Systems,Man,and Cybemtics,Part B, 1996;26(1):29～41

6.M Dorigo,L M Gambardella.Ant colony system:a cooperative learning approach to the traveling salesman problem[J].IEEE Transactions on Evolutionary Computation,1997;1(1):53～66

7.M Dorigo et al.Guest editorial:special section on ant colony optimi- zation[J].IEEE Transactions on Evolutionary Computation,2002;6(4): 317～319

8.E Bonabeau,M Dorigo,G Theraulaz.Swarm Intelligence-From Natural to Artificial System[M].New York,NY:Oxford University Press,1999

9.J-L Deneubourg,S Goss,N Franks et al.The dynamics of collective sorting:Robot-like ants and ant-like robots[C].In:J-A Meyer,S Wilson eds.Proceedings of the First international Conference on Simulation of Adaptive haviour,From Animals to Animals J,MIT Press,Cambridge MA,1991:356～365

10.E Lumer,B Faieta.Diversity and adaptation in populations of clustering ants[C].In:Proceedings of the Third International Conference on Simu- lation of Adaptive Behavior:From Animals to nimats 3,MIT Press,

各种聚类算法及改进算法的研究

论文关键词：数据挖掘；聚类算法；聚类分析论文摘要：该文详细阐述了数据挖掘领域的常用聚类算法及改进算法，并比较分析了其优缺点，提出了数据挖掘对聚类的典型要求，指出各自的特点，以便于人们更快、更容易地选择一种聚类算法解决特定问题和对聚类算法作进一步的研究。并给出了相应的算法评价标准、改进建议和聚类分析研究的热点、难点。上述工作将为聚类分析和数据挖掘等研究提供有益的参考。 1 引言随着经济社会和科学技术的高速发展，各行各业积累的数据量急剧增长，如何从海量的数据中提取有用的信息成为当务之急。聚类是将数据划分成群组的过程，即把数据对象分成多个类或簇，在同一个簇中的对象之间具有较高的相似度，而不同簇中的对象差别较大。它对未知数据的划分和分析起着非常有效的作用。通过聚类，能够识别密集和稀疏的区域，发现全局的分布模式，以及数据属性之间的相互关系等。为了找到效率高、通用性强的聚类方法人们从不同角度提出了许多种聚类算法，一般可分为基于层次的，基于划分的，基于密度的，基于网格的和基于模型的五大类。 2 数据挖掘对聚类算法的要求(1)可兼容性：要求聚类算法能够适应并处理属性不同类型的数据。(2)可伸缩性：要求聚类算法对大型数据集和小数据集都适用。(3)对用户专业知识要求最小化。(4)对数据类别簇的包容性：即聚类算法不仅能在用基本几何形式表达的数据上运行得很好，还要在以其他更高维度形式表现的数据上同样也能实现。(5)能有效识别并处理数据库的大量数据中普遍包含的异常值，空缺值或错误的不符合现实的数据。(6)聚类结果既要满足特定约束条件，又要具有良好聚类特性，且不丢失数据的真实信息。(7)可读性和可视性：能利用各种属性如颜色等以直观形式向用户显示数据挖掘的结果。(8)处理噪声数据的能力。(9)算法能否与输入顺序无关。 3 各种聚类算法介绍随着人们对数据挖掘的深入研究和了解，各种聚类算法的改进算法也相继提出，很多新算法在前人提出的算法中做了某些方面的提高和改进，且很多算法是有针对性地为特定的领域而设计。某些算法可能对某类数据在可行性、效率、精度或简单性上具有一定的优越性，但对其它类型的数据或在其他领域应用中则不一定还有优势。所以，我们必须清楚地了解各种算法的优缺点和应用范围，根据实际问题选择合适的算法。 3.1 基于层次的聚类算法基于层次的聚类算法对给定数据对象进行层次上的分解，可分为凝聚算法和分裂算法。 (1)自底向上的凝聚聚类方法。这种策略是以数据对象作为原子类，然后将这些原子类进行聚合。逐步聚合成越来越大的类，直到满足终止条件。凝聚算法的过程为：在初始时，每一个成员都组成一个单独的簇，在以后的迭代过程中，再把那些相互邻近的簇合并成一个簇，直到所有的成员组成一个簇为止。其时间和空间复杂性均为O(n2)。通过凝聚式的方法将两簇合并后，无法再将其分离到之前的状态。在凝聚聚类时，选择合适的类的个数和画出原始数据的图像很重要。 [!--empirenews.page--] (2)自顶向下分裂聚类方法。与凝聚法相反，该法先将所有对象置于一个簇中，然后逐渐细分为越来越小的簇，直到每个对象自成一簇，或者达到了某个终结条件。其主要思想是将那些成员之间不是非常紧密的簇进行分裂。跟凝聚式方法的方向相反，从一个簇出发，一步一步细化。它的优点在于研究者可以把注意力集中在数据的结构上面。一般情况下不使用分裂型方法，因为在较高的层很难进行正确的拆分。 3.2 基于密度的聚类算法很多算法都使用距离来描述数据之间的相似性，但对于非凸数据集，只用距离来描述是不够的。此时可用密度来取代距离描述相似性，即基于密度的聚类算法。它不是基于各种各样的距离，所以能克服基于距离的算法只能发现“类圆形”的聚类的缺点。其指导思想是：只要一个区域中的点的密度（对象或数据点的数目）大过某个阈值，就把它加到与之相近的聚类中去。该法从数据对象的分布密度出发，把密度足够大的区域连接起来，从而可发现任意形状的簇，并可用来过滤“噪声”数据。常见算法有DBSCAN，DENCLUE 等。[1][2][3]下一页 3.3 基于划分的聚类算法给定一个N个对象的元组或数据库，根据给定要创建的划分的数目k，将数据划分为k个组，每个组表示一个簇类（<=N）时满足如下两点：(1)每个组至少包含一个对象；(2)每个对

蚁群算法应用

大连理工大学 研究生必修课 作业 课程名称：现代物流管理 研究生姓名：徐静学号：21511149 作业成绩： 任课教师(签名) 交作业日时间：2016 年6 月1日

蚁群算法在TSP问题上的应用 摘要蚁群算法是受现实蚂蚁群体行为启发而得出的一类仿生算法。本文以解决TSP问题为基础,系统地介绍了蚁群算法从诞生到成熟过程中几个代表性的算法。在阐述算法基本思想的前提下，着重论述算法的创新之处。 关键词蚁群算法，TSP问题，蚁群优化 1引言 蚁群算法也称作蚁群优化(Ant Colony Optimization，ACO)，最早是由Dorigo及其研究同伴所提出，用于求解诸如旅行商问题之类的组合优化问题。自然界蚂蚁在其经过的路径上会留下某种生物信息物质(信息素)，该物质会吸引蚁群中的其它成员再次选择该段路径；食物与巢穴之前较短的路径容易积累较多的信息素，因而使得更多的蚂蚁选择走该段路径，最终几乎所有的蚂蚁都集中在最短路径上完成食物的搬运。Dorigo等从此现象中抽象出路径选择和信息素积累的数学模型，作为蚁群算法的核心，并通过对蚂蚁寻找最短路径的计算机模拟，实现了对TSP问题的求解。自此，蚁群算法越来越多地被用于求解其它的组合优化问题，也被推广到工业工程上应用。 蚁群算法特点是并发性、鲁棒性、正反馈性等。在蚁群算法求解问题的过程中，利用蚁群在问题空间中同时构造问题的多个解体现了算法的并发性。蚁群不会因为单个蚂蚁寻找到较差的解或者因为问题空间发生改变而使得算法丧失作用，这体现了算法的鲁棒性。在蚂蚁构造问题解的过程中，以蚁群觅食行为为例，会在经过的解路径上释放信息素，而解空间中获得信息素越多的路径，对蚂蚁的吸引力就越大，使更多的蚂蚁经过该路径并进一步在上面释放信息素，这体现了算法的正反馈性。 TSP问题代表一类组合优化问题，在实际工程中有许多应用，如计算机联网、电子地图、交通诱导、电气布线、VLSI单元布局、ATM分组交换网等。鉴于其重要的工程与理论价值，TSP常作为算法性能研究的典型算例。求其最优解的代价是指数级的，因此对其近似解的研究一直是算法设计的一个重要课题。 TSP问题是典型的NP完全问题，许多算验证法及算法效率测试都以TSP问题为基础。在蚁群算法研究中，第一个蚁群算法，蚂蚁系统,就是在TSP问题的基础上提出来的。而后，依据TSP问题，又提出了蚁群算法系列中具有代表性的蚁群系统、最大——最小蚂蚁系统。 本文以TSP问题为基础,对蚁群算法的基本问题及典型的蚁群算法进行了综述。涉及到算法的基本问题、算法描述、算法改进及意义。通过研究总结了蚁群算法的发展历程和实现思想。

蚁群聚类算法综述

计算机工程与应用2006.16 引言 聚类分析是数据挖掘领域中的一个重要分支[1],是人们认 和探索事物之间内在联系的有效手段,它既可以用作独立的 据挖掘工具,来发现数据库中数据分布的一些深入信息,也 以作为其他数据挖掘算法的预处理步骤。所谓聚类(clus- ring)就是将数据对象分组成为多个类或簇(cluster),在同一 簇中的对象之间具有较高的相似度,而不同簇中的对象差别大。传统的聚类算法主要分为四类[2,3]:划分方法,层次方法, 于密度方法和基于网格方法。 受生物进化机理的启发,科学家提出许多用以解决复杂优 问题的新方法,如遗传算法、进化策略等。1991年意大利学A.Dorigo等提出蚁群算法,它是一种新型的优化方法[4]。该算不依赖于具体问题的数学描述,具有全局优化能力。随后他 其他学者[5～7]提出一系列有关蚁群的算法并应用于复杂的组优化问题的求解中,如旅行商问题(TSP)、调度问题等,取得 著的成效。后来其他科学家根据自然界真实蚂蚁群堆积尸体分工行为,提出基于蚂蚁的聚类算法[8,9],利用简单的智能体 仿蚂蚁在给定的环境中随意移动。这些算法的基本原理简单懂[10],已经应用到电路设计、文本挖掘等领域。本文详细地讨现有蚁群聚类算法的基本原理与性能,在归纳总结的基础上 出需要完善的地方,以推动蚁群聚类算法在更广阔的领域内 到应用。 2聚类概念及蚁群聚类算法 一个簇是一组数据对象的集合,在同一个簇中的对象彼此 类似,而不同簇中的对象彼此相异。将一组物理或抽象对象分组为类似对象组成的多个簇的过程被称为聚类。它根据数据的内在特性将数据对象划分到不同组(或簇)中。聚类的质量是基于对象相异度来评估的,相异度是根据描述对象的属性值来计算的,距离是经常采用的度量方式。聚类可用数学形式化描述为:设给定数据集X={x 1 ,x 2 ,…,x n },!i∈{1,2,…,n},x i ={x i1 ,x i2 , …,x

蚁群算法综述

智能控制之蚁群算法 1引言 进入21世纪以来，随着信息技术的发展，许多新方法和技术进入工程化、产品化阶段，这对自动控制技术提出新的挑战，促进了智能理论在控制技术中的应用，以解决用传统的方法难以解决的复杂系统的控制问题。随着计算机技术的飞速发展，智能计算方法的应用领域也越来越广泛。 智能控制技术的主要方法有模糊控制、基于知识的专家控制、神经网络控制和集成智能控制等,以及常用优化算法有:遗传算法、蚁群算法、免疫算法等。 蚁群算法是近些年来迅速发展起来的，并得到广泛应用的一种新型模拟进化优化算法。研究表明该算法具有并行性，鲁棒性等优良性质。它广泛应用于求解组合优化问题，所以本文着重介绍了这种智能计算方法，即蚁群算法，阐述了其工作原理和特点，同时对蚁群算法的前景进行了展望。 2 蚁群算法概述 1、起源 蚁群算法(ant colony optimization, ACO)，又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型技术。它由Marco Dorigo于1992年在他的博士论文中引入，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。 Deneubourg及其同事(Deneubourg et al.,1990; Goss et al.,1989)在可监控实验条件下研究了蚂蚁的觅食行为，实验结果显示这些蚂蚁可以通过使用一种称为信息素的化学物质来标记走过的路径，从而找出从蚁穴到食物源之间的最短路径。 在蚂蚁寻找食物的实验中发现，信息素的蒸发速度相对于蚁群收敛到最短路径所需的时间来说过于缓慢，因此在模型构建时，可以忽略信息素的蒸发。然而当考虑的对象是人工蚂蚁时，情况就不同了。实验结果显示，对于双桥模型和扩展双桥模型这些简单的连接图来说，同样不需要考虑信息素的蒸发。相反，在更复杂的连接图上，对于最小成本路径问题来说，信息素的蒸发可以提高算法找到好解的性能。 2、基于蚁群算法的机制原理 模拟蚂蚁群体觅食行为的蚁群算法是作为一种新的计算智能模式引入的，该算法基于如下假设： （1）蚂蚁之间通过信息素和环境进行通信。每只蚂蚁仅根据其周围的环境作出反应，也只对其周围的局部环境产生影响。 （2）蚂蚁对环境的反应由其内部模式决定。因为蚂蚁是基因生物，蚂蚁的行为实际上是其基因的自适应表现，即蚂蚁是反应型适应性主体。 （3）在个体水平上，每只蚂蚁仅根据环境作出独立选择；在群体水平上，单

启发式优化算法综述

启发式优化算法综述 一、启发式算法简介 1、定义 由于传统的优化算法如最速下降法，线性规划，动态规划，分支定界法，单纯形法，共轭梯度法，拟牛顿法等在求解复杂的大规模优化问题中无法快速有效地寻找到一个合理可靠的解，使得学者们期望探索一种算法:它不依赖问题的数学性能，如连续可微，非凸等特性; 对初始值要求不严格、不敏感，并能够高效处理髙维数多模态的复杂优化问题，在合理时间内寻找到全局最优值或靠近全局最优的值。于是基于实际应用的需求，智能优化算法应运而生。智能优化算法借助自然现象的一些特点，抽象出数学规则来求解优化问题，受大自然的启发，人们从大自然的运行规律中找到了许多解决实际问题的方法。对于那些受大自然的运行规律或者面向具体问题的经验、规则启发出来的方法，人们常常称之为启发式算法（Heuristic Algorithm）。 为什么要引出启发式算法，因为NP问题，一般的经典算法是无法求解，或求解时间过长，我们无法接受。因此，采用一种相对好的求解算法，去尽可能逼近最优解，得到一个相对优解，在很多实际情况中也是可以接受的。启发式算法是一种技术，这种技术使得在可接受的计算成本内去搜寻最好的解，但不一定能保证所得的可行解和最优解，甚至在多数情况下，无法阐述所得解同最优解的近似程度。 启发式算法是和问题求解及搜索相关的，也就是说,启发式算法是为了提高搜索效率才提出的。人在解决问题时所采取的一种根据经验规则进行发现的方法。其特点是在解决问题

时,利用过去的经验,选择已经行之有效的方法，而不是系统地、以确定的步骤去寻求答案，以随机或近似随机方法搜索非线性复杂空间中全局最优解的寻取。启发式解决问题的方法是与算法相对立的。算法是把各种可能性都一一进行尝试，最终能找到问题的答案，但它是在很大的问题空间内，花费大量的时间和精力才能求得答案。启发式方法则是在有限的搜索空间内，大大减少尝试的数量，能迅速地达到问题的解决。 2、发展历史 启发式算法的计算量都比较大，所以启发式算法伴随着计算机技术的发展，才能取得了巨大的成就。纵观启发式算法的历史发展史： 40年代：由于实际需要，提出了启发式算法（快速有效）。 50年代：逐步繁荣，其中贪婪算法和局部搜索等到人们的关注。 60年代: 反思，发现以前提出的启发式算法速度很快，但是解得质量不能保证，而且对大规模的问题仍然无能为力（收敛速度慢）。 70年代：计算复杂性理论的提出，NP问题。许多实际问题不可能在合理的时间范围内找到全局最优解。发现贪婪算法和局部搜索算法速度快，但解不好的原因主要是他们只是在局部的区域内找解，等到的解没有全局最优性。由此必须引入新的搜索机制和策略。 Holland的遗传算法出现了（Genetic Algorithm）再次引发了人们研究启发式算法的兴趣。 80年代以后：模拟退火算法（Simulated Annealing Algorithm），人工神经网络（Artificial Neural Network），禁忌搜索（Tabu Search）相继出现。 最近比较火热的：演化算法（Evolutionary Algorithm）, 蚁群算法（Ant Algorithms），拟人拟物算法，量子算法等。

比较专家系统、模糊方法、遗传算法、神经网络、蚁群算法的特点及其适合解决的实际问题

比较专家系统、模糊方法、遗传算法、神经网络、蚁群算法的特点及其适合解决的实际问题 一、专家系统(Expert System) 1，什么是专家系统？ 在日常生活中大家所认知的“专家”一般都拥有某一特定领域的大量专业知识，以及丰富的实际经验。在解决问题时，专家们通常拥有一套独特的思维方式，能较圆满地解决一类困难问题，或向用户提出一些建设性的建议等。 专家系统一般定义为一个具有智能特点的计算机程序。 它的智能化主要表现为能够在特定的领域内模仿人类专家思维来求解复杂问题。因此，专家系统必须包含领域专家的大量知识，拥有类似人类专家思维的推理能力，并能用这些知识来解决实际问题。 专家系统的基本结构如图1所示，其中箭头方向为数据流动的方向。 图1 专家系统的基本组成 专家系统通常由知识库和推理机两个主要组成要素。 知识库存放着作为专家经验的判断性知识,例如表达建议、 推断、 命令、 策略的产生式规则等, 用于某种结论的推理、 问题的求解,以及对于推理、 求解知识的各种控制知识。 知识库中还包括另一类叙述性知识, 也称作数据,用于说明问题的状态,有关的事实和概念,当前的条件以及常识等。

专家系统的问题求解过程是通过知识库中的知识来模拟专家的思维方式的，因此，知识库是专家系统质量是否优越的关键所在，即知识库中知识的质量和数量决定着专家系统的质量水平。一般来说，专家系统中的知识库与专家系统程序是相互独立的，用户可以通过改变、完善知识库中的知识内容来提高专家系统的性能。 推理机实际上是一个运用知识库中提供的两类知识,基于木某种通用的问题求解模型,进行自动推理、 求解问题的计算机软件系统。 它包括一个解释程序, 用于决定如何使用判断性知识推导新的知识, 还包括一个调度程序, 用于决定判断性知识的使用次序。 推理机的具体构造取决于问题领域的特点,及专家系统中知识表示和组织的方法。 推理机针对当前问题的条件或已知信息，反复匹配知识库中的规则，获得新的结论，以得到问题求解结果。在这里，推理方式可以有正向和反向推理两种。正向推理是从前件匹配到结论，反向推理则先假设一个结论成立，看它的条件有没有得到满足。由此可见，推理机就如同专家解决问题的思维方式，知识库就是通过推理机来实现其价值的。 人机界面是系统与用户进行交流时的界面。通过该界面，用户输入基本信息、回答系统提出的相关问题，并输出推理结果及相关的解释等。 综合数据库专门用于存储推理过程中所需的原始数据、中间结果和最终结论，往往是作为暂时的存储区。解释器能够根据用户的提问，对结论、求解过程做出说明，因而使专家系统更具有人情味。 知识获取是专家系统知识库是否优越的关键，也是专家系统设计的“瓶颈”问题，通过知识获取，可以扩充和修改知识库中的内容，也可以实现自动学习功能。 2，专家系统的特点 在功能上, 专家系统是一种知识信息处理系统, 而不是数值信息计算系统。在结构上, 专家系统的两个主要组成部分 – 知识库和推理机是独立构造、分离组织, 但又相互作用的。在性能上, 专家系统具有启发性, 它能够运用专家的经验知识对不确定的或不精确的问题进行启发式推理, 运用排除多余步骤或减少不必要计算的思维捷径和策略；专家系统具有透明性, 它能够向用户显示为得出某一结论而形成的推理链, 运用有关推理的知识(元知识)检查导出结论的精度、一致性和合理性, 甚至提出一些证据来解释或证明它的推理；专家系统具有灵活性, 它能够通过知识库的扩充和更新提高求解专门问题的水平或适应环境对象的某些变化,通过与系统用户的交互使自身的性能得到评价和监护。 3，专家系统适合解决的实际问题 专家系统是人工智能的一个应用，但由于其重要性及相关应用系统之迅速发展，它已是信息系统的一种特定类型。专家系统一词系由以知识为基础的专家系统(knowledge-based expert system)而来，此种系统应用计算机中储存的人类知识，解决一般需要用到专家才能处理的问题，它能模仿人类专家解决特定问题时的推理过程，因而可供非专家们用来增进问题解决的能力，同时专家们也可把它视为具备专业知识的助理。由于在人类社会中，专家资源确实相当稀少，有了专家系统，则可使此珍贵的专家知识获得普遍的应用。 专家系统技术广泛应用在工程、科学、医药、军事、商业等方面，而且成果相当丰硕，甚至在某些应用领域，还超过人类专家的智能与判断。其功能应用领

蚁群算法

社会性动物的群集活动往往能产生惊人的自组织行为，如个体行为显得盲目的蚂蚁在组成蚁群后能够发现从蚁巢到食物源的最短路径。生物学家经过仔细研究发现蚂蚁之间通过一种称之为“外激素”的物质进行间接通讯、相互协作来发现最短路径。受其启发，1991年由意大利学者 M. Dorigo，V. Maniezzo 和 A. Colorni 通过模拟蚁群觅食行为提出了一种基于种群的模拟进化算法——蚁群优化。本文阐述了算法的基本原理及特性以及一些优化的蚁群算法，阐述了蚁群算法在数据挖掘中的应用,最后总结了蚁群算法在数据挖掘应用中尚待解决的问题。 关键词: 蚁群算法; 蚁群优化; 数据挖掘 正文文字大小：大中小 1 蚁群算法原理 自1991年由意大利学者 M. Dorigo，V. Maniezzo 和 A. Colorni 通过模拟蚁群觅食行为提出了一种基于种群的模拟进化算法——蚁群优化。该算法的出现引起了学者们的极大关注，蚁群算法的特点： ①其原理是一种正反馈机制或称增强型学习系统; 它通过【最优路径上蚂蚁数量的增加→信息素强度增加→后来蚂蚁选择概率增大→最优路径上蚂蚁数量更大增加】达到最终收敛于最优路径上L ②它是一种通用型随机优化方法, 它吸收了蚂蚁的行为特(内在搜索机制) , 它是使用人工蚂蚁仿真(也称蚂蚁系统) 来求解问题L但人工蚂蚁决不是对实际蚂蚁的一种简单模拟, 它融进了人类的智能L人工蚂蚁有一定的记忆; 人工蚂蚁不完全是瞎的; 人工蚂蚁生活的时空是离散的L ③它是一种分布式的优化方法, 不仅适合目前的串行计算机, 而且适合未来的并行计算机L ④它是一种全局优化的方法, 不仅可用于求解单目标优化问题, 而且可用于求解多目标优化问题L ⑤它是一种启发式算法, 计算复杂性为o (Nc*n2*m) , 其中Nc 是迭代次数, m 是蚂蚁数目, n 是目的节点数目L 蚁群发现最短路径的原理和机制[1] 下面用图 1解释蚁群发现最短路径的原理和机制。 如图 1(a)所示，在蚁巢和食物源之间有两条道路 Nest-A-B-D-Food 和Nest-A-C-D-Food，其长度分别为 4 和 6。单位时间内蚂蚁可移动一个单位长度的距离。开始时所有路径上都没有外激素。 如图 1(b)，在 t=0 时刻，20 只蚂蚁从蚁巢出发移动到 A。由于路径上没有外激素，它们以

智能优化算法(蚁群算法和粒子群算法)

7.1 蚁群优化算法概述 ?7.1.1 起源 ?7.1.2 应用领域 ?7.1.3 研究背景 ?7.1.4 研究现状 ?7.1.5 应用现状

7.1.1 蚁群优化算法起源 20世纪50年代中期创立了仿生学，人们从生物进化的机理中受到启发。提出了许多用以解决复杂优化问题的新方法，如进化规划、进化策略、遗传算法等，这些算法成功地解决了一些实际问题。

20世纪90年代意大利学者M．Dorigo，V．Maniezzo，A．Colorni等从生物进化的机制中受到启发，通过模拟自然界蚂蚁搜索路径的行为，提出来一种新型的模拟进化算法——蚁群算法，是群智能理论研究领域的一种主要算法。

背景：人工生命 ?“人工生命”是来研究具有某些生命基本特征的人工系统。人工生命包括两方面的内容。 ?研究如何利用计算技术研究生物现象。?研究如何利用生物技术研究计算问题。

?现在关注的是第二部分的内容，现在已经有很多源于生物现象的计算技巧。例如，人工神经网络是简化的大脑模型，遗传算法是模拟基因进化过程的。 ?现在我们讨论另一种生物系统－社会系统。更确切的是，在由简单个体组成的群落与环境以及个体之间的互动行为，也可称做“群智能”(swarm intelligence)。这些模拟系统利用局部信息从而可能产生不可预测的群体行为（如鱼群和鸟群的运动规律），主要用于计算机视觉和计算机辅助设计。

?在计算智能(computational intelligence)领域有两种基于群智能的算法。蚁群算法(ant colony optimization)和粒子群算法(particle swarm optimization)。前者是对蚂蚁群落食物采集过程的模拟，已经成功运用在很多离散优化问题上。

蚁群算法研究综述

蚁群算法综述 控制理论与控制工程09104046 吕坤一、蚁群算法的研究背景 蚂蚁是一种最古老的社会性昆虫，数以百万亿计的蚂蚁几乎占据了地球上每一片适于居住的土地，它们的个体结构和行为虽然很简单，但由这些个体所构成的蚁群却表现出高度结构化的社会组织，作为这种组织的结果表现出它们所构成的群体能完成远远超越其单只蚂蚁能力的复杂任务。就是他们这看似简单，其实有着高度协调、分工、合作的行为，打开了仿生优化领域的新局面。 从蚁群群体寻找最短路径觅食行为受到启发，根据模拟蚂蚁的觅食、任务分配和构造墓地等群体智能行为，意大利学者M.Dorigo等人1991年提出了一种模拟自然界蚁群行为的模拟进化算法——人工蚁群算法，简称蚁群算法(Ant Colony Algorithm,ACA)。 二、蚁群算法的研究发展现状 国内对蚁群算法的研究直到上世纪末才拉开序幕，目前国内学者对蚁群算法的研究主要是集中在算法的改进和应用上。吴庆洪和张纪会等通过向基本蚁群算法中引入变异机制，充分利用2-交换法简洁高效的特点，提出了具有变异特征的蚊群算法。吴斌和史忠植首先在蚊群算法的基础上提出了相遇算法，提高了蚂蚁一次周游的质量，然后将相遇算法与采用并行策略的分段算法相结合。提出一种基于蚁群算法的TSP问题分段求解算法。王颖和谢剑英通过自适应的改变算法的挥发度等系数，提出一种自适应的蚁群算法以克服陷于局部最小的缺点。覃刚力和杨家本根据人工蚂蚁所获得的解的情况，动态地调整路径上的信息素，提出了自适应调整信息素的蚁群算法。熊伟清和余舜杰等从改进蚂蚁路径的选择策略以及全局修正蚁群信息量入手，引入变异保持种群多样性，引入蚁群分工的思想，构成一种具有分工的自适应蚁群算法。张徐亮、张晋斌和庄昌文等将协同机制引入基本蚁群算法中，分别构成了一种基于协同学习机制的蚁群算法和一种基于协同学习机制的增强蚊群算法。 随着人们对蚁群算法研究的不断深入，近年来M.Dorigo等人提出了蚁群优化元启发式(Ant-Colony optimization Meta Heuristic，简称ACO-MA)这一求解复杂问题的通用框架。ACO-MH为蚁群算法的理论研究和算法设计提供了技术上的保障。在蚁群优化的收敛性方面，W.J.Gutjahr做了开创性的工作，提出了基于图的蚂蚁系统元启发式(Graph-Based Ant System Metaheuristic)这一通用的蚁群优化 的模型，该模型在一定的条件下能以任意接近l的概率收敛到最优解。T.StBtzle 和M.Dorigo对一类ACO算法的收敛性进行了证明，其结论可以直接用到两类实验上，证明是最成功的蚁群算法——MMAs和ACS。N.Meuleau和M.Dorigo研究了

蚁群算法聚类分析

蚁群算法聚类分析 摘要： 蚁群算法是今年来才提出的一种基于种群寻优的启发式搜索算法，由意大利学者M.Dorigo等于1991年首先提出。该算法受到自然界中真实蚁群集体行为的启发，利用真实蚁群通过个体间的信息传递、搜索从蚁穴到食物间的最短路径的集体寻优特征，来解决一些离散系统中优化的困难问题。本文就蚁群算法的基本原理、模型特征、聚类分析展开论述。 关键字： 蚁群算法原理模型聚类分析

引言 蚁群算法是最近几年才提出的一种新型的模拟进化算法。蚂蚁是大家司空见惯的一种昆虫，而他们的群体合作的精神令人钦佩。他们的寻食、御敌、筑巢(蚂蚁的筑窝、蜜蜂建巢)之精巧令人惊叹。蚂蚁是自然界中常见的一种生物，人们对蚂蚁的关注大都是因为“蚂蚁搬家，天要下雨”之类的民谚。然而随着近代仿生学的发展，这种似乎微不足道的小东西越来越多地受到学者们的关注。1991年M．DIorigo，V.MaIliezzo等人首先提出了蚁群算法 (Ant Colony Algorithms)，人们开始了对蚁群的研究：相对弱小，功能并不强大的个体是如何完成复杂的工作的(如寻找到食物的最佳路径并返回等)。在此基础上一种很好的优化算法逐渐发展起来。 基本蚁群算法的机制原理 模拟蚂蚁群体觅食行为的蚁群算法是作为一种新的计算智能模式引入的，该算法基于如下基本假设： (1)蚂蚁之间通过信息素和环境进行通信。每只蚂蚁仅根据其周围的局部环境做出反应，也只对其周围的局部环境产生影响； (2)蚂蚁对环境的反应由其内部模式决定。因为蚂蚁是基因生物，蚂蚁的行为实际上是其基因的适应性表现，即蚂蚁是反应型适应性主体； (3)在个体水平上，每只蚂蚁仅根据环境做出独立选择；在群体水平上，单只蚂蚁的行为是随机的，但蚁群可通过自组织过程形成高度有序的群体行为； 由上述假设和分析可见，基本蚁群算法的寻优机制包含两个基本阶段：适应阶段和协作阶段。在适应阶段，各候选解根据积累的信息不断调整自身结构，路径上经过的蚂蚁越多，信息量越大，则该路径越容易被选择；时间越长，信息量会越小；在协作阶段，候选解之间通过信息交流，以期望产生性能更好的解，类似于学习自动机的学习机制。 蚁群算法实际上是一类智能多主体系统，其自组织机制使得蚁群算法不需要对所求问题的每一方面都有详尽的认识。自组织本质上是蚁群算法机制在没有外界作用下使系统熵增加的动态过程，体现了从无序到有序的动态演化，其逻辑结构如图1所示。

基于蚁群算法的TSP问题研究

南京航空航天大学金城学院毕业设计（论文）开题报告 题目基于蚁群算法的TSP问题研究 系部XXXX系 专业XXXX 学生姓名XXXX学号XXXX 指导教师XXXX职称讲师 毕设地点XXXX 年月日

填写要求 1．开题报告只需填写“文献综述”、“研究或解决的问题和拟采用的方法”两部分内容，其他信息由系统自动生成，不需要手工填写。 2．为了与网上任务书兼容及最终打印格式一致，开题报告采用固定格式，如有不适请调整内容以适应表格大小并保持整体美观，切勿轻易改变格式。 3．任务书须用A4纸，小4号字，黑色宋体，行距1.5倍。 4．使用此开题报告模板填写完毕，可直接粘接复制相应的内容到毕业设计网络系统。

1.结合毕业设计（论文）课题任务情况，根据所查阅的文献资料，撰写1500～2000字左右的文献综述： 1.1蚁群算法的发展和应用 在计算机自动控制领域中,控制和优化始终是两个重要问题。使用计算机进行控制和优化本质上都表现为对信息的某种处理。随着问题规模的日益庞大,特性上的非线性及不确定性等使得难以建立精确的“数学模型”。人们从生命科学和仿生学中受到启发,提出了许多智能优化方法,为解决复杂优化问题(NP-hard问题)提供了新途径。 蚁群算法(Ant Colony Algorithm,ACA)是Dorigo M等人于1991年提出的。 经观察发现,蚂蚁个体之间是通过一种称之为信息素的物质进行信息传递的。在运动过程中,蚂蚁能够在它所经过的路径上留下该种信息素,而且能够感知信息素的浓度,并以此指导自己的运动方向。蚁群的集体行为表现出一种信息正反馈现象:某一路径上走过的蚂蚁越多,则后来者选择该路径的概率就越大。蚂蚁个体之间就是通过这种信息的交流达到搜索食物的目的。它充分利用了生物蚁群通过个体间简单的信息传递，搜索从蚁巢至食物间最短路径的集体寻优特征，以及该过程与旅行商问题求解之间的相似性。同时，该算法还被用于求解二次指派问题以及多维背包问题等，显示了其适用于组合优化问题求解的优越特征。 蚁群算法应用于静态组合优化问题,其典型代表有旅行商问题(TSP)、二次分配问题(QAP)、车间调度问题、车辆路径问题等。在动态优化问题中的应用主要集中在通讯网络方面。这主要是由于网络优化问题的特殊性,如分布计算,随机动态性,以及异步的网络状态更新等。例如将蚁群算法应用于QOS组播路由问题上,就得到了优于模拟退火(SA)和遗传算法(GA)的效果。蚁群优化算法最初用于解决TSP 问题，经过多年的发展，已经陆续渗透到其他领域中，如图着色问题、大规模集成电路设计、通讯网络中的路由问题以及负载平衡问题、车辆调度问题等。蚁群算法在若干领域获得成功的应用，其中最成功的是在组合优化问题中的应用。 1.2蚁群算法求解TSP问题 （1）TSP问题的描述 TSP问题的简单形象描述是:给定n个城市,有一个旅行商从某一城市出发,访问各城市一次且仅有一次后再回到原出发城市,要求找出一条最短的巡回路径。 （2）TSP问题的理论意义 该问题是作为所有组合优化问题的范例而存在的。它已经成为并将继续成为测

NS2中蚁群算法路由协议的实现_田克纯

一、引言 目前，最广泛使用的验证网络协议的正确性和测试相关性能的方法是通过虚拟环境进行模拟仿真。NS2是最流行的进行网络模拟的软件之一，是由美国加州大学的LNBL网络研究组于1989年开发的一个开放源代码的网络仿真软件［1］，已广泛被科研院所和各大高校用于网络分析、研究和教学。 蚁群算法是M．Dorigo提出的一种基于生物习性的启发式算法，用于解决复杂组合优化问题。它能在一个合理的时间内对复杂问题有一个较优的结果，在网络路由方面，该算法也体现出了很好的路由性能。虽然NS2集成了大量典型的有线和无线网络下各个层的协议，但还没有提供蚁群算法协议功能，因此以下主要论述把蚁群算法集成到NS2中，并能在Otcl脚本中使用的实现方法。 二、NS2原理［2］ NS2是一个离散事件模拟器，其核心部分是一个离散事件模拟引擎。NS2中有一个“调度器”类，负责记录当前时间，调度网络时间队列中的事件，并提供函数产生新事件，指定事件发生的时间。在一个网络模拟器中，典型的时间包括分组到达，时钟超时等，模拟时钟的推进由事件发生的时间量决定。模拟处理过程的速率不直接对应着实际时间。一个事件的处理可能又会产生后继的时间。模拟器所做的就是不停地处理一个个事件，直到所有的事件都被处理完或者某一特定事件发生为止。 NS2还有一个丰富的构件库，有了这个构件库，用户可以完成自己所要研究的系统的建模工作。NS2的构件库所支持的网络类型包括广域网、局域网、移动通信网、卫星通信网等，所支持的路由方式包括层次路由、动态路由、多播路由等。NS2还提供了跟踪和检测的对象，可以把网络系统中的状态和事件记录下来以便分析。NS2构件库的部分类层次结构如图1所示。 NS2中的网络构件一般由相互关联的两个类来实现，一个在C＋＋中，一个在Otcl中，这种方式称为分裂对象模型。构件的主要功能是在C＋＋中实现的，Otcl中的类则主要提供C＋＋对象面向用户的接口。C＋＋对象和Otcl对象之间的这种连接机制就是TclCL。这种分裂对象模型增强了可扩展性和可组合性。 NS2中蚁群算法路由协议的实现 田克纯，农秀凤，王方 （桂林电子科技大学信息与通信学院，广西桂林541004） 摘要：网络模拟是当前网络通信研究中的重要手段之一，在网络通信的建设开发过程中起着不可替代的作用。 NS2由于其扩展性强、执行效率高，已被广泛应用于各种网络的仿真。首先介绍NS2的原理，然后结合 蚁群算法介绍如何添加新协议到NS环境下并实现，最后给出新协议AntSense的仿真结果。 关键词：网络模拟；NS2；蚁群算法；新协议 中图分类号：T P319文献标识码：A文章编号：1008-3545（2010）04-0043-04 43

蚁群算法及其在序列比对中的应用研究综述

蚁群算法及其在序列比对中的应用研究综述摘要：蚁群算法是一种新颖的仿生进化算法。作为一种全局搜索的方法，蚂蚁算法具有正反馈性、并行性、分布性、自组织性等特点，自提出以来，便在求解复杂组合优化问题上显示出了强大的优势。序列比对是生物信息学的基础，通过在比对中获得大量的序列信息，可以推断基因的结构、功能和进化关系。本文首先详细阐述了蚁群算法的基本原理、各种改进技术及收敛性分析，然后对蚁群算法在双序列比对和多序列比对的应用研究进行了综述和评价，最后指出了下一步的研究方向。 关键词：蚁群算法；序列比对；信息素 Abstract: Ant colony algorithm (ACA) is a novel bionic evolutionary algorithm. As a global searching approach，ACA has some characteristic，such as positive feedback, distributing，paralleling, self-organizing, etc，and from it was introduced, it has been used to solve all kinds of complex optimization problem. Sequence alignment is the basement of Bioinformatics. With the wealth of sequence information obtained from sequence alignment, one can infers the structure, function and evolutionary relationship of genes. In this paper, the basic principles of ACA are introduced at length, and various improvements and convergence Analysis of ACA are also presented. Then the current study of double sequence alignment and multiple sequence alignment based on ant colony algorithm are reviewed and evaluated. Finally, some future research directions about ACA are proposed. Key words: Ant Colony Algorithm; Sequence Alignment; Pheromone 1 引言 蚁群算法(Ant Algorithm)是一种源于大自然中生物世界的新的仿生类算法，作为通用型随机优化方法，它吸收了昆虫王国中蚂蚁的行为特性，通过其内在的搜索机制，在一系列困难的组合优化问题求解中取得了成效。由于在模拟仿真中使用的是人工蚂蚁概念，因此有时亦被称为蚂蚁系统(Ant System)。据昆虫学家的观察和研究发现，生物世界中的蚂蚁有能力在没有任何可见提示下找出从其窝巢至食物源的最短路径，并能随环境的变化而变化，适应性地搜索新的路径，产生新的选择。作为昆虫的蚂蚁在寻找食物源时，能在其走过的路径上释放一种蚂蚁特有的分泌物——信息激素(Pheromone)，使得一定范围内的其他蚂蚁能够察觉到并由此影响它们以后的行为。当一些路径上通过的蚂蚁越来越多时，其留下的信息激素轨迹(Trail)也越来越多，以致信息素强度增大（随时间的推移会逐渐减弱），后来蚂蚁选择该路径的概率也越高，从而更增加了该路径的信息素强

蚁群聚类算法研究及应用

－5009－ 0引言 俗话说“物以类聚，人以群分”，人们在不知不觉中进行着 聚类活动，它是人们认识和探索事物之间内在联系的有效手段。聚类在数据挖掘中有着重要的地位，它既可以用作独立的数据挖掘工具，来发现数据库中数据分布的一些深入信息，也可以作为其它数据挖掘算法的预处理步骤。因此，聚类算法的研究具有很重要的现实意义。 蚁群算法不依赖于具体问题，具有全局优化能力，因此受 到了广大学者的注意。此后蚁群算法不断被改进并应用于不同领域。在聚类分析方面，Deneubourg等人受蚂蚁堆积尸体和分类它们的幼体启发，最早将蚁群算法用于聚类分析，从此开始了蚁群聚类算法的研究。 本文详细地讨论了现有的蚁群聚类算法的基本原理与性 能，在归纳总结的基础上提出需要完善的地方，以推动蚁群聚类算法的进一步研究及在更广阔的领域内得到应用。 1聚类概念及数学模型 聚类就是把一组个体按照相似性归为若干类或簇，使得 属于同一类或簇的个体之间的差别尽可能的小，而不同类或簇的个体间的差别尽可能大。聚类质量是用对象的相异度来评估，而不同类型变量的相异度的计算方法是不同的，常用的度量方法是区间标度变量中的欧几里得距离。 聚类的数学描述：设样本集={,=1,2,…,}，其中为 维模式向量，其聚类问题就是找到一个划分={ 1 , 2 ,…, }，满足= =1 ，≠，=，,=1,2,…,，≠，且使 得总的类内离散度和= =1 ,最小，其中为的 聚类中心，=1,2,…,；,为样本到其聚类中心的距 离，即,=‖‖。聚类目标函数为各样本到对应 聚类中心的距离总和，聚类中心=1 ，||为的样 本数目。 2蚁群聚类算法分类及应用 由于现实的蚁群运动过程接近于实际的聚类问题，所以 近年来涌现出大量的蚁群聚类算法。这些算法不仅思想、原理不同，而且算法的特性也根据解决问题的不同而不同，如初始参数及待聚类数据的要求、聚类形状等。

蚁群算法综述

《智能计算—蚁群算法基本综述》 班级：研1102班 专业：计算数学 姓名：刘鑫 学号： 1107010036 2012年

蚁群算法基本综述 刘鑫 （西安理工大学理学院，研1102班，西安市，710054） 摘要:蚁群算法( ACA)是一种广泛应用于优化领域的仿生进化算法。ACA发展背景着手，分析比较国内外ACA研究团队与发展情况立足于基本原理,分析其数学模型,介绍了六种经典的改进模型，对其优缺点进行分析，简要总结其应用领域并对其今后的发展、应用做出展望。 关键词:蚁群；算法；优化；改进；应用 0引言 专家发现单个蚂蚁只具有一些简单的行为能力。但整个蚁群却能完成一系列复杂的任务。这种现象是通过高度组织协调完成的1991年。意大利学者M.Dorigo 首次提出一种新型仿生算法ACA。研究了蚂蚁的行为。提出其基本原理及数学模型。并将之应用于寻求旅行商问题(TSP)的解。 通过实验及相关理论证明,ACA有着有着优化的选择机制的本质。而这种适应和协作机制使之具有良好的发现能力及其它算法所没有的优点。如较强的鲁棒性、分布式计算、易与其他方法结合等；但同时也不应忽略其不足。如搜索时间较长，若每步进行信息素更新，计算仿真时所占用CPU时间过长：若当前最优路径不是全局最优路径，但其信息素浓度过高时。靠公式对信息素浓度的调整不能缓解这种现象。会陷人局部收敛无法寻找到全局最优解：转移概率过大时，虽有较快的收敛速度，但会导致早熟收敛。所以正反馈原理所引起的自催化现象意在强化性能好的解，却容易出现停滞现象。笔者综述性地介绍了ACA对一些已有的提出自己的想法，并对其应用及发展前景提出了展望。 1 蚁群算法概述 ACA源自于蚁群的觅食行为。S.Goss的“双桥”实验说明蚂蚁总会选择距食物源较短的分支蚂蚁之间通过信息素进行信息的传递,捷径上的信息素越多,吸引的蚂蚁越多。形成正反馈机制,达到一种协调化的高组织状态该行为称集体自催化目前研究的多为大规模征兵，即仅靠化学追踪的征兵。 1 .1 蚁群算法的基本原理

人工蜂群算法在警用无人机战术需求中的应用浅析

人工蜂群算法在警用无人机战术需求中的应用浅析 摘要随着无人机在警务工作中越来越广泛的应用，以及适应新形势下警务实战化改革需求的无人机联合信息传导概念的不断发展，如何发挥无人机集群智能成为了当前警用无人机需解决的问题。立足于生物科技，将人工蜂群算法与警用无人机控制应用技术结合，探索能够有效优化无人机集群智能的应用方法。 关键词人工蜂群算法；集群智能；无人机；最优值 引言 当前国内外对无人机战术规划的研究成果比较多，但主要集中在无人机的航行移动上。虽然无人机战术功能研究近年来受到了广泛的重视，也取得了较大的进展，但相对于无人机的航行移动仍处于远远滞后的状态。航行移动和战术功能是无人机战术规划中密不可分的两个重要步骤，只有保证两者协调发展，才能对无人机执行作战任务提供全面支持，从而使无人机能够满足更多任务需求。通过对无人机集群智能问题进行层次分析，将无人机集群智能问题劃分为航行移动问题和战术功能问题分别进行分析，再进行有机结合，有效地降低原问题的复杂性。 1 从航行移动上发挥警用无人机集群智能优势 在传统的警用无人机应用中，首先要解决无人机在飞行过程中的供能问题，既无人机本身的载荷能力考量。一般小型无人机动力不足以支持长时间的作战任务需求。为此，从提高任务执行效能上考虑，要优化执行任务中的航行移动问题。针对此类问题，我们要将地形学和ABC算法相结合，通过地形学对航行移动路线的拓展，以降低航行移动路线的复杂程度，再通过ABC算法对相关任务地形进行快速的路线搜索，针对航行移动问题的实际要求，将集群智能机制引入ABC 算法的信息更新机制中，显著地提高了最优值的搜索效率。同时，分析警用无人机在实际过程中情报搜集问题的特殊性与复杂性，从最大程度满足用户需求出发，给出了需求满足最优值的战术处理路径和行动路线。利用ABC算法协同性强、搜索行为灵活等优点，在算法的基础上，利用蜂群采蜜行为的分工协同能力，引入蜂群当前循环中的生物天性，调整了多无人机现实战术计划，从而提高了搜索效率[1]。 2 从战术功能上发挥警用无人机集群智能优势 愈来愈加特殊化和复杂化的任务和战术环境，使得警务无人机在应用方面更趋向于多元化。在过去的研究中，无人机任务类型及能力制约是指对单架无人机，其机上携带的任务载荷和功能配备是有限的，所能完成的任务类型及数量受其任务载荷限制。为此，在无人机协同多任务分配问题中，由于单架无人机所能完成的任务类型和数量有限，故特定的无人机只能执行与自身能力相符合的任务，且其任务过程不能超过自身最大任务数量限制和飞行载荷限制，超出自身能力范围的任务就必须交由其他无人机执行。为此，在当前警用无人机的技术水平上，依