【蚁群算法】

蚁群算法的基本思想来源于自然界蚂蚁觅食的最短路径原理，根据昆虫科学家的观察，发现自然界的蚂蚁虽然视觉不发达，但它们可以在没有任何提示的情况下找到从食物源到巢穴的最短路径，并在周围环境发生变化后，自适应地搜索新的最佳路径。

 

蚂蚁在寻找食物源的时候，能在其走过的路径上释放一种叫信息素的激素，使一定范围内的其他蚂蚁能够察觉到。当一些路径上通过的蚂蚁越来越多时，信息素也就越来越多，蚂蚁们选择这条路径的概率也就越高，结果导致这条路径上的信息素又增多，蚂蚁走这条路的概率又增加，生生不息。这种选择过程被称为蚂蚁的自催化行为。对于单个蚂蚁来说，它并没有要寻找最短路径，只是根据概率选择；对于整个蚁群系统来说，它们却达到了寻找到最优路径的客观上的效果。这就是群体智能。

 

蚁群算法是一个寻找最优路径的方法，在蚂蚁的世界，每天的工作就是找食物，搬食物。首先，每个蚂蚁在没找到食物的时候，它们的行动会有一定的惯性，也就是说他们会朝着一个方向一直走，但这不是绝对的，那要是一直走也找不到食物岂不是要累死。在它们遇见障碍的时候就会改变方向，这个方向是随机的，这是蚂蚁的行动看起来不像一个傻子一样，起码还知道遇到障碍物躲开。但是这个举动往往是蚁群算法能找到路径的关键，因为他不是一成不变的，蚂蚁在行动的时候会有一定的随机性，用在现代我们叫做创新。蚂蚁懂得创新，你说它厉不厉害！怪不得蚂蚁总能找到最短的路径。

 

当蚂蚁找到食物的时候，就会向环境周围散发一种信息素，当然了，信息素是在一定范围内有效的，随着时间推移会消失，跟喷了香水一样大笑。其他的蚂蚁如果发现这种信息素了就会过来，这样，就会有更多的蚂蚁找到食物。当然了，如果最开始的蚂蚁找到的路径可能不是最优的，那么蚂蚁是怎样找到最优的路径呢？这就要归功于蚂蚁的创新精神了。在蚂蚁感受到信息素的时候他会沿着信息素多的方向走，但是他们偶尔也会另辟蹊径，如果他们通过这条路也找到了食物，而且这条路比之前的路更短，那么逐渐的更多的蚂蚁会被吸引到这条路径上来。为什么会有这样的事情发生呢？因为在相同的时间里，路径越短，蚂蚁走的次数就越多，散发的信息素浓度越高。

 

 

蚁群算法能做什么

蚁群算法根据模拟蚂蚁寻找食物的最短路径行为来设计的仿生算法，因此一般而言，蚁群算法用来解决最短路径问题，并真的在旅行商问题（TSP，一个寻找最短路径的问题）上取得了比较好的成效。目前，也已渐渐应用到其他领域中去，在图着色问题、车辆调度问题、集成电路设计、通讯网络、数据聚类分析等方面都有所应用。

 

 

规则

(1)感知范围

蚂蚁观察到的范围是一个方格世界，相关参数为速度半径，一般为3，可观察和移动的范围为3x3方格。

(2)环境信息

蚂蚁所在环境中有障碍物、其他蚂蚁、信息素，其中信息素包括食物信息素(找到食物的蚂蚁留下的)、窝信息素(找到窝的蚂蚁留下的)，信息素以一定速率消失。

(3)觅食规则

蚂蚁在感知范围内寻找食物，如果感知到就会过去；否则朝信息素多的地方走，每只蚂蚁会以小概率犯错误，并非都往信息素最多的方向移动。蚂蚁找窝的规则类似，仅对窝信息素有反应。

(4)移动规则

蚂蚁朝信息素最多的方向移动，当周围没有信息素指引时，会按照原来运动方向惯性移动。而且会记住最近走过的点，防止原地转圈。

(5)避障规则

当蚂蚁待移动方向有障碍物时，将随机选择其他方向；当有信息素指引时，将按照觅食规则移动。

(6)散发信息素规则

在刚找到食物或者窝时，蚂蚁散发的信息素最多；当随着走远时，散发的信息素将逐渐减少。

 

 

蚁群算法的关键参数

蚂蚁数量： 

设M表示城市数量，m表示蚂蚁数量。m的数量很重要，因为m过大时，会导致搜索过的路径上信息素变化趋于平均，这样就不好找出好的路径了；m过小时，易使未被搜索到的路径信息素减小到0，这样可能会出现早熟，没找到全局最优解。一般上，在时间等资源条件紧迫的情况下，蚂蚁数设定为城市数的1.5倍较稳妥。

 

信息素因子： 

信息素因子反映了蚂蚁在移动过程中所积累的信息量在指导蚁群搜索中的相对重要程度，其值过大，蚂蚁选择以前走过的路径概率大，搜索随机性减弱；值过小，等同于贪婪算法，使搜索过早陷入局部最优。实验发现，信息素因子选择[1,4]区间，性能较好。

 

启发函数因子： 

启发函数因子反映了启发式信息在指导蚁群搜索过程中的相对重要程度，其大小反映的是蚁群寻优过程中先验性和确定性因素的作用强度。过大时，虽然收敛速度会加快，但容易陷入局部最优；过小时，容易陷入随机搜索，找不到最优解。实验研究发现，当启发函数因子为[3,4.5]时，综合求解性能较好。

 

信息素挥发因子： 

信息素挥发因子表示信息素的消失水平，它的大小直接关系到蚁群算法的全局搜索能力和收敛速度。实验发现，当属于[0.2，0.5]时,综合性能较好。

 

信息素常数： 

这个参数为信息素强度，表示蚂蚁循环一周时释放在路径上的信息素总量，其作用是为了充分利用有向图上的全局信息反馈量，使算法在正反馈机制作用下以合理的演化速度搜索到全局最优解。值越大，蚂蚁在已遍历路径上的信息素积累越快，有助于快速收敛。实验发现，当值属于[10,1000]时，综合性能较好。

 

最大迭代次数： 

最大迭代次数值过小，可能导致算法还没收敛就已结束；过大则会导致资源浪费。一般最大迭代次数可以取100到500次。一般来讲，建议先取200，然后根据执行程序查看算法收敛的轨迹来修改取值。

 

应用

该算法应用于其他组合优化问题，如旅行商问题、指派问题、Job—shop调度问题、车辆路由问题、图着色问题和网络路由问题等。最近几年，该算法在网络路由中的应用受到越来越多学者的关注，并提出了一些新的基于蚂蚁算法的路由算法。同传统的路由算法相比较，该算法在网络路由中具有信息分布式性、动态性、随机性和异步性等特点，而这些特点正好能满足网络路由的需要。