<b>蚁群算法小程序(C/C++语言实现)(一)</b>[VC/C++编程]

算法注释:

程序开始运行,蚂蚁们开始从窝里出动了,探求食物;他们会顺着屏幕爬满整个画面,直到找到食物再返回窝.

此中,‘F’点表示食物,‘H’表示窝,白色块表示障碍物,‘+’就是蚂蚁了.

预期的后果:各个蚂蚁在没有事前奉告他们食物在什么地方的前提下开始探求食物.当一只找到食物今后,它会向环境释放一种信息素,吸引其他的蚂蚁过来,这样越来越多的蚂蚁会找到食物!有些蚂蚁并没有象别的蚂蚁一样总反复一样的路,他们会另辟蹊径,假如令开辟的道路比本来的其他道路更短,那么,渐渐,更多的蚂蚁被吸引到这条较短的路上来.最后,经过一段时间运行,大概会呈现一条最短的途径被大大都蚂蚁反复着.

原理:为什么小小的蚂蚁可以找到食物?他们具有智能么?假想,假如我们要为蚂蚁计划一个人工智能的程序,那么这个程序要多么复杂呢?首先,你要让蚂蚁可以避开障碍物,就必须按照得当的地形给它编进指令让他们可以巧妙的避开障碍物,其次,要让蚂蚁找到食物,就需求让他们遍历空间上的全部点;再次,假如要让蚂蚁找到最短的途径,那么需求计算全部大概的途径并且对比它们的大小,并且更重要的是,你要当心翼翼的编程,因为程序的错误大概会让你半途而废.这是多么难以想象的程序!太复杂了,恐怕没人可以完成这样烦琐冗余的程序.

但是,事实并没有你想得那么复杂,上面这个程序每个蚂蚁的核心程序编码不过100多行!为什么这么简单的程序会让蚂蚁干这样复杂的事情?答案是:简单法则的涌现.事实上,每只蚂蚁并非像我们想象的需求知道整个世界的信息,他们其实只关心很小范围内的眼前信息,并且按照这些部分信息操纵几条简单的法则举行抉择,这样,在蚁群这个集体里,复杂性的行为就会凸现出来.这就是人工生命、复杂性科学注释的规律!那么,这些简单法则是什么呢?下面具体阐明:

1、范围:蚂蚁察看到的范围是一个方格世界,蚂蚁有一个参数为速度半径（普通是3）,那么它能察看到的范围就是3*3个方格世界,并且能移动的距离也在这个范围之内.

2、环境:蚂蚁所在的环境是一个虚拟的世界,此中有障碍物,有别的蚂蚁,还有信息素,信息素有两种,一种是找到食物的蚂蚁洒下的食物信息素,一种是找到窝的蚂蚁洒下的窝的信息素.每个蚂蚁都仅仅能感知它范围内的环境信息.环境以一定的速率让信息素消逝.

3、寻食法则:在每只蚂蚁能感知的范围内探求能否有食物,假若有就直接过去.不然看能否有信息素,并且对比在能感知的范围内哪一点的信息素最多,这样,它就朝信息素多的地方走,并且每只蚂蚁多会以小概率出错误,从而并非往信息素最多的点移动.蚂蚁找窝的法则和上面一样,只不过它对窝的信息素做出反映,而对食物信息素没反映.

4、移动法则:每只蚂蚁都朝向信息素最多的方向移,并且,当四周没有信息素指引的时刻,蚂蚁会按照自己本来运动的方向惯性的运动下去,并且,在运动的方向有一个随机的小的扰动.为了避免蚂蚁原地转圈,它会记着近来刚走过了哪些点,假如发现要走的下一点已经在近来走过了,它就会尽大概避开.

5、避障法则:假如蚂蚁要移动的方向有障碍物挡住,它会随机的挑选另一个方向,并且有信息素指引的话,它会按照寻食的法则行为.

7、播撒信息素法则:每只蚂蚁在刚找到食物大概窝的时刻撒发的信息素最多,并随着它走远的距离,播撒的信息素越来越少.

按照这几条法则,蚂蚁之间并没有直接的关系,但是每只蚂蚁都和环境发生交互,而通过信息素这个纽带,实际上把各个蚂蚁之间关联起来了.比方,当一只蚂蚁找到了食物,它并没有直接奉告别的蚂蚁这儿有食物,而是向环境播撒信息素,当别的的蚂蚁经过它四周的时刻,就会感遭到信息素的存在,进而按照信息素的指引找到了食物.

问题:说了这么多,蚂蚁毕竟是怎么找到食物的呢?

在没有蚂蚁找到食物的时刻,环境没有有效的信息素,那么蚂蚁为什么会相对有效的找到食物呢?这要归功于蚂蚁的移动法则,特别是在没有信息素时刻的移动法则.首先,它要能尽大概保持某种惯性,这样使得蚂蚁尽大概向前方移动（开始,这个前方是随机固定的一个方向）,而不是原地无谓的打转大概震惊;其次,蚂蚁要有一定的随机性,固然有了固定的方向,但它也不能像粒子一样直线运动下去,而是有一个随机的干扰.这样就使得蚂蚁运动起来具有了一定的目的性,尽大概保持本来的方向,但又有新的摸索,特别当碰到障碍物的时刻它会当即改变方向,这可以当作一种挑选的历程,也就是环境的障碍物让蚂蚁的某个方向精确,而其他方向则不对.这就注释了为什么单个蚂蚁在复杂的诸如迷宫的地图中仍旧能找到躲藏得很好的食物.

当然,在有一只蚂蚁找到了食物的时刻,其他蚂蚁会沿着信息素很快找到食物的.

蚂蚁若何找到最短途径的?这一是要归功于信息素,别的要归功于环境,具体说是计算机时钟.信息素多的地方明显经过这里的蚂蚁会多,因而会有更多的蚂蚁堆积过来.假定有两条路从窝通向食物,开始的时刻,走这两条路的蚂蚁数目一样多（大概较长的路上蚂蚁多,这也无关紧急）.当蚂蚁沿着一条路到达终点今后会即刻返回来,这样,短的路蚂蚁往复一次的时间就短,这也意味着反复的频率就快,因而在单位时间里走过的蚂蚁数目就多,洒下的信息素自然也会多,自然会有更多的蚂蚁被吸引过来,从而洒下更多的信息素……;而长的路正相反,因此,越来越多地蚂蚁堆积到较短的途径上来,最短的途径就近似找到了.大概有人会问部分最短途径和全局最短路的问题,实际上蚂蚁渐渐接近全局最短路的,为什么呢?这源于蚂蚁会出错误,也就是它会按照一定的概率不往信息素高的地方走而另辟蹊径,这可以理解为一种创新,这种创新假如能缩短路途,那么按照方才论述的原理,更多的蚂蚁会被吸引过来.

引伸随着蚂蚁的踪影,你找到了什么?通过上面的原理论述和实际操作,我们不难发现蚂蚁之所以具有智能行为,完好归功于它的简单行为法则,而这些法则综合起来具有下面两个方面的特点:

1、多样性2、正反馈多样性保证了蚂蚁在寻食的时刻不置走进死胡同而无限循环,正反馈机制则保证了相对优异的信息可以被保存下来.我们可以把多样性当作是一种创造本领,而正反馈是一种学习强化本领.正反馈的力气也可以比方成声望的看法,而多样性是冲破声望表现的创造性,恰是这两点当心翼翼的巧妙结合才使得智能行为涌现出来了.[Page]引伸来说,大自然的进化,社会的进步、人类的创新实际上都离不开这两样东西,多样性保证了系统的创新本领,正反馈保证了优异特点可以得到强化,二者要恰到好处的结合.假如多样性多余,也就是系统过于活泼,这相当于蚂蚁会过量的随机运动,它就会陷入浑沌状况;而相反,多样性不够,正反馈机制过强,那么系统就好比一潭死水.这在蚁群中来说就表现为,蚂蚁的行为过于僵硬,当环境改变了,蚂蚁群仍旧不能得当的调整.

既然复杂性、智能行为是按照底层法则涌现的,既然底层法则具有多样性和正反馈特点,那么大概你会问这些法则是那边来的?多样性和正反馈又是那边来的?我本人的看法:法则根源于大自然的进化.而大自然的进化按照方才讲的也表现为多样性和正反馈的巧妙结合.而这样的巧妙结合又是为什么呢?为什么在你眼前显现的世界是如此维妙维肖呢?答案在于环境造就了这一切,之所以你看到维妙维肖的世界,是因为那些不可以适应环境的多样性与正反馈的结合都已经死掉了,被环境淘汰了!

参数阐明:最大信息素:蚂蚁在一开始拥有的信息素总量,越大表示程序在较长一段时间可以存在信息素.信息素消减的速度:随着时间的流逝,已经存在于世界上的信息素会消减,这个数值越大,那么消减的越快.

错误概率表示这个蚂蚁不往信息素最大的区域走的概率,越大则表示这个蚂蚁越有创新性.

速度半径表示蚂蚁一次能走的最大长度,也表示这个蚂蚁的感知范围.

记忆本领表示蚂蚁能记着多少个方才走过点的坐标,这个值避免了蚂蚁在本地打转,阻滞不前.而这个值越大那么整个系统运行速度就慢,越小则蚂蚁越简单原地转圈.

　　以上是“<b>蚁群算法小程序(C/C++语言实现)(一)</b>[VC/C++编程]”的内容，如果你对以上该文章内容感兴趣，你可以看看七道奇为您推荐以下文章：