欢迎来到天天文库
浏览记录
ID:44584840
大小:255.09 KB
页数:5页
时间:2019-10-23
《[转帖]浅谈蚂蚁算法(精品)》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库。
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•蚂蚁筑巢的启迪-■…群体智能蚂蚁群最令惊叹的能力是“筑巢”,这类“群体智能”是口然界中普遍存在的现象,其中道理我们并不清楚,但我们可以对这种现象进行“唯象”地建模研究。蚂
此文档下载收益归作者所有