群体智能仿真之简单蚁群算法

在生活中我们或多或少都会看到过蚂蚁，面对这个奇怪的家伙我们平时并不怎么关注它，但偶尔也会发现这个东西的神奇之处，为什么它们能成群结队的搬家，它们为什么能在群体中如此密切的配合行动，分工明确而不会乱成一团。

这就是我们要探讨的问题，这要从蚁群算法开始说起，蚁群算法是一种用来寻找优化路径的概率型算法。它由Marco Dorigo于1992年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。这是百度百科中对蚁群算法的简短描述，那么要想了解一个事物就要从他的本质开始了解。所以我就查找了一些相关的资料。首先我们知道蚂蚁是一种昆虫，而且蚂蚁的种类繁多，世界上已知有11700多种。这个就不做过多的描述了，到处都可以查得到。而蚂蚁算法的由来是从蚂蚁的社会形态中得到启发的。我们知道蚂蚁在8000万之前就建立了自己的社会，而我们人类的只有5000余年的文明史，可是我们经常会发现，小小的蚂蚁却能建立起组织完好的复杂城市，也就所谓的蚁穴。有许多“蚂蚁城市”往往由5000万个成员组成，而对比我们人类社会，人口稠密的大城市也不过1000多万人，但是却有不少的都市问题。

接下来我们了解下蚂蚁的分工，蚂蚁有四种不同的蚁型，即蚁后、雄蚁、工蚁和兵蚁，不同的蚁型有不同的分工，那么这些蚂蚁之间是怎么进行交流的呢？化学通信是蚂蚁采取的基本信息交流方式，自然界中的蚂蚁会分泌一种化学刺激物——信息素（pheromone）。这是一种很重要的东西，也是接下来算法中的一个很重要的条件。蚂蚁的许多行为受信息素调控，如蚁后分泌名为“女皇物质”的信息素来控制工蚁的发育。说到信息素我们开始进入正题了，在自然界中，尽管蚂蚁个体比较简单，但是整个蚂蚁群体却表现得高度机构化，在许多情况下可以完成许多复杂的任务，这种能力来源于蚂蚁群体中的个体协作行为，其群体行为主要包括寻找食物、任务分配和构造墓地。

那么我们主要来浅谈一下寻找食物，在自然界中，蚂蚁的食物来源总是随机散布于蚁巢周围。我们只要仔细观察就可以发现，经过一段时间之后，蚂蚁总能找到一条从蚁巢到食物的最短路线，这条路上蚂蚁都整整齐齐的排着队，在路线上来回运动。

 下面我们用几幅图来说明一下

如图a所示可以看到蚂蚁和事物源之间是一条直线；当食物和巢穴之间出现一个障碍物的时候如图b所示，我们可以看到各只蚂蚁之间的分布是均匀的，不管路径长短，蚂蚁总是按同等概率选择各条路径；蚂蚁在运动的过程中能留下信息素，而且能感知这种物质的存在及其强度，并倾向于信息素浓度高的方向运动的概率也会比浓度低的方向概率要高，也就形成了如图c所示的现象障碍物较短的一边蚂蚁比较多，因为路径比较短来回的蚂蚁所用的时间比较短次数多留下的信息素浓度比较高，也就慢慢的吸引了其他更多的蚂蚁往这条路上走。最后形成了图d的场景，蚂蚁都集中到了路线短的一边去了。这就是蚂蚁最优路线形成的关键原因。

下面去看一下用代码实现的Demo：

规则：1、首先固定蚁巢的位置在中间位置，开始的时候利用随机数random，蚂蚁从蚁巢随机走向各个位置。

2、蚂蚁活动的最大距离为屏幕斜线距离，当移动距离达到最大距离和步数时，蚂蚁开始自动回到家的位置进行重置，进行下一轮随机；移动距离在找到家或者食物的时候清零。

3、蚂蚁移动的方向是偏向信息素浓度高的一侧移动的，信息素撒播规则按照 屏幕斜线距离/蚂蚁移动距离，也就是蚂蚁移动的距离越远撒播的信息素浓度就越低，选择方向的计算公式采用 单元格浓度/8个方向单元格浓度总和，也就蚂蚁的的观察范围是9个单元格。

4、信息素在每次迭代时，进行统一挥发一个常量值，随着时间的推移信息素如果没有跟新就会消失。

5、如果周围没有信息素的指引时，蚂蚁的运动具有一定的惯性，并有一定的概率选择其他路径，蚂蚁遇到障碍物会绕开。

---

首先看初始的状态，蚂蚁向四周随机散开，图中黄色方块的是食物，白色圆点的代表蚂蚁，棕色方块的代表障碍物，黄色圆点代表找到食物的蚂蚁。

  蚂蚁找到了去到食物的最优路线

 

 设置障碍物之后我们可以看到蚂蚁绕开了障碍物还是能找到食物

  这时候蚂蚁们进入了局部最优的状态，也是这个简单的蚁群算法的缺陷的地方，在蚂蚁的周围虽然还有很多的食物，但是搜索到一定程度，就会出现停滞状态陷入局部最优，或者盲目随机搜索，搜索时间较长，最后造成蚂蚁一直在一两个地方来回的搬运食物。

 

参考博客：http://www.cnblogs.com/Leo_wl/p/5665715.html

参考资料：蚁群算法原理及其应用/段海滨著