浅谈蚂蚁算法

《浅谈蚂蚁算法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、浅谈蚂蚁算法张铃（安徽大学）摘要：木文简单介绍，近年来在人工智能界引出的新的研究小热点一--蚂蚁算法，以及我们对蚂蚁算法的一些研究成果。我们从完全不同的观点來研究蚂蚁等昆虫群体猖能的现象，即从进化的过程來对待昆虫的群体智能的现象。提出一个用一种特殊的人工神经网络来描述“群体智能”的数学模型，最后用计算机对筑巢过程进行模拟。1.弓I：蚂蚁是人家司空见惯的一种昆虫，而他们的群体合作的精神令人钦佩。他们的寻食、御敌、筑巢（蚂蚁的筑贞，蜜蜂建巢）之精巧令人惊叹。若我们是能从他们身上学习到一些什么的话，也将是一件非常冇益Z事关于蜜蜂觅食，人们已经做过很彻

2、底地了解，据说它们是用飞行的舞姿（兜圈圈）来传递信息，圈子的轴方向表示花蜜的方向，用飞行的圈数表示有花蜜地方的距离，别的蜜蜂得此信号，就纷拥向该方向飞去。而蚂蚁觅食的方法，却另有一番世界，据研究当蚂蚁找到食物并将它搬回来时，就会在具经过的路径上帘下一种“外激素”，其他蚂蚁嗅到这个激素的“味道”，就沿该路奋勇向前，觅食而去。不但如此

3、仏口.述会沿着最短的路径奔向食物。20世纪90年代初意大利学者Dorigo,Maniezzo提出的第―个"蚂蚁算法（antcolonyalgorithm）"。就是依照蚂蚁觅食原理，设计的一个群体智能的算法。2.简单的

4、蚂蚁算法如前所述，蚂蚁能很快地找到通向食物的最短路径，卜•面我们较仔细地分析一卜•蚂蚁是如何找到到食物地点的最短程的。设一群蚂蚁（随机地）向四面八方去觅食，当某只蚂蚁觅到食物时，--般就沿原路回巢，同时在归途上留下外激素，外激素随曹向四周散发其浓度会不断下降。若有两只蚂蚁都找到食物，且沿原路返回（见图一）设0A比0BA短，当第一只蚂蚁回到0点时，第二只蚂蚁（沿0BA的蚂蚁）才回到C点。于是0A路上有两次外激素的遗超物（去一次、回来一次），而在0C路是只有去一次的外激素遗超物，故0A的外激素浓度比0C上大，据研究蚂蚁一般会沿外激素浓度大的路径上前

5、行。于是后面的蚂蚁会渐渐地沿由0到A的最短程到达A点（指所有已求到的路径中的最短者）。以上就是蚂蚁能以最短和找到食物的原因。我们下面简单介绍，人们是如何根据这个原理设计出求最短程的“蚂蚁算法”的。下面以求通过n个城市的最矩回路为例。设有n个，设在t时刻在第i个城市上有蚂蚁ai（t）个，令共有m个蚂蚁.设在t时刻在连接第i,j两城市间的道路留下的外激索量为bi,t）规定每个蚂蚁，在未完成一个I叫路时，不重复走己走过的城市.第k个蚂蚁从i城市到j城市的概率P厂工厲⑴’jw充许的城市英中外激素量bj（t）冇许多不同的定义，如可定义为:b（t）=ect

6、,c>0;或定义为：bii(t+n)=dbii(t)+dij,ij(t),s是第/<个蚂蚁求到的回路长度第r轮第k只蚂蚁经过边（/J）0,其它其中d.e是一正常量.（1）这样每只蚂蚁经过n次迁移示就得到一条冋路，其长度记为U.若满足要求，则停止•不然，利用（1）式重新计算各边的外激索浓度，进行第二轮的搜索….以上是利用蚂蚁算法求解最短回路的简单介绍，有兴趣的读者可参考有关的文献。借助蚂蚁的启辿，不但可以开发出求最短程的算法，还可以开发出其它的算法，下面再举一、二。据说蚂蚁很爱卫生，对其窩内经常进行大扫除，将垃圾堆在一起，然后拉到窩外。根据蚂蚁的

7、上述行为，人们以蚂蚁为师设计分类算法：一群蚂蚁随机出发，遇到垃圾，就将其拉走（拉的方向也是随机的），拉垃圾时，若遇到某一堆垃圾时，就放下。放下垃圾后，再次进行拉垃圾行为。。。。当然还要加了一些限制，才能达到人们所希望的结果。另外，蚂蚁同心协进行搬运食物，是我们见得最多的蚂蚁行为，有人以此为蓝本设计出几个机器人共同推盒子的算法。如美国阿尔伯塔大学设计出儿个机器人共同推盒子的实验。借助蚂蚁分工合作的特点（蚁皇管牛男育女、工蚁管干活、兵蚁管保卫）的启迪，人们设计了求解任务分配问题的蚂蚁算法，并应用于工厂屮汽车喷漆问题。如美国西北人学将蚂蚁算法用于卡车

8、厂汕漆车间，负责给离开装配线的卡车上漆的工作安排。他们采取工人分组，各组只喷一种颜色，只冇当某小组任务特别紧张吋，才分配另一小组前去帮助。通过这种设计后工厂各车间改变颜色的次数更少，从而提高了整体的生产率。乂如美国MClWorld-com公司一直研究人工蚂蚁，并用于管理公司的电话网，对用户记帐收费等工作。另外，述设计“人工蚂蚁”打算用于因特网的路由管理。国内也冇研究者用蚂蚁算法求解全国144个城市的最魚回路问题，求得的解同其它方法求到得解一样精确，这说明蚂蚁算法不但是求解组合优化问题的nJ行方法，而且是一种很有竞争力的算法。1.蚂蚁筑巢的启迪群

9、体智能蚂蚁群最令惊叹的能力是“筑巢”，这类“群体智能”是自然界中普遍存在的现象，其中道理我们并不清楚，但我们可以对这种现象进行“唯象”地建模研究。蚂蚁