蚁群算法

落日映苍穹つ 2022-06-05 03:36 200阅读 0赞

**1.蚁群算法定义**  
又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型算法。它由Marco Dorigo于1992年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。蚁群算法是一种模拟进化算法，初步的研究表明该算法具有许多优良的性质，并且现在已用于我们生活的方方面面。  
**2.基本原理**  
蚂蚁在运动过程中，会留下一种称为信息素的东西，并且会随着移动的距离，播散的信息素越来越少，所以往往在家或者食物的周围，信息素的浓度是最强的，而蚂蚁自身会根据信息素去选择方向，当然信息素越浓，被选择的概率也就越大，并且信息素本身具有一定的挥发作用。 蚂蚁的运动过程可以简单归纳如下：

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

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

实验demo：[http://lab.breezedust.com/aco/][http_lab.breezedust.com_aco]  
github：[https://github.com/BreezeDust/AlgorithmsLab/tree/master/heuristic/ACO][https_github.com_BreezeDust_AlgorithmsLab_tree_master_heuristic_ACO]

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

1）搜索到一定程度，会出现停滞状态，陷入局部最优的情况  
2）盲目的随机搜索，搜索时间较长

而影响蚂蚁是否能够找到好的最优解，依赖这几个关键因素：

1）信息素怎么洒播（比如维持在一个特地范围的值等）  
2）信息素怎么挥发（除了全局挥发，可以让蚂蚁自身进行局部挥发等手段）  
3）通过怎样的方式让蚂蚁选择运动方向，减少盲目性和不必要性（给蚂蚁一点点智能和经验）  
4）给蚂蚁和环境一定的记忆能力能够帮助减少搜索空间

原文链接：[https://www.cnblogs.com/Leo\_wl/p/5665715.html][https_www.cnblogs.com_Leo_wl_p_5665715.html]

[http_lab.breezedust.com_aco]: http://lab.breezedust.com/aco/
[https_github.com_BreezeDust_AlgorithmsLab_tree_master_heuristic_ACO]: https://github.com/BreezeDust/AlgorithmsLab/tree/master/heuristic/ACO
[https_www.cnblogs.com_Leo_wl_p_5665715.html]: https://www.cnblogs.com/Leo_wl/p/5665715.html