摘要自意大利学者M. Dorigo于1991年提出蚁群算法后，该算法引起了学者们的极大关注，在短短十多年的时间里，已在组合优化、网络路由、函数优化、数据挖掘、机器人路径规划等领域获得了广泛应用，并取得了较好的效果。
本文首先讨论了该算法的基本原理，接着介绍了旅行商问题，然后对蚁群算法及其二种改进算法进行了分析，并通过计算机仿真来说明蚁群算法基本原理，然后分析了聚类算法原理和蚁群聚类算法的数学模型，通过调整传统的蚁群算法构建了求解聚类问题的蚁群聚类算法。
最后，本文还研究了一种依赖信息素解决聚类问题的蚁群聚类算法，并把此蚁群聚类算法应用到对人工数据进行分类，还利用该算法对2005年中国24所高校综合实力进行分类，得到的分类结果与实际情况相符，说明了蚁群算法在聚类分析中能够收到较为理想的结果。
【关键词】蚁群算法；计算机仿真；聚类；蚁群聚类Study on Ant Colony Algorithm and its Application inClusteringAbstract：As the ant colony algorithm was proposed by M. Dorigo in 1991,it bringed a extremely large attention of scholars, in past short more than ten years, optimized, the network route, the function in the combination optimizes, domains and so on data mining, robot way plan has obtained the widespread application, and has obtained the good effect.This acticle discussed the basic principle of it at first, then introduced the TSP,this acticle also analysed the ant colony algorithm and its improved algorithm, and explanated it by the computer simulates, then it analysed the clustering algorithm and the ant clustering algorithm, builded the ant clustering algorith to solution the clustering by the traditioned ant algorithm. At last, this article also proposed the ant clustering algorith to soluted the clustering dependent on pheromon. Carry on the classification to the artificial data using this ant clustering algorithm; Use this algorithm to carry on the classification of the synthesize strength of the 2005 Chinese 24 universities; we can obtain the classified result which matches to the actual situation case. In the next work, we also should do the different cluster algorithm respective good and bad points as well as the classified performance aspect the comparison research; distinguish the different performance of different algorithm in the analysis when the dates are different.Key words：Ant colony algorithm; Computer simulation; clustering; Ant clustering目录1 引言 (3)1.1群智能 (2)1.2蚁群算法 (3)1.3聚类问题 (4)1.4本文研究工作 (5)2 蚁群算法原理及算法描述 (5)2.1蚁群算法原理 (5)2.2蚁群优化的原理分析 (8)2.3算法基本流程 (10)2.4蚁群觅食过程计算机动态模拟 (11)2.5人工蚂蚁与真实蚂蚁的对比 (13)2.6本章小结 (14)3 基本蚁群优化算法及其改进 (15)3.1旅行商问题 (15)3.2基本蚁群算法及其典型改进 (15)3.2.1 蚂蚁系统 (15)3.2.2 蚁群系统 (16)3.2.3 最大-最小蚂蚁系统 (16)3.3基本蚁群算法仿真实验 (16)3.3.1 软硬件环境 (16)3.3.2 重要参数设置 (16)3.3.3仿真试验 (17)3.4本章小结 (19)4 蚁群聚类算法及其应用 (20)4.1聚类问题 (20)4.2蚁群聚类算法的数学模型 (21)4.3蚁群聚类算法 (21)4.3.1 蚁群聚类算法分析 (22)4.3.2 蚁群聚类算法流程 (25)4.4蚁群聚类算法在高校分类中的应用 (25)4.5本章小结 (27)5 结论与展望 (28)参考文献 (29)致谢 (31)附录 (32)1 引言下面将介绍群智能以及蚁群算法和聚类问题。
1.1 群智能成群的鸟、鱼、浮游生物、蚂蚁、蜜蜂等都是以集群形式进行筑巢、觅食、迁徙和逃避捕食者等复杂行为，而这些行为是单个个体不可能有足够的能力来指挥完成的。
数以千计的个体如何组成一个群落，又如何相互协调、分工、合作来完成复杂任务的呢？通过生物学家对微生物、群居昆虫、群居动物的调查得出结论，各种社会型生物的各种集体行为似乎都可以找到几个共同的属性[1]：(1)控制充分的分布在许多个体之中；(2)个体之间的交流为局部交流；(3)群体的行为要明显优于个体的行为；(4)群体对外界的变化的反应具有鲁棒性和适应性。
受社会性昆虫行为的启发，计算机工作者通过对它们的模拟产生了一系列对于传统问题的新的解决方法，这些研究就是群集智能的研究。
群集智能(Swarm Intelligence)中的群体(Swarm)指的是“一组相互之间可以进行直接通信或者间接通信(通过改变局部环境)的主体，这组主体能够合作进行分布问题求解”。
而所谓群集智能指的是“无智能的主体通过合作表现出智能行为的特性”。
群集智能在没有集中控制并且不提供全局模型的前提下，为寻找复杂的分布式问题的解决方案提供了基础。
概括地说，使得社会型生物的个体相互协作而实现神奇的群体行为的答案是个体进行相互合作时体现的自组织行为[2]。
自组织是一些动态环境条件的连续变化。
Krieger 等用这种蚂蚁的阈值模型为一群在活动场地聚集目标物体的机器人定义了一个劳力分配的分布式系统[3,4]。
在他们的实验中，由基于阈值行为活动控制的机器人能够完成聚集任务，同时这个系统作为一个整体显示了固有的容错性和功能衰减。
一个或多个人行为的自适应，导致整体功能仅仅略微的降低。
最重要的是，在系统设计时在机器人之间并没有外在的交流机制，同时在机器人的控制程序里没有明确包含在错误的环境里的应对措施。
尽管这个实验是在大学的实验室条件下完成的，但它足以显示这种方法对于在开放的环境下控制工业机器人的变换是有很大的潜力的。
由此可见，群智能有着以下几个方面的特点[1,3]：(1)由于系统中单个个体的能力比较简单，这样每个个体的执行时间比较短，实现起来比较方便，具有简单性；(2)单个个体具有改变环境的能力和系统自调节性；(3)无中心控制和数据源。
这样的系统更具有鲁棒性，不会由于某一个或者某几个个体的故障而影响整个问题的求解；(4)群体中相互合作的个体是分布的。
这个特点与计算机网络的工作环境非常相似；(5)各个体通过对环境的感知进行合作，个体的增加或减少都不会加大系统通信的开销。
这样，系统具有更好的可扩展性，同时也具有更好的安全性。
根据其特点，群智能能够被用于解决大多数优化问题或者能够转化用领域已扩展到各种工程优化问题，如电信路由选择、TSP 问题、车间调度问题、二次分配问题等等，并取得了意想不到的收获。
虽说群智能的研究还处于初级阶段，并且存在着许多困难，但是可以预言群智能的研究代表了以后计算机研究发展的一个重要方向。
本文所讨论的蚁群算法就是一种群智能算法[2]。
1.2 蚁群算法蚁群觅食过程是一种典型的群智能行为过程[5]，蚁群寻找食物时会派出一些蚂蚁分头在四周游荡，如果一只蚂蚁找到食物，它就返回巢中通知同伴并沿途留下“信息素”(pheromone)作为蚁群前往食物所在地的标记。
信息素会逐渐挥发，如果两只蚂蚁同时找到同一食物，又采取不同路线回到巢中，那么比较绕远的一条路上信息素的气味会比较淡，蚁群将倾向于沿另一条更近的路线前往食物所在地。
受到蚂蚁觅食时的通信机制的启发，90年代Dorigo提出了蚁群算法(ant colony algorithm,ACA)来解决计算机算法学中经典的“旅行商问题”--如果有n 个城市，需要对所有n个城市进行访问且只访问一次的最短距离。
在解决旅行商问题时，蚁群算法设计虚拟的“蚂蚁”将摸索不同路线，并留下会随时间逐渐消失的虚拟“信息素”。
虚拟“信息素”也会挥发，每只蚂蚁每次随机选择要走的路径，他们倾向于选择路径比较短的、信息素比较浓的路径。
根据“信息素较浓的路线更近”的原则，即可以选择出最佳路线。
由于这个算法利用了正反馈机制，使得较短的路线能够有较大的机会得到选择并且采用了概率算法，所以它能够不局限于局部最优解。
蚁群算法对于解决旅行商问题并不是目前最好的方法，但首先它提出了一种解决旅行商问题的新思路；其次由于这种算法特有的解决方法，它已经成功的被应用于解决组合优化问题。
作为通用型随机优化算法，蚁群算法自问世以来表现了强大的生命力，较之以往的启发式算法不论在搜索效率上，还是在算法的时间复杂度方面都取得了令人满意的效果，现在已经陆续应用到组合优化、人工智能、通讯数据挖掘、机器人路径规划等多个领域。
另外蚁群算法的正反馈性和协同性使其可用于分布式系统，隐含的并行性更使之具有较强的发展潜力。