-
蚁群算法聚类分析
摘要：
蚁群算法是今年来才提出的一
种基于种群寻优的启发式搜索算法，由意大利学者
等于
1991
年首先提出。该算法受到自然界中真实蚁群集体行为的启发，利
用真实
蚁群通过个体间的信息传递、
搜索从蚁穴到食物间的最短
路径的集体寻优特征，
来解决一些
离散系统中优化的困难问题。
本文就蚁群算法的基本原理、模型特征、聚类分析展开论述。
关键字：
蚁群算法
原理
模型
聚类分析
引言
蚁群算法是最近几年才提出的一
种新型的模拟进化算法。
蚂蚁是大家司空见惯的一种昆
虫，而他
们的群体合作的精神令人钦佩。他们的寻食、御敌、筑巢
(
蚂蚁
的筑窝、蜜蜂建巢
)
之精巧令人惊叹。
蚂蚁是自然界中常见的一种生物，
人们对蚂蚁的关注大都是因为
“蚂蚁搬
家，天要下雨”
之类的民谚。然而随着近代仿生学的发
展，这种似乎微不足道的小东西越来
越多地受到学者们的关注。
1991
年
M
．
DIorigo
，
zzo
等人首先提
出了蚁群算法
(Ant
Colony
Algorithms)
，人们开始了对蚁群的研究：相对弱小，功能并不强大的个
体是如何完
成复杂的工作的
(
如寻找到
食物的最佳路径并返回等
)
。
在此基础
上一种很好的优化算法逐渐
发展起来。
基本蚁群算法的机制原理
模拟蚂蚁群
体觅食行为的蚁群算法是作为一种新的计算智能模式引入的，
该算法基于如
下基本假设：
(1)
蚂蚁
之间通过信息素和环境进行通信。
每只蚂蚁仅根据其周围的局部环境做出反应，
也只对其周围的局部环境产生影响；
(2)<
/p>
蚂蚁对环境的反应由其内部模式决定。因为蚂蚁是基因生物，蚂蚁的行为实际上是
其基因的适应性表现，即蚂蚁是反应型适应性主体；
< br>(3)
在个体水平上，每只蚂蚁仅根据环境做出独立选择；在群体水平上，单只蚂
蚁的行
为是随机的，但蚁群可通过自组织过程形成高度有序的群体行为；
由上述假设和分析可见，
基本蚁群算法的寻优机制包
含两个基本阶段：
适应阶段和协作
阶段。在适应阶段，各候选解
根据积累的信息不断调整自身结构，路径上经过的蚂蚁越多，
信息量越大，则该路径越容
易被选择；时间越长，信息量会越小；在协作阶段，候选解之间
通过信息交流，以期望产
生性能更好的解，类似于学习自动机的学习机制。
蚁群算法实
际上是一类智能多主体系统，
其自组织机制使得蚁群算法不需要对所求问题
的每一方面都有详尽的认识。
自组织本质上是蚁群算法机制在没有外界作用下
使系统熵增加
的动态过程，体现了从无序到有序的动态演化，其逻辑结构如图
1
所示。
图
1
基本蚁群算法的逻辑结构
由图
1
可见，先将具体的组合优化问题表述成规
范的格式，然后利用蚂蚁算法在“探索
(exploration)
’
’和
“利用
(exploita
tion)
之间根据信息素这一反馈载体确定决策点，
同
时按照相应的信息素更新规则对每只蚂蚁个体的信息素进行增量构建，
随后从整体角度规划
出蚂蚁活动的行为方向，周而复始，即可求出组合优化问题的最优解
。
基本蚁群算法的模型特征
现在大量的工作是围绕组合优化问题进行的，
因为蚁群模型的定义要受
到问题结构的影
响，
故而选择一种标准的问题是衡量算法好坏，
并与其它算法进行比较的前提，
通常选择的
问题是旅行商问题
(TSP)
，
T
sP
具有广泛的代表意义和应用前景，
许多现实问题均可抽象为
TSP
的求解，故我们以
TSP
为例来描述基本蚁群算法的模型特征。
TS
P
问题属于一种典型的组合优化问题，
其定义为：
给定
n
个城市的集合，
寻找
一条只经
过各城市一次的具有最短长度的闭合路径。
设
(X
i
，
Y
j
)
是城市
i
的坐标值，
d
ij
为城市
i
和城市
j
之
间的距离，用欧几里德空间距离表示：
(1)
一个
TSP
问题可由图
(N
，
E)
给定，其中
N
是城市的集合，
E
是城市之间的
支路集合
(
欧
几里德空间中
TSP
意义下的一个全连接图
)
< br>，令
b
i
(t)(i=1
，
2
，
?
，
n)
为
t
时刻位于城市
i
的蚂蚁个数，则
为蚁群中蚂蚁的总个数。每个蚂蚁可认为具有下列特征的简
单智能体：
(1)
其选择城市的概率是城市之间的距离和连接
支路所包含的当前信息素余量的函数；
(2)
为了强制蚂蚁进行合法的周游，直到周游完一次所有的城市，才允许蚂蚁游走己访
问过的城市，设置禁忌表来进行控制；
(3)
当完成一次周游后，它在每条访问过的支路上都会留下信息素。
设：
u(t)
为
t
时刻在
ij
连线上残留的信息量，而初始时刻
各条路径上的信息量相等，即
T
ii
(
O)=c
。如果在时间间隔
(t
，
t+1)
中
m
个蚂
蚁都从当前城市选择下一个城市，则经过
n
个时
间间隔。
为了避免残留信息过多引起的残留信息淹没启发信息的问题，
在每一只蚂蚁完成对
所有
n
个城市的访问后
(
也即一个循环结束后
)
，必须对残留信息进行更新处理，模仿人类记
忆的特点，
对
1
日的信息进行削弱。同时，必须将最新的蚂蚁访问路径的信
息加入
T ij
，此
时按如下方法修改
各条路径上的残留信息。
(2)
(3)
上式中，
p
< br>为信息残留系数，
l
—
p
表征了从时刻
t
到
t
+n
路径
(I,j)
上残留信息
的挥发程度。△
T
ij
为本次循环第
k
只蚂蚁在
t
与
t+n
时刻，留在路径
(i,j)
上的
年位长度上的信息量。
根据
Morigo
的
Ant
—
Cycle
System
模型，有
(4)
上式中，
Q
为常量，
L
k
为第
k
只蚂蚁在本次循环中所走路径的长度。则
t
时刻蚂
蚁
k(k=l
，
2
，
3
，
?
，
n)
由城市
i
到城市
j
的选择概率定义如下：
< br>
（
5
）
定义
tabuk
为一动态增长的列表，其中
记录了蚂蚁
k
所经过的所有的城市号，
第
k
只蚂蚁访问的城市列表，则
城市<
/p>
j
的某种启发信息。
Ant cycle
算法流程如图
2<
/p>
所示：
为允许
为
t
时刻蚂蚁由城市
i
选择
图
2 Ant-
cycle
算法流程图
而后
Dorigo
等人又提出了蚁群算法的另外两
个版本：蚁密算法和蚁量算法，这两种算
法在信息素更新的方式上利用的是局部信息，<
/p>
而蚁周算法利用的是整体信息。
这两种算法的
模型中，每只蚂蚁在每一步后都留下了它的信息素，而不必等到周游结束。在蚁密算法中，
< br>蚂蚁每次从
i
到
j
都会在支路
(ij)
上留下数量为
< br>Q
的信息素：在蚁量算法中，一只从
i
< br>到
j
的蚂蚁在支路
(i
，
j)
上留下数量为
Q
/d
ij
的信息素。其更新方式定义如下：
(6)
(7)
基本蚁群算法的优点和不足之处
蚁群
算法的基本思想是模仿蚂蚁依赖信息量
(pheromone)
进行通信而显示出的社会性行
为，在智能体
(agent)
定义的基础上，由一个贪心法指导下的自催化
(auto cata
lytic)
过程
引导每个智能体的行动，
它是一种随机的通用试探法。
AS
的信息正反馈机制能迅速
找到好的
解决方法；
分布式计算可以避免过早地收敛；
强启发能在早期的寻优中迅速找到合适的解决
方案，该算法已经被成功地
运用于许多能被表达为在图表上寻找最佳路径的问题。
不难看出，蚁群算法的优点在于：
(
1)
较强的鲁棒性：对蚁群算法模型稍加修改，就可以应用于其他问题；
(2)
分布式计算：蚁群算法是一种基于种群的进化
算法，具有本质并行性，易于并行实
现；
(3)
易于与其他方法结合：
蚁群算法很容易与多种启发式
算法结合，
以改善算法的性能。
但是蚁群算法也存在着若干不足之处，如：
< br>(1)
需要较长的搜索时间，蚁群算法的复杂度可以反映这一点。虽然计算机计算
速度的
提高和蚁群算法的本质并行性在一定程度上可以缓解这一问题，但是对于大规模优
化问题，
这还是一个很大的障碍；
(
2)
该算法容易出现停滞现象
(stagnation
behaVior)
，即搜索进行到一定程度后，所有
个体所发现的解完全一致，不能对解空间进一步搜索，不利于发现更好的解；
(3)
蚁群算法是一种基于蚁群群体行为的算法，群体各个个体
需要通过交换信息素实现
相互通讯，
并通过信息素的差异分布构
造问题的解。
算法求解问题过程中需要问题空间中存
在信息素的
差异，
而这一差异的出现常常需要耗费算法一部分的时间，
在某
些情况下会很大
程度地降低算法的运行效率；
(4)
在算法实现方面存在许多不确定的因素，比如，信息素初始数值的确定，
不同的蚁
群算法设置为不同的数值，
而且具有很大的差异；
在信息素的更新方面，
同样具有差异很大
的
很多不同的方式；
另外，
算法还有许多参数的取值要在算法中确
定，
这些参数在不同取值
的情况下，常常会对算法的性能和求解
效率产生重大影响；
(5)
在蚁群依
据信息素确定行走路径的过程中，
可能会出现蚁群陷入局部最优解的情况，
造成了算法求解的偏差。
聚类数目已知的蚁群聚类算法
聚类分
析师一种传统的多变量统计分类方法，
用以探讨如何将所搜集的物体分类，
似的
相同群体具有高度的相异性。
聚类分析的用途甚
广，
在科学数据探测、
图像处理、
模式
识别、
文档检索、医疗诊断、
web
分
析、计算物学等领域起着非常重要的作用。
聚类问题的本质是
一个非线性规划问题，
目前没有有效的算法解决这些问题。
蚁群
算法
作为一种分布式寻优算法，
已经展示了其优良的搜索最优解
的能力，
并具有其他通用型算法
不具备的特征。
由于蚁群算法能够应用于各种优化组合问题，
因此可以用来解决聚类分析问
题。
基于蚁群算法的聚类算法大致分为聚类数目已知和聚类数目未知
两类问题，
本文将着重
介绍聚类数目已知的聚类算法。
1.
问题提出
一幅图中含有多个物体，在图像中进行聚类分析需要对不同的物体分割表示，如图
3
所
示，手写了
12
个待分类样品，要分成
4
类，如何让计算机
自动将这
12
个物体归类呢？本文将
用
蚁群算法解决聚类问题的实现方法。
图
3
待聚类的样品数字
2.
蚂蚁的结构
在已知聚类数据的蚁群聚类算法中，
每只蚂蚁都表示为一种可能的聚类结果。
首先生成
具有
m
只蚂
蚁的蚁群，每只蚂蚁在搜索开始之前分配一个空的长度为样本个数
N
的解集
S
，解
集中的第
i
个位置对应地
i
个样品
所属的类号。在搜索结束后，解集中的值表示的是第
i
个样
品所归属的类。
针对图
< br>3
，分为
4
类的
12
个样品，设计蚂蚁的解集，假设蚂蚁
S
i
进行搜索后找到的解集，
如表
< br>1
所示。
表
1
某只蚂蚁的解集
< br>某已知蚂蚁
S
i
中的值表示的是第
1
个样品分到第
< br>2
类，第
2
个样品分到第
4
类，等等，这
是蚂蚁利用信息素把每个样品
分到相应的类中后的解集。
3.
构造信息素矩阵
在
12
样品分到
4
个类规模的聚类问题中，信息素是一个在迭代过程中不断更新的
12*4<
/p>
的
矩阵。在出事阶段，信息素值被初始化为同一个数值，例如表<
/p>
2
所示。
-
-
-
-
-
-
-
-
-
上一篇：各种动物群体的英文表达
下一篇：3分钟内儿童故事6个(1个纯英语故事)