文档介绍：浅谈蚂蚁算法张铃(安徽大学)摘要:本文简单介绍,近年来在人工智能界引岀的新的研究小热点…■蚂蚁算法,以及我们对蚂蚁算法的一些研究成果。我们从完全不同的观点来研究蚂蚁等昆虫群体智能的现象,即从进化的过程来对待昆虫的群体智能的现象。提出一个用一种特殊的人工神经网络来描述“群体智能”的数学模型,最后用计算机对筑巢过程进行模拟。弓I:蚂蚁是大家司空见惯的一种昆虫,血他们的群体合作的精神令人钦佩。他们的寻食、御敌、筑巢(蚂蚁的筑窝,蜜蜂建巢)之精巧令人惊叹。若我们是能从他们身丄学****到一些什么的话,也将是一件非常有益之事关于蜜蜂觅食,人们已经做过很彻底地了解,据说它们是用飞行的舞姿(兜圈圈)来传递信息,圈子的轴方向表示花蜜的方向,用飞行的圈数表示有花蜜地方的距离,别的蜜蜂得此信号,就纷拥向该方向飞去。而蚂蚁觅食的方法,却另有一番世界,据研究半蚂蚁找到食物并将它搬回来时,就会在其经过的路径上留下一种“外激素”,其他蚂蚁嗅到这个激索的“味道”,就沿该路奋勇向前,觅食而去。不但如此而且还会沿着最短的路径奔向食物。20世纪90年代初意大利学者Dorigo,Maniezzo提出的第一个“蚂蚁算法(antcolonyalgorithm)no就是依照蚂蚁觅食原理,设计的一个群体智能的算法。简单的蚂蚁算法如前所述,蚂蚁能很快地找到通向食物的最短路径,下面我们较仔细地分析一下蚂蚁是如何找到到食物地点的最短程的。设一群蚂蚁(随机地)向四面八方去觅食,当某只蚂蚁觅到食物时,一般就沿原路回巢,同时在归途上留下外激素,外激素随着向四周散发其浓度会不断下降。若有两只蚂蚁都找到食物,且沿原路返回(见图一)设OA比OBA短,当第一貝蚂蚁回到0点吋,第二只蚂蚁(沿OBA的蚂蚁)才冋到C点。于是OA路上有两次外激索的遗留物(去一次、冋来一次),而在OC路是只有去一次的外激索遗留物,图一故OA的外激索浓度比0C上大,据研究蚂蚁一-般会沿外激索浓度大的路径上前行。于是后面的蚂蚁会渐渐地沿由O到A的最短程到达A点(指所有已求到的路径屮的最短者)。以上就是蚂蚁能以最短和找到食物的原因。我们下面简单介绍,人们是如何根据这个原理设计出求最短程的“蚂蚁算法”的。下面以求通过n个城市的最短回路为例。设有n个,设在t吋刻在第i个城市上有蚂蚁“i(t)个,,j两城市间的道路留下的外激素量为bij(t)规定每个蚂蚁,在未完成一个回路时,⑴有许多不同的定义,如可定义为:b(Xe「>0;或定义为:bij(t+n)=dbij(t)+dij?如()=亍亠純),L提第k个蚂蚁求到的回路长度X、 [I,第/轮第R只蚂蚁经过边(i,j)也珂 0,其它其中d、e是一正常量. (1)这样每只蚂蚁经过n次迁移后就得到一条回路,,则停止•不然,利用(1)式重新计算各边的外激素浓度,进行第二轮的搜索•…以丄是利用蚂蚁算法求解最短回路的简单介绍,有兴趣的读者可参考有关的文献。借助蚂蚁的启迪,不但可以开发出求最短程的算法,还可以开发岀其它的算法,下面再举一、二。据说蚂蚁很爱卫生,对其窩内经常进行大扫除,将垃圾堆在一起,然后拉到窩外。根据蚂蚁的丄述行为,人们以蚂蚁为师设计分类算法:—•群蚂蚁随机出发,遇