一、算法描述
蚂蚁算法(AntColonyOptimization,ACO),又称蚁群算法,是一种用来在图中寻找优化路径的机率型技术。它由MarcoDorigo于1992年在他的博士论文中引入,其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。
昆虫世界中,蚂蚁的组成是一种群居的世袭大家庭,我们称之为蚁群。蚂蚁分为世袭制的蚁王(后)和工蚁两种,它们具有高度组织的社会性,彼此沟通不仅可以借助触觉和视觉的联系,在大规模的协调行动中还可以借助外激素(有些书称信息素)之类的信息介质。蚂蚁平时在巢穴附近作无规则行走,一旦发现食物并不立即进食而是将之搬回蚁穴与其他蚂蚁分享,在食物小时则独自搬回蚁穴,否则就回蚁穴搬兵,一路上会留下外激素,食物越大外激素的浓度就越大,越能吸引其他的蚂蚁过去一起搬去食物,这样最终就能将食物全部搬回蚁穴。
设想,如果我们要为蚂蚁
设计一个人工智能的
程序,那么这个程序要多么复杂呢?首先,要让蚂蚁能够避开障碍物,就必须根据适当的地形给它编进指令让他们能够巧妙地避开障碍物,其次,要让蚂蚁找到食物,就需要让他们遍历空间上的所有点;再次,如果要让蚂蚁找到最短的路径,那么需要计算所有可能的路径并且比较它们的大小,而且更重要的是程序的错误也许会让你前功尽弃。
然而,事实并没有想得那么复杂,每个蚂蚁只做了非常简单的
工作:检查某个范围内有无食物,并逐渐向外激素浓的方向运动。每只蚂蚁只关心很小范围内的眼前信息,而且根据这些局部信息利用几条简单的规则进行决策,这样,在蚁群这个集体里,复杂性的行为就会凸现出来。
1.范围规则
蚂蚁观察到的范围是一个方格世界,蚂蚁有一个参数为速度半径(一般是3),那么它能观察到的范围就是3*3个方格世界,并且能移动的距离也在这个范围之内。
2.环境规则
蚂蚁所在的环境是一个虚拟的世界,其中有障碍物,有别的蚂蚁,还有信息素。信息素有两种,一种是找到食物的蚂蚁洒下的食物信息素,一种是找到窝的蚂蚁洒下的窝的信息素。每个蚂蚁都仅仅能感知它范围内的环境信息。环境以一定的速率让信息素消失。
3.觅食规则
在每只蚂蚁能感知的范围内寻找是否有食物,如果有就直接过去。否则看是否有信息素,并且比较在能感知的范围内哪一点的信息素最多,这样,它就朝信息素多的地方走,并且每只蚂蚁多会以小概率犯错误,从而并不是往信息素最多的点移动。蚂蚁找窝的规则和上面一样,只不过它对窝的信息素做出反应,而对食物信息素没反应。
4.移动规则
每只蚂蚁都朝向信息素最多的方向移动。当周围没有信息素指引的时候,蚂蚁会按照自己原来运动的方向惯性地运动下去,且在运动的方向有一个随机的小的扰动。为了防止蚂蚁原地转圈,它会记住最近刚走过了哪些点,如果发现要走的下一点已经在最近走过了,它就会尽量避开。
5.避障规则
如果蚂蚁要移动的方向有障碍物挡住,它会随机地选择另一个方向,并且有信息素指引的话,它会按照觅食的规则行为。
6.播撒信息素规则
每只蚂蚁在刚找到食物或者窝的时候撒发的信息素最多,并随着它走远的距离,播撒的信息素越来越少。
根据这几条规则,蚂蚁之间并没有直接的关系,但是每只蚂蚁都和环境发生交互,而通过信息素这个纽带,实际上把各个蚂蚁之间关联起来了。比如,当一只蚂蚁找到了食物,它并没有直接告诉其他蚂蚁这儿有食物,而是向环境播撒信息素,当其他的蚂蚁经过它附近的时候,就会感觉到信息素的存在,进而根据信息素的指引找到了食物。
二、实现
理解蚁群算法的实质之后,就可以利用
计算机语言编写出一个蚁群算法程序来,关键是实现以上介绍的几个规则,下面用
Java来实现。
1.蚂蚁
蚂蚁是蚁群中最小的单位,是所有简单规则应用的最小个体。
publicclassAnt
{
publicSquareSQUARE;//蚂蚁所在方格
publicFoodCARRYING=null;//所搬的食物数
publicintID;//蚂蚁的编号
publicbooleanHELPING=false;//是否帮忙搬运食物
publicvoidmove(intturn)
{
//蚂蚁移动到下一个方格