浅谈蚂蚁算法new.doc

浅谈蚂蚁算法new.doc浅谈蚂蚁算法张铃(安徽大学) 摘要: 本文简单介绍, 近年来在人工智能界引出的新的研究小热点---- 蚂蚁算法, 以及我们对蚂蚁算法的一些研究成果。我们从完全不同的观点来研究蚂蚁等昆虫群体智能的现象, 即从进化的过程来对待昆虫的群体智能的现象。提出一个用一种特殊的人工神经网络来描述“群体智能”的数学模型, 最后用计算机对筑巢过程进行模拟。 1 .引:蚂蚁是大家司空见惯的一种昆虫,而他们的群体合作的精神令人钦佩。他们的寻食、御敌、筑巢( 蚂蚁的筑窝, 蜜蜂建巢) 之精巧令人惊叹。若我们是能从他们身上学****到一些什么的话, 也将是一件非常有益之事关于蜜蜂觅食,人们已经做过很彻底地了解,据说它们是用飞行的舞姿(兜圈圈)来传递信息,圈子的轴方向表示花蜜的方向, 用飞行的圈数表示有花蜜地方的距离, 别的蜜蜂得此信号, 就纷拥向该方向飞去。而蚂蚁觅食的方法,却另有一番世界,据研究当蚂蚁找到食物并将它搬回来时,就会在其经过的路径上留下一种“外激素”, 其他蚂蚁嗅到这个激素的“味道”, 就沿该路奋勇向前, 觅食而去。不但如此而且还会沿着最短的路径奔向食物。 20 世纪 90 年代初意大利学者 Dorigo , Maniezzo 提出的第一个“蚂蚁算法( ant colony algorithm )”。就是依照蚂蚁觅食原理,设计的一个群体智能的算法。 2 .简单的蚂蚁算法如前所述,蚂蚁能很快地找到通向食物的最短路径,下面我们较仔细地分析一下蚂蚁是如何找到到食物地点的最短程的。设一群蚂蚁(随机地)向四面八方去觅食,当某只蚂蚁觅到食物时,一般就沿原路回巢,同时在归途上留下外激素, 外激素随着向四周散发其浓度会不断下降。若有两只蚂蚁都找到食物, 且沿原路返回( 见图一)设 OA比 OBA 短, 当第一只蚂蚁回到 O 点时, 第二只蚂蚁(沿 OBA 的蚂蚁) 才回到 C点。于是 OA 路上有两次外激素的遗留物(去一次、回来一次) ,而在 OC 路是只有去一次的外激素遗留物, BCA O 图一故 OA 的外激素浓度比 OC 上大, 据研究蚂蚁一般会沿外激素浓度大的路径上前行。于是后面的蚂蚁会渐渐地沿由 O到A 的最短程到达 A 点(指所有已求到的路径中的最短者) 。以上就是蚂蚁能以最短和找到食物的原因。我们下面简单介绍,人们是如何根据这个原理设计出求最短程的“蚂蚁算法”的。下面以求通过 n 个城市的最短回路为例。设有 n 个,设在 t 时刻在第 i 个城市上有蚂蚁 a i (t) 个, 令共有 m 个蚂蚁. 设在 t 时刻在连接第 i ,j 两城市间的道路留下的外激素量为 b ij (t) 规定每个蚂蚁, 在未完成一个回路时, 不重复走已走过的城市. 第k 个蚂蚁从 i 城市到 j 城市的概率???充许的城市 tb tbp)( )( , 其中外激素量 b ij (t) 有许多不同的定义, 如可定义为:b(t)=e -ct ,c>0; 或定义为: b ij (t+n)=db ij (t)+d ij,?????????其它只蚂蚁经过边轮第第个蚂蚁求到的回路长度是第,0 ),(,1jiktt kLL etd è àá è è àá êèè àá??(t), )( 1 其中 d、e 是一正常量. (1) 这样每只蚂蚁经过 n 次迁移后就得到一条回路, 其长度记为 L k. 若满足要求,