蚁群算法

蚁群算法

算法简介：
蚁群算法是一种用来寻找优化路径的概率型算法。它由Marco Dorigo于1992年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。
这种算法具有分布计算、信息正反馈和启发式搜索的特征，本质上是进化算法中的一种启发式全局优化算法。
基本原理：
1、蚂蚁在路径上释放信息素。
2、碰到还没走过的路口，就随机挑选一条路走。同时，释放与路径长度有关的信息素。
3、信息素浓度与路径长度成反比。后来的蚂蚁再次碰到该路口时，就选择信息素浓度较高路径。
4、最优路径上的信息素浓度越来越大。
5、最终蚁群找到最优寻食路径。
算法实例：
旅行商问题(TSP)优化

对于每只蚂蚁k ，路径记忆向量 Rk按照访问顺序记录了所有k已经经过的城市序号。设蚂蚁k当前所在城市为i， 则其选择城市j作为下一个访问对象的概率为：

信息素更新

这里m是蚂蚁个数, ρ是信息素的蒸发率，规定0≤ ρ≤1， 在AS中通常设置为 ρ =0.5，Δτij是第k只蚂蚁在它经过的 边上释放的信息素量，它等于蚂蚁k本轮构建路径长度的 倒数。Ck表示路径长度，它是Rk中所有边的长度和。

~alpha 是信息素重要程度因子
~beta 是启发函数重要程度因子
~rho 是信息素挥发因子
~用坐标来表示城市位置；
~用 D(i,j) = sqrt(sum((citys(i,:) - citys(j,:)).^2))计算城市之间的距离；
~用random函数随机产生各个蚂蚁的起点城市；
~用轮盘赌法选择下一个访问城市；
~通过禁忌表来控制蚂蚁不走已走过的路线。

当beta 和rho不变时，改变alpha，得到结果如下：
alpha=0.3时：


alpha=0.5时：


alpha=1时：


可以看出来alpha越大，蚂蚁选择之前走过的路径可能性就越大，搜索路径的随机性就减弱，alpha越小，蚁群搜索范围就会减少，容易陷入局部最优

当alpha和rho不变时，改变beta，得到结果如下：
beta=0.5时，


beta=1时，

beta=3时，


通过上面的图片对照可以得出beta值越大，蚁群就越容易选择局部较短路径，这时算法的收敛速度是加快了，但是随机性不高，容易得到局部的相对最优

当alpha和beta不变时，改变rho，得到结果如下：
rho=0.1时，

rho=0.5时，

rho=0.9时，

信息素挥发因子rho对算法的影响具有双重性,当rho较小时，未被选中路径上的信息量将迅速衰减，这使搜索空间减小，算法陷入局部最优的可能性加大而算法的收敛性提高；另一方面，被选路径上的信息量增量减小，这使搜索空间增大，算法陷入局部最优的可能性减小，而算法的收敛性降低。

实验小结：
1、alpha越大，蚂蚁选择之前走过的路径可能性就越大，搜索路径的随机性就减弱，alpha越小，蚁群搜索范围就会减少，容易陷入局部最优；beta值越大，蚁群就越容易选择局部较短路径，这时算法的收敛速度是加快了，但是随机性不高，容易得到局部的相对最优；信息素挥发因子rho对算法的影响具有双重性，居中最佳。
2、蚁群算法中每个个体可以通过释放信息素来改变周围的环境，且每个个体能够感知周围环境的实时变化，个体间通过环境进行间接地通讯，所以它可以运用于许多实例中。
3、蚁群算法具有收敛速度慢和易于陷入局部最优解的缺点，还待改进。