Ｎｏ．３ Ｊｕ．．，２００７ 微处理机 ＭＩＣＲＯＰＲＯＣＥＳＳＯＲＳ 第３期 ２００７年６月
基于分区策略的蚂蚁算法拳
于红斌 ，李孝安
（１．河南师范大学计算机与信息技术学院，新乡４５３００７；２．西北工业大学计算机学院，西安７１００７２）
摘要：蚂蚁算法是一种解决组合优化问题的有效算法，该算法具有许多优良的性质，但是也 存在一些缺点，如计算时间较长等。该文在基本蚂蚁算法的基础上，提出分区策略和信息素直接优 化策略。分区策略加快了蚂蚁算法初期信息素的获得速度，信息素直接优化方法加速了蚂蚁算法
后期收敛的速度。实验表明，这种改进有效提高了蚂蚁算法的搜索效率。
关键词：蚂蚁算法；分区策略；信息素
中图分类号：ＴＰ３０１ 文献标识码：Ａ 文章编号：１００２—２２７９（２００７）０３—００７８—０３
Ａｎｔ Ａｌｇｏｒｉｔｈｍ Ｂａｓｅｄ ｏｎ Ｓｅｐａｒａｔｉｎｇ Ａｒｅａｓ Ｓｔｒａｔｅｇｙ
ＹＵ Ｈｏｎｇ—Ｂｉｎ 。ＬＩ Ｘｉａｏ—Ａｎ （１．Ｓｃｈｏｏｌ ｏｆＣｏｍｐｕｔｅｒ ａｎｄ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｅｃｈｎｏｌｏｇｙ，ｔｔｅｎａｎ Ｎｏｒｍａｌ Ｕｎｉｖｅｒｓｉｔｙ，Ｘｉｎｘｉａｎｇ ４５３００７，Ｃｈｉｎａ； ２．Ｓｃｈｏｏｌ ｏｆＣｏｍｐｕｔｅｒ，Ｎｏｒｔｈｗｅｓｔｅｒｎ Ｐｏｌｙｔｅｃｈｎｉｃａｌ Ｕｎｉｖｅｒｓｉｔｙ，Ｘｉ’ｏ，ｎ ７１００７２，Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ：Ａｎｔ ａｌｇｏｒｉｔｈｍ（ＡＡ）ｉｓ ａｌｌ ｅｆｆｅｃｔｉｖｅ ａｌｇｏｒｉｔｈｍ ｔｏ ｓｏｌｖｅ ｃｏｍｂｉｎａｔｏｒｉａｌ ｐｒｏｂｌｅｍｓ ｗｈｉｃｈ ｓｈｏｗｓ ｍａｎｙ ｐｒｏｍｉｓｉｎｇ ｃｈａｒａｃｔｅｒｓ，ｂｕｔ ｉｔ ａｌｓｏ ｈａｓ ｓｏｍｅ ｓｈｏｒｔｃｏｍｉｎｇｓ ｓｕｃｈ ａｓ ｎｅｅｄｉｎｇ ｍｏｒｅ ｃｏｍｐｕｔｉｎｇ ｔｉｍｅ． Ｂａｓｅｄ ｏｎ ＡＡ，ｔｗｏ ｎｏｖｅｌ ｓｔｒａｔｅｇｉｅｓ ａｒｅ ｄｅｓｉｇｎｅｄ ｔｏ ｉｍｐｒｏｖｅ ｔｈｅ ｐｅｒｆｏｒｍａｎｃｅ．Ｏｎｅ ｉｓ ｓｅｐａｒａｔｉｎｇ ｔｈｅ ｃｉｔｉｅｓ ｉｎｔｏ ｓｅｖｅｒａｌ ａｒｅａｓ ｉｎ ｏｒｄｅｒ ｔｏ ｏｂｔａｉｎ ｔｈｅ ｉｎｉｔｉａｌ ｐｈｅｒｏｍｏｎｅ ｍｏｒｅ ｑｕｉｃｋｌｙ．Ｔｈｅ ｏｔｈｅｒ ｑｕｉｃｋｅｎｓ ｔｈｅ ｃｏｎｖｅｒ－
…………………………………………………………‘ 实用第一 智慧密集 。 ……………… … …… … … … …
。。ｌ鼍尊笺｜胃｜ｌ 。鼍 嚣簧｜譬 尊｜１ ０ ｜毫｜螽甏ｌ 誊麓每 一一 ｉ臻甏、｛鬣 萋鍪鼍《ｉ｜ ｜。。§｜ ｜罄｜ｌ麓鬟｜鼍尊ｌ毫■。 ｜鼍 鼍 ｌｌ 蚂蛱赣 赣 ； 砖 磅 ｜＿｜ｌ｜｜ ０≯ ｊ＿ ｊ。ｌ ｜
摘 要 介绍了蚂蚁算法的概念并用Ｊａｖａ语言实现，从而使人们认识到这一算法的科学 性、实用性。 关键词Ｊａｖａ，蚂蚁算法
一、描述 蚂蚁算法（Ａｎｔ Ｃｏｌｏｎｙ Ｏｐｔｉｍｉｚａｔｉｏｎ，ＡＣＯ），又称蚁群算法， 是一种用来在图中寻找优化路径的机率型技术。它由Ｍａｒｃｏ Ｄｏｒｉｇｏ于１９９２年在他的博士论文中引入，其灵感来源于蚂蚁 在寻找食物过程中发现路径的行为。 昆虫世界中，蚂蚁的组成是一种群居的世袭大家庭，我们 称之为蚁群。蚂蚁分为世袭制的蚁王（后）和工蚁两种，它们 具有高度组织的社会性，彼此沟通不仅可以借助触觉和视觉的 联系，在大规模的协调行动中还可以借助外激素（有些书称信 息素）之类的信息介质。蚂蚁平时在巢穴附近作无规则行走， 一旦发现食物并不立即进食而是将之搬回蚁穴与其他蚂蚁分 享，在食物小时则独自搬回蚁穴，否则就回蚁穴搬兵，一路上 会留下外激素，食物越大外激素的浓度就越大，越能吸引其他 的蚂蚁过去一起搬去食物，这样最终就能将食物全部搬回蚁 穴。 设想，如果我们要为蚂蚁设计一个人工智能的程序，那么 这个程序要多么复杂呢？首先，要让蚂蚁能够避开障碍物，就 必须根据适当的地形给它编进指令让他们能够巧妙地避开障碍 物，其次，要让蚂蚁找到食物，就需要让他们遍历空间上的所 有点；再次，如果要让蚂蚁找到最短的路径，那么需要计算所 有可能的路径并且比较它们的大小，而且更重要的是程序的错 误也许会让你前功尽弃。 然而，事实并没有想得那么复杂，每个蚂蚁只做了非常简 单的工作：检查某个范围内有无食物，并逐渐向外激素浓的方 向运动。每只蚂蚁只关心很小范围内的眼前信息，而且根据这 些局部信息利用几条简单的规则进行决策，这样，在蚁群这个 集体里，复杂性的行为就会凸现出来。 １．范围规则 蚂蚁观察到的范围是一个方格世界，蚂蚁有一个参数为速 度半径（一般是３），那么它能观察到的范围就是３ ３个方 格世界，并且能移动的距离也在这个范围之内。 ２．环境规则 蚂蚁所在的环境是一个虚拟的世界，其中有障碍物，有 别的蚂蚁，还有信息素。信息素有两种，一种是找到食物的蚂 蚁洒下的食物信息素，一种是找到窝的蚂蚁洒下的窝的信息 素。每个蚂蚁都仅仅能感知它范围内的环境信息。环境以一定 的速率让信息素消失。 ３．觅食规则 在每只蚂蚁能感知的范围内寻找是否有食物，如果有就直 接过去。否则看是否有信息素，并且比较在能感知的范围内哪 一点的信息素最多，这样，它就朝信息素多的地方走，并且每 只蚂蚁多会以小概率犯错误，从而并不是往信息素最多的点移 动。蚂蚁找窝的规则和上面一样，只不过它对窝的信息素做出 反应，而对食物信息素没反应。 ４．移动规则 每只蚂蚁都朝向信息素最多的方向移动。当周围没有信息 素指引的时候，蚂蚁会按照自己原来运动的方向惯性地运动下 去，且在运动的方向有一个随机的小的扰动。为了防止蚂蚁原 地转圈，它会记住最近刚走过了哪些点，如果发现要走的下一 点已经在最近走过了，它就会尽量避开。 ５．避障规则 如果蚂蚁要移动的方向有障碍物挡住，它会随机地选择另 一个方向，并且有信息素指引的话，它会按照觅食的规则行 为。 ６．播撒信息素规则 每只蚂蚁在刚找到食物或者窝的时候撒发的信息素最多， 并随着它走远的距离，播撒的信息素越来越少。 根据这几条规则，蚂蚁之间并没有直接的关系，但是每只 蚂蚁都和环境发生交互，而通过信息素这个纽带，实际上把各 个蚂蚁之间关联起来了。比如，当一只蚂蚁找到了食物，它并 没有直接告诉其他蚂蚁这儿有食物，而是向环境播撒信息素， 当其他的蚂蚁经过它附近的时候，就会感觉到信息素的存在， 进而根据信息素的指引找到了食物。
第３６卷第３期 、，ｏ１．３６ Ｎｏ．３ 河北工业大学学报 ＪＯＵＲＮＡＬ ＯＦ ＨＥＢＥＩ ＵＮＩＶＥＲＳＩＴＹ ＯＦ ＴＥＣＨＮＯＬＯＧＹ ２００７年６月 Ｊｕｎｅ ２００７
文章编号：１００７－２３７３（２００７）０３－００４８－０５
结合蚂蚁算法的Ｋ－Ｍｅａｎｓ聚类分析
杨昕，彭玉青
（河北工业大学计算机与信息学院，天津３００１３０）
摘要蚂蚁算法是一种新的基于种群的模拟进化算法 Ｋ－Ｍｅａｎｓ、基于密度的聚类是常见的基于分割的聚类方法， 本文将蚂蚁算法、Ｋ－Ｍｅａｎｓ算法、密度思想结合在一起，提出了一种基于密度一蚂蚁思想的Ｋ－Ｍｅａｎｓ算法，它利 用蚂蚁算法的随机性，很大程度上解决局部最优问题，而且克服了Ｋ．Ｍｅａｎｓ算法初始参数的敏感性，提高了聚 类的质量．再结合密度思想，使蚂蚁有选择地遍历，提高了算法效率，并克服了基于密度的算法不能发现任意形 状聚类的问题． 关键词 聚类分析；蚂蚁算法；Ｋ－Ｍｅａｎｓ；密度；数据 中图分类号ＴＰ３９１．４１ 文献标识码Ａ
Ｔｈｅ Ｋ．Ｍｅａｎｓ Ｃｌｕｓｔｅｒｉｎｇ Ａｎａｌｙｓｉｓ Ｃｏｍｂｉｎｅｄ ｗｉｔｈ Ａｎｔ Ｃｏｌｏｎｙ
ＹＡＮＧ Ｘｉｎ，ＰＥＮＧ Ｙｕ—ｑｉｎｇ
（Ｓｃｈｏｏｌ ｏｆＣｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ａｎｄ Ｅｎｇｉｎｅｅｒ，Ｈｅｂｅｉ Ｕｎｉｖｅ￣ｉｔｙ ｏｆＴｅｃｈｎｏｌｏｇｙ，Ｔｉａｎｊｉｎ ３００１３０，Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ Ｔｈｅ ａｎｔ ａｌｇｏｒｉｔｈｍ ｉｓ ａ ｎｅｗ ｅｖｏｌｕｔｉｏｎａｌ ｍｅｔｈｏｄ，ｋ：ｍｅａｎｓ ａｎｄ ｔｈｅ ｄｅｎｓｉｔｙ－ｃｌｕｓｔｅｒ ａｒｅ ｆａｍｉｌｉａｒ ｃｌｕｓｔｅｒ ａｎａｌｙｓｉｓ、 Ｉｎ ｔｈｉｓ ｐａｐｅ￣ ｗｅ ｐｒｏｐｏｓｅｄ ａ ｎｅｗ Ｋ－Ｍｅａｎｓ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ Ｏｎ ｄｅｎｓｉｔｙ ａｎｄ ａｎｔ ｔｈｅｏｒｙ，ｗｈｉｃｈ ｒｅｓｏｌｖｅｄ ｔｈｅ ｐｒｏｂｌｅｍ ｏｆ ｌｏｃａｌ ｍｉｎｉｍａｌ ｂｙ ｔｈｅ ｒａｎｄｏｍ ｃｉｔｙ ｏｆ ａｎｔｓ ａｎｄ ｈｕｒｄｌｅｄ ｔｈｅ ｏｒｉｇｉｎａｌ ｐａｒａｍｅｔｅｒ ｓｅｎｓｉｔｉｖｉｔｙ ｏｆ ｋ－ｍｅａｎｓ．Ｉｔ ｃｏｍｂｉｎｅｄ ｔｈｏｕｇｈｔ ｏｆｄｅｎｓｉｔｙ ａｎｄ ｍａｄｅ ｔｈｅ ａｎｔｓ ｓｅａｒｃｈｉｎｇ ｓｅｌｅｃｔ．Ｉｔ ｉｍｐｒｏｖｅｄ ｔｈｅ ｅｆｆｉｃｉｅｎｃｙ ａｎｄ ｏｖｅｒｃａｍｅ ｔｈｅ ｐｒｏｂｌｅｍ ｏｆｎｏｔ ｆｅｎｄｉｎｇ ｃｌｕｓｔｅｒｉｎｇ ｃｅｎｔｅｒ ｏｆ ａｒｂｉｔｒａｒｉｎｅｓｓ ｓｈａｐｅ． Ｋｅｙ ｗｏｒｄｓ ｃｌｕｓｔｅｒ ａｎａｌｙｓｉｓ；ａｎｔ ａｌｇｏｒｉｔｈｍ；Ｋ－Ｍｅａｎｓ；ｄｅｎｓｉｔｙ；ｄａｔａ
蚂蚁算法求解TSP问题
指导教师：李正学
系 别：应用数学系
班 级：2003级06班
姓 名：王源
学 号：200312082
蚂蚁算法求解TSP问题
摘 要 蚂蚁算法是通过蚂蚁觅食而发展出的一种新的启发算法，该算法已经成功的解决了
诸如TSP问题。本文简要学习探讨了蚂蚁算法和TSP问题的基本内容，尝试解决一个实例
问题并给出C语言算法。
关键词 蚂蚁算法；TSP问题。
1 蚂蚁算法与TSP问题
1.1 蚂蚁算法
蚂蚁算法(Ant Colony Algorithm) 是由意大利学者M.Dorigo ,V. Manierio ,A.
Collorni等人于二十世纪九十年代提出的一种新型的模拟进化算法。受到人们对
自然界中真实蚁群集体行为研究成果的启发,考虑到蚁群搜索食物的过程与旅行
商问题的相似性,利用蚁群算法求解旅行商问题(Traveling Salesman Problem,
TSP ) 、指派问题(AssignmentProblem)和调度问题( Scheduling Problem) ,取得了
一些比较满意的实验结果。蚁群算法是一种适应性好、鲁棒性强,具有正反馈结
构的并行算法。这些初步研究已显示出蚁群算法在求解复杂优化问题(特别是离
散优化问题)方面的一些优越性,证明它是一种很有发展前景的方法。蚂蚁算法在
各个领域的应用,说明该算法有着广泛的适应性,但由于该算法出现的较晚,对其
研究还处于起步阶段,远不如遗传算法、人工神经网络和模拟退火算法那样成熟。
算法的很多特性,如算法的收敛性,参数的设定都来自于大量实验统计结果,目前
对该算法理论研究有待进一步加强。
经过研究发现，蚂蚁在觅食的过程中通过一种称之为信息素（Pheromone）
的物质相互传递信息。更具体地，蚂蚁在运动过程中能够在其所经过的路径上留
下信息素，而且在运动过程中能够感受到这种信息素的存在及其强度，并以此指
导自己的运动方向。蚂蚁倾向于朝着信息素浓度高的方向前进，因此，由大量蚂
