[转帖]浅谈蚂蚁算法（精品）

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

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

2、人们已经做过很彻底地了解，据说它们是用飞行的舞姿（兜圈圈）來传递信息，圈子的轴方向表示花蜜的方向，用飞行的圈数表示有花蜜地方的距离，别的蜜蜂得此信号，就纷拥向该方向飞去。而蚂蚁觅食的方法，却另有一番世界，据研究当蚂蚁找到食物并将它搬回来时，就会在其经过的路径上留下一种“外激索”，其他蚂蚁嗅到这个激索的“味道”，就沿该路奋勇向前，觅食而去。不但如此而且还会沿着最短的路径奔向食物。20世纪90年代初意犬利学者Dorigo,Maniezzo提岀的第一个"蚂蚁算法（antcolonyalgorithm）"o就是依照蚂蚁觅食原理，设计的

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

4、，据研究蚂蚁一般会沿外激素浓度大的路径上前行。于是后面的蚂蚁会渐渐地沿由0到A的最短程到达A点（指所有已求到的路径中的最短者）。以上就是蚂蚁能以最短和找到食物的原I大I。我们下而简单介绍，人们是如何根据这个原理设计出求最短程的“蚂蚁算法”的。下而以求通过n个城市的最短回路为例。设有n个，设在I时刻在第i个城市上有蚂蚁ai（t）个，令共有m个蚂蚁.设在t吋刻在连接第ij两城市间的道路留下的外激索量为bj（t）规定每个蚂蚁，在未完成一个冋路时，不重复走已走过的城市.第k个蚂蚁从i城市到j城市的概率Jw充许的城市其屮外激素量bij⑴

5、有许多不同的定义，如可定义为:b（tW>0；或定义为:bij(t+n)=dbij(t)+dij.如（）=£1沁），S是第k个蚂蚁求到的冋路长度*=iLk打、［1,第/轮第k只蚂蚁经过边（z,j）勺心］0,其它其中d、e是一正常量.（1）这样每只蚂蚁经过n次迁移后就得到一条冋路，其长度记为Lk•若满足耍求，则停止•不然,利用（1）式重新计算各边的外激素浓度，进行第二轮的搜索•…以上是利用蚂蚁算法求解最短回路的简单介绍，有兴趣的读者可参考有关的文献。借助蚂蚁的启迪，不但可以开发岀求最短程的算法，还可以开发出其它的算法，下而再举一、

6、—0据说蚂蚁很爱卫生，对其窩内经常进行大扫除，将垃圾堆在-•起，然后拉到窩外。根据蚂蚁的上述行为，人们以蚂蚁为师设计分类算法：一群蚂蚁随机出发，遇到垃圾，就将其拉走（拉的方向也是随机的），拉垃圾时，若遇到某一堆垃圾时，就放下。放下垃圾后，再次进行拉垃圾行为。。。。当然还要加了一些限制,才能达到人们所希望的结果。另外，蚂蚁同心协进行搬运食物，是我们见得最多的蚂蚁行为，有人以此为兰本设计出几个机器人共同推盒子的算法。如美国阿尔伯塔大学设计出几个机器人共同推盒子的实验。借助蚂蚁分工合作的特点（蚁皇管生男育女、工蚁管干活、兵蚁管保卫）

7、的启迪，人们设计了求解任务分配问题的蚂蚁算法，并应用于工厂屮汽车喷漆问题。如美国西北大学将蚂蚁算法用于卡车厂油漆车间，负责给离开装配线的卡车上漆的工作安排。他们釆取工人分组,各组只喷一种颜色，只有当某小组任务特别紧张时，才分配另一小组前去帮助。通过这种设计后工厂各车间改变颜色的次数更少，从而提高了整体的生产率。又如美国MCIWorld-com公司一直研究人工蚂蚁，并用于管理公司的电话网，对用户记帐收费等工作。另外，还设计“人工蚂蚁”打算用于因特网的路由管理。国内也有研究者用蚂蚁算法求解全国144个城市的最短回路问题，求得的解同

8、其它方法求到得解一样精确，这说明蚂蚁算法不但是求解组合优化问题的可行方法，而且是一种很有竞争力的算法。3•蚂蚁筑巢的启迪-■…群体智能蚂蚁群最令惊叹的能力是“筑巢”，这类“群体智能”是口然界中普遍存在的现象，其中道理我们并不清楚，但我们可以对这种现象进行“唯象”地建模研究。蚂