蚁群算法 _生活百科

文章插图
蚁群算法蚁群算法是一种用来寻找最佳化路径的机率型算法。它由Marco Dorigo于1992年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。
【蚁群算法】这种算法具有分布计算、信息正反馈和启发式搜寻的特徵，本质上是进化算法中的一种启发式全局最佳化算法。
基本介绍中文名：蚁群算法
外文名：ant colony optimization
简称：ACO
提出人：Marco Dorigo
提出时间：1992年
所属学科：计算机
背景蚁群系统(Ant System或Ant Colony System)是由义大利学者Dorigo、Maniezzo等人于20世纪90年代首先提出来的。他们在研究蚂蚁觅食的过程中，发现单个蚂蚁的行为比较简单，但是蚁群整体却可以体现一些智慧型的行为。例如蚁群可以在不同的环境下，寻找最短到达食物源的路径。这是因为蚁群内的蚂蚁可以通过某种信息机制实现信息的传递。后又经进一步研究发现，蚂蚁会在其经过的路径上释放一种可以称之为“信息素”的物质，蚁群内的蚂蚁对“信息素”具有感知能力，它们会沿着“信息素”浓度较高路逕行走，而每只路过的蚂蚁都会在路上留下“信息素”，这就形成一种类似正反馈的机制，这样经过一段时间后，整个蚁群就会沿着最短路逕到达食物源了。思想将蚁群算法套用于解决最佳化问题的基本思路为：用蚂蚁的行走路径表示待最佳化问题的可行解，整个蚂蚁群体的所有路径构成待最佳化问题的解空间。路径较短的蚂蚁释放的信息素量较多，随着时间的推进，较短的路径上累积的信息素浓度逐渐增高，选择该路径的蚂蚁个数也愈来愈多。最终，整个蚂蚁会在正反馈的作用下集中到最佳的路径上，此时对应的便是待最佳化问题的最优解。实现蚂蚁找到最短路径要归功于信息素和环境，假设有两条路可从蚁窝通向食物，开始时两条路上的蚂蚁数量差不多：当蚂蚁到达终点之后会立即返回，距离短的路上的蚂蚁往返一次时间短，重複频率快，在单位时间里往返蚂蚁的数目就多，留下的信息素也多，会吸引更多蚂蚁过来，会留下更多信息素。而距离长的路正相反，因此越来越多的蚂蚁聚集到最短路径上来。蚂蚁具有的智慧型行为得益于其简单行为规则，该规则让其具有多样性和正反馈。在觅食时，多样性使蚂蚁不会走进死胡同而无限循环，是一种创新能力；正反馈使优良信息保存下来，是一种学习强化能力。两者的巧妙结合使智慧型行为涌现，如果多样性过剩，系统过于活跃，会导致过多的随机运动，陷入混沌状态；如果多样性不够，正反馈过强，会导致僵化，当环境变化时蚁群不能相应调整。规则(1)感知範围蚂蚁观察到的範围是一个方格世界，相关参数为速度半径，一般为3，可观察和移动的範围为3x3方格。(2)环境信息蚂蚁所在环境中有障碍物、其他蚂蚁、信息素，其中信息素包括食物信息素(找到食物的蚂蚁留下的)、窝信息素(找到窝的蚂蚁留下的)，信息素以一定速率消失。(3)觅食规则蚂蚁在感知範围内寻找食物，如果感知到就会过去；否则朝信息素多的地方走，每只蚂蚁会以小机率犯错误，并非都往信息素最多的方向移动。蚂蚁找窝的规则类似，仅对窝信息素有反应。(4)移动规则蚂蚁朝信息素最多的方向移动，当周围没有信息素指引时，会按照原来运动方向惯性移动。而且会记住最近走过的点，防止原地转圈。(5)避障规则当蚂蚁待移动方向有障碍物时，将随机选择其他方向；当有信息素指引时，将按照觅食规则移动。(6)散发信息素规则在刚找到食物或者窝时，蚂蚁散发的信息素最多；当随着走远时，散发的信息素将逐渐减少。特点与其他最佳化算法相比，蚁群算法具有以下几个特点：(1)採用正反馈机制，使得搜寻过程不断收敛，最终逼近最优解。(2)每个个体可以通过释放信息素来改变周围的环境，且每个个体能够感知周围环境的实时变化，个体间通过环境进行间接地通讯。(3)搜寻过程採用分散式计算方式，多个个体同时进行并行计算，大大提高了算法的计算能力和运行效率。(4)启发式的机率搜寻方式不容易陷入局部最优，易于寻找到全局最优解。套用该算法套用于其他组合最佳化问题，如旅行商问题、指派问题、Job—shop调度问题、车辆路由问题、图着色问题和网路路由问题等。最近几年，该算法在网路路由中的套用受到越来越多学者的关注，并提出了一些新的基于蚂蚁算法的路由算法。同传统的路由算法相比较，该算法在网路路由中具有信息分散式性、动态性、随机性和异步性等特点，而这些特点正好能满足网路路由的需要。