蚁群算法聚类分析研究

李晓霞+党巾涛

[摘 要]蚁群算法是一种基于仿生学原理的组合优化算法，应用于旅行商问题、二次分配问题、车辆调度问题及网络路由设计等问题。本文将蚁群算法的思想应用到聚类分析中，并给出了蚁群聚类算法的模型和步骤，并进行了仿真实验，得到其最优解。

[关键词]蚁群算法； 聚类分析； 蚁群聚类算法

中图分类号：U416.2 文献标识码：A 文章编号：1009-914X（2016）15-0348-01

引言

M.Dorigo在1991年提出的蚁群算法是一种基于仿生学原理的组合优化算法，它具有其他智能优化算法及群体智能算法的优点，本文详细的叙述了蚁群算法的基本思想、原理和理论，并将其应用到聚类分析中，给聚类分析的分类算法提供了更广阔的思路。

1 蚁群算法的基本原理

蚁群算法是模拟蚂蚁觅食的原理设计出的一种群集智能算法。蚂蚁在觅食过程中能够在其经过的路径上留下一种称之为信息素的物质，并在觅食过程中能够感知这种物质的强度，并指导自己行动方向，它们总是朝着该物质强度高的方向移动，因此大量蚂蚁组成的集体觅食就表现为一种对信息素的正反馈现象。某一条路径越短，路径上经过的蚂蚁越多，其信息素遗留的也就越多，信息素的浓度也就越高，蚂蚁选择这条路径的几率也就越高，由此构成的正反馈过程，从而逐渐的逼近最优路径，找到最优路径。其模拟的原理图如下图所示：

2 蚁群算法在聚类分析中的应用

（1）问题提出

一幅图像中含有多个物体，在图像中进行聚类分析需要对不同的物体分割标识，如图3所示，手写了12个待分类样品，要分成4类，如何让计算机自动将这12个物体归类？

（2）构造目标函数

已知模式样品集{X}有N个样品和M个模式分类{，j=1，2，...M}，每个样品有N个特征。以每个模式样品到聚类中心得距离之和达到最小作为目标函数，其数学模型表示为

式中，为第i个样品的第p个属性，为第j个类中心的第p个属性。

（3）实现步骤

①初始化蚁群参数，包括蚁群数目、、转换规则参数、信息蒸发参数、局部搜索阈值等。

②初始化信息素矩阵。

③所有蚂蚁根据信息素构建解集。

④计算各类中心。计算每只蚂蚁的目标函数，并对蚂蚁按目标函数值排序。

⑤在排序后的蚂蚁解集中，将前L个蚂蚁作为要交换样品的蚂蚁，取L=2，对要交换的蚂蚁实施局部搜索操作。

⑥更新信息素值。

⑦如果没有达到最大迭代次数，则转步骤③，否则输出最优类解集。

（4）效果图

参考文献

[1] 章春芳.自适应的并行蚁群算法及其应用[D].扬州大学，2006.

[2] 胡建军，唐常杰等基于最近邻优先的高效聚类算法[J].四川大学学报（工程科学版），2004，36（6）.

[3] 刘波.一种利用信息嫡的群体智能聚类算法[J].计算机工程与应用，2004，30（35）180-182.

作者简介

李晓霞，女，山西省大同市人，硕士研究生学历，信息与通信工程专业。

党巾涛，男，山西省运城市人，硕士研究生学历，信息与通信工程专业。