蚁群算法

简述

在蚂蚁种群中，蚂蚁间相互交流的方式是通过一种名为信息素的物质，它可以是蚂蚁行动时留下的物质，可以被其他蚂蚁所感知。

蚁群算法

在寻找食物的过程中，如左图所示，三角形ABC是等边三角形，蚂蚁窝在A点，C点有食物，A点的两只蚂蚁选择了两条路线前往C点，一条为AB->BC，另一条A->C，当走远路的蚂蚁，到达C点时，延AC边上的蚂蚁已经走了一个来回，路径上信息素如右图所示。后到会感知到边AC上的信息素浓度更高一些，于是他也会选择AC来行走，因为相同时间内，信息素浓度更高的说明，路程更短。

蚁群算法便是基于这样的一个思想来解决如TSP等优化问题，一下介绍便是拿TSP问题来介绍蚁群算法

基础知识

初始信息素

信息素用符号τ来表示，如下式，下标i，j表示从城市i到城市j这条道路上的信息素，上标0表示这是初次计算，也就是初始信息素，初始信息素都设置为1，或者一个较小的常数，表示每条道路上的信息素都相等，这样通过运算蚂蚁爬向各个城市的概率都相等

信息素

道路选择

基于信息素，每只蚂蚁都有一个选择道路的公式，如下式

选择道路概率

其中

J(k)
表示为蚂蚁k未走过的地方，禁忌表tabu_k表示为蚂蚁走过的地方，当所有n个城市都加入到tabu中，则表示蚂蚁完成了一次周游。概率式子中η是一个启发因子，通常为城市i到j距离的倒数，启发因子存在的目的是为对蚂蚁的初步移动产生指引，α和β分别表示信息素和启发因子的相对重要程度，个人感觉可以预先设定也可以随迭代次数更新，比如初期时β稍微大一些，方便蚂蚁找到最优解的邻域，后期α稍微打些，方便结果收敛。概率的式子实际作用就是计算出了每一条路径所占的权重，权重大的路径被蚂蚁选中的概率就大。

信息素更新

当所有蚂蚁完成一次周游后，各个路径上的信息素进行一次更新

信息素更新
其中ρ表示信息素的消散系数，前半部就是表示原有信息素的保留，Δτ则表示的信息素的增量，Δτ的计算方式有很多种，其中ant-cycle的模型计算如下
单个蚂蚁对τ的影响
其中Q为蚂蚁完成一次周游释放的总信息素，L_k为这次周游的总长度，长度越长，信息素留的越少。当然，别忘了计算信息素变量的总和
信息素增量和
M. Dorigo提出了3种蚁群算法的模型，其中上式称为ant-cycle模型，另外两个模型分别称为ant-quantity模型和ant-density模型，其差别主要在于Δτ的表示方式，ant-cycle模型有更好的搜索性能，是因为使用了每一次周游的总长度来计算信息素的存量。信息素更新完成后，便可以开始新一代的路径搜索。

蚁群算法的流程

1. 参数初始化。令时间t=0和循环次数A=0，设置最大循环次数G,将m个蚂蚁置于n个元素(城市)上，令有向图上每条边( i,j)的初始化信息量τ=c，其中c表示常数，且初始时刻Δτ =0。
2. 循环次数N=N+1。
3. 蚂蚁的禁忌表索引号k=1。
4. 蚂蚁数目h=k+1.
5. 蚂蚁个体根据状态转移概率公式计算的概率选择元素并前进，j∈{J_k(i) }。
6. 修改禁忌表指针，即选择好之后将蚂蚁移动到新的元素，并把该元素移动到该蚂蚁个体的禁忌表中。
7. 若集合0中元素未遍历完，即k<m, 则跳转到第4步;否则执行第8步。
8. 记录本次最佳路线。
9. 更新每条路径上的信息量。
10. 若满足结束条件，即如果循环次数N≥G，则循环结束并输出程序优化结果:否则清空禁忌表并跳转到第2步。