自话蚁群算法（带简单模拟实验）

2016-07-17 00:06:00

原文地址：http://breezedust.com/2016/07/10/zi-hua-yi-qun-suan-fa-jian-dan-mo-ni-shi-li/

这算是填3年前的一个坑吧，已经懒癌晚期了，想必也还是要挣扎下，那今天先从蚁群算法这个坑说起，如果你是要寻找怎么优化蚁群算法，可以直接跳过本文，如果你还不了解什么是蚁群算法，或许本文能够提起你的兴趣。

如果你同样对遗传算法和粒子群算法感兴趣，请查看3年前我对于这两个算法见解的文章。

自话粒子群算法（超简单实例)
自话遗传算法（带实例）

简单蚁群算法模拟实验：

Demo
Github

这个模拟实验比较简单，并没有对信息素、路径选择等做优化，主要是方便大家查看简单的蚂蚁系统能够带来一个什么样的效果,详细说明见后文。

什么是蚁群算法

按百度百科的话来说，蚁群算法(ant colony optimization, ACO)，又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型算法。它由Marco Dorigo于1992年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。蚁群算法是一种模拟进化算法，初步的研究表明该算法具有许多优良的性质，并且现在已用于我们生活的方方面面。

基本原理

蚂蚁在运动过程中，会留下一种称为信息素的东西，并且会随着移动的距离，播散的信息素越来越少，所以往往在家或者食物的周围，信息素的浓度是最强的，而蚂蚁自身会根据信息素去选择方向，当然信息素越浓，被选择的概率也就越大，并且信息素本身具有一定的挥发作用。蚂蚁的运动过程可以简单归纳如下：

当周围没有信息素指引时，蚂蚁的运动具有一定的惯性，并有一定的概率选择其他方向
当周围有信息素的指引时，按照信息素的浓度强度概率性的选择运动方向
找食物时，蚂蚁留下家相关的A信息素，找家时，蚂蚁留下食物相关的B信息素，并随着移动距离的增加，洒播的信息素越来越少
随着时间推移，信息素会自行挥发

一个简单的例子，如果现在有两条通往食物的路径，一条较长路径A,一条较短路径B,虽然刚开始A,B路径上都有蚂蚁，又因为B比A短，蚂蚁通过B花费的时间较短，随着时间的推移和信息素的挥发，逐渐的B上的信息素浓度会强于A，这时候因为B的浓度比A强，越来越多多蚂蚁会选择B，而这时候B上的浓度只会越来越强。如果蚂蚁一开始只在A上呢，注意蚂蚁的移动具有一定小概率的随机性，所以当一部分蚂蚁找到B时，随着时间的推移，蚂蚁会收敛到B上，从而可以跳出局部最优。

实验

上面的描述可能不是很形象，现在我们来模拟做个小实验，实验地址Demo，源码已放在 Github

简单蚁群实验环境：

满足上面4点基本规则,信息素散播规则按照屏幕斜线距离/蚂蚁移动距离，移动距离在找到食物或者家清0(言外之意式，蚂蚁最多能够移动斜线这么远的距离，这个公式比较简单)
超过一定的移动步数未找到食物或窝的蚂蚁进行重置
选择方向的计算公式采用单元格浓度/8个方向单元格浓度总和,用轮盘赌进行概率选择
信息素在每次迭代时，进行统一挥发一个常量值

现在我们来看看蚂蚁是否能够找到最近的食物。

1.首先我们放置一个较远的食物A，图中的绿色为食物，白色为蚂蚁，暗蓝色为家相关的信息素，颜色深浅代表浓度。

注意：我们上面采用的信息素洒播规则，会让家相关的信息素浓度围绕着家呈梯形分布，这样蚂蚁在回家时，能够根据浓度找到家，食物相关信息素也一样。感兴趣的朋友可以在源码里修改信息素显示参数，显示食物相关的信息素分布图。

2.过一会儿，我们发现蚂蚁都聚集在这条路径上，然后我们放一个离得很近的食物B

3.最后我们会发现这条路径上的蚂蚁越来越多，再过一会儿，A路径上基本没有什么蚂蚁了。

你有可能问，那障碍是干嘛用的，我当时只是想干一件小时候经常干的事情，如

1.一群蚂蚁找到了食物

2.我拦住了他们的去路

3.最后他们还是找到了食物，坏笑

最后

如果你亲自动手做实验，你会发现，当蚂蚁在一条路径上觅食很久时，你再放置一个近的食物基本没啥效果，你也可以理解为当一只蚂蚁找到一条路径时，过了很久的时间，大多数蚂蚁都选择了这条路径，就在这时候，突然有一只蚂蚁找到了较近的食物，但因为时间过得太久，两条路径上浓度相差太大（浓度越大，被选择的概率就越大），整个系统基本已经停滞了，陷入了局部最优。所以简单的蚂蚁系统是存在一些问题的，如：