1. 蚁群算法

蚁群算法基本概念介绍及名词解释请见上一篇博文：智能算法-蚁群算法（1）

故事性简单理解：一群蚂蚁想寻找食物。在讨论下，它们决定分头去寻找食物，为每只蚂蚁随机选择出发地，规定每只蚂蚁爬行速度相同，并且每只蚂蚁在爬过的地方会释放信息素，信息素会随着时间逐渐挥发，残留在地上的浓度会越来越低。之后的蚂蚁会更倾向于去探索信息素残留浓度高的那条路，因为这说明上一只蚂蚁爬过这条路找到当前最优解所用的时间短，也就是这条路的距离更短。以这样的方式，不断重复，最终找到最优解。

2. 示例详解

2.1 问题阐述

以蚁群算法解决旅行商问题（TSP）举例。旅行商问题，即从一个城市出发，经过所有城市，最终再回到出发城市，请找到最短的路径的方案。四个城市A、B、C、D之间的举例矩阵如下所示：

 规定：蚂蚁种群的规模 $m=3$，预先设置的参数𝛼＝1，预先设置的参数𝛽＝2，信息素的蒸发率 𝜌＝0.5

2.2 步骤一：初始化

首先使用贪婪算法得到路径$（ACDBA）$，则该初始路径所用的距离为 $Cnn=f(ACDBA)=1+2+4+3=10$

路径初始信息素浓度：

初始化所有边上的信息素: 𝜏𝑖𝑗=𝜏0

2.3 步骤二：为每只蚂蚁选择探索路径

2.3.1 选择每只蚂蚁初始出发城市

本题设定共有3只蚂蚁，为每只蚂蚁随机选择出发城市，假设蚂蚁1选择城市 $A$，蚂蚁2选择城市 $B$，蚂蚁3选择城市 $D$（此处出发城市选择是随机的，也可以使用其他方式来选择）。

2.3.2 选择下一个访问城市

为每只蚂蚁选择下一访问城市。以蚂蚁1为例，当前出发城市 $i=A$

可访问城市集合：$J1(i)$ = {$B$,$C$,$D$}

蚂蚁𝑘当前从城市 𝑖 出发,选择城市 𝑗 作为下一个访问对象的概率为： 

通过以上固定公式计算蚂蚁1选择B、C、D作为下一访问城市的概率：

用轮盘赌法则选择下一访问城市。假设产生的随机数 $q=random(0,1)=0.05<0.081$，则蚂蚁1将会选择城市 $B$ (此处使用的是轮盘赌选择方式，也可以使用其他选择方式，例如：直接选择概率最大的作为下一个访问城市)

用同样的方法为蚂蚁2和3选择下一访问城市，假设蚂蚁2选择城市 $D$，蚂蚁3选择城市 $A$

2.3.3 继续选择下一个访问城市

当前蚂蚁1所在城市 $B$，路径记忆向量 $R1=(AB)$，可访问城市集合$J2(i)$ = {$C$,$D$}。

计算蚂蚁1选择 $C$, $D$ 作为下一城市的概率：

 同样使用轮盘赌选择策略选择下一访问城市。假设产生的随机数 $q=random(0,1)=0.67$，则蚂蚁1将会选择城市 $D$。

用同样的方法为蚂蚁2和3选择下一访问城市，假设蚂蚁2选择城市 $C$，蚂蚁3选择城市 $D$。

2.3.4 构造出三只蚂蚁的完整路径

此时三只蚂蚁第一次探索的路径已经构造完毕:

• 蚂蚁1构建的路径为 $(\ast \ast AB\ast \ast CDA)$
• 蚂蚁2构建的路径为 $(BDC\ast \ast AB\ast \ast )$
• 蚂蚁3构建的路径为 $(DACBD)$

2.4 步骤三：信息素更新

计算每只蚂蚁构建的路径长度：

• 蚂蚁1的路径长度：$C1=3+4+2+1=10$
• 蚂蚁2的路径长度：$C2=4+2+1+3=10$
• 蚂蚁3的路径长度：$C3=2+1+5+4=12$

更新每条边上的信息素：初始路径上挥发剩下的信息素+3只蚂蚁刚走过的信息素  注：$（1/10+1/10）$是因为3只蚂蚁中有两只蚂蚁经过了AB路径，$（1/12）$是因为3只蚂蚁有一只经过了AC路径。

2.5 步骤四：循环迭代

如果满足约束条件（算法循环结束条件），则输出全局最优结果并结束程序，否则，转向步骤2.3.1继续执行。