蚁群算法

维基百科

蚁群算法(Ant Colony Optimization, ACO)，又称蚂蚁算法，是一种用来在图中寻找优化路径的几率型算法。它由Macro Dorigo 与1992年的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。蚁群算法是这一种模拟进化算法，初步的研究表明该算法具有许多优良的性质。

自然界中，蚂蚁的食物总是随机散布于蚁巢周围。仔细观察就会发现，经过一段时间后，蚂蚁总能找到一条从蚁巢到食物源的最短路径。

主要原理：蚂蚁在一开始时，会以相同的概率选择路线，在运动过程中，能够在其经过的路径上留下信息素，而且能感知这种物质的存在以及强度，并以此指导自己的运动方向，蚂蚁倾向于往信息素浓度高的方向移动。在相等时间内，较短路径上的信息量就遗留的比较多，则选择较短路径的蚂蚁也随之增多。蚂蚁群体行为表现出了一种信息正反馈现象，即某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大，蚂蚁个体之间就是通过这种信息交流机制来搜索食物，并最终沿着最短路径行进。

蚁群算法模型的建立

• 蚂蚁个体的抽象
• 问题空间的描述
• 寻找路径的抽象
• 信息素挥发的抽象
• 启发因子的引入

蚁群算法解决TSP(Travelling Salesman Problem)

假设n为城市规模，$i$和$j$为任意两个城市，$d_{ij}$表示城市之间的距离，$b_i(t)$表示t时刻在城市$i$蚂蚁的数量，则$m={\sum }_{i=1}^n{b}_i(t)$表示蚂蚁的总数量。在遍历过程中，把蚂蚁经过一个城市称为一次迭代，遍历n个城市需要n次迭代(每只蚂蚁下次总是走之前没走过的城市，有个禁忌表记录走过的城市)。蚂蚁系统采用${\tau }_{ij}(t)$来模仿$t$时刻路径$i$到$j$上面的信息素残留量。类似于蚂蚁觅食过程，每条路径上面的信息素会挥发，如果有蚂蚁经过的时候，信息素的浓度会相应的增加。因此，蚂蚁系统中的信息素浓度的更新公式为：
$${\tau }_{ij}(t+n)=\rho \cdot {\tau }_{ij}(t)+\Delta {\tau }_{ij}$$
式中，$\rho$是一个0到1的数字，(1-$\rho$)为挥发因子。另外，$\Delta {\tau }_{ij}$表示一次旅行（遍历所有城市）后，所有路径$i$到$j$的蚂蚁留下的信息素的总量，即：
$$\Delta {\tau }_{ij}=\sum _{k=1}^m\Delta {\tau }_{ij}^k$$
式中，$\Delta {\tau }_{ij}^k$表示第k只蚂蚁在路径$i$到$j$上面留下的信息素量。如果第k只蚂蚁经过路径$i$到$j$，则
$$\Delta {\tau }_{ij}=Q/L_k$$
式中，Q为一个常数，$L_k$为蚂蚁已经走过路径的总长度。否则，第K只蚂蚁在$i$到$j$上面留下来的信息量为0。
然后就是启发因子的引入，${\eta }_{ij}=1/d_{ij}$。通过结合信息素和启发因子，可以得到蚂蚁选择路径$i$到$j$的概率为：
$$p_{ij}^k(t)=\{\begin{array}{ll}\frac{[{\tau }_{ij}(t){]}^{\alpha }[{\eta }_{ij}{]}^{\beta }}{{\sum }_{k\in allowed}[{\tau }_{ik}(t){]}^{\alpha }[{\eta }_{ik}{]}^{\beta }}& j\in allowe{d}_k\\ 0& else\end{array}$$
式中$\alpha$和$\beta$是调节因子，调节${\tau }_{ij}(t)$和${\eta }_{ij}$的作用大小。$allowe{d}_k$表示蚂蚁k还没有走过的路径。所以如果信息浓度${\tau }_{ij}(t)$越大、路径长度越短（对应${\eta }_{ij}$越大），则路径被选择的概率就越大
求解TSP问题的蚁群算法中的人工蚂蚁具有以下特点：

1. 他们概率性地选择下一条路径，该概率与路径长度和路径上的信息素浓度有关；
2. 为了保证解的逻辑可行，蚂蚁不允许选择已经走过的路径（通过禁忌表实现）；
3. 蚂蚁走过一条路径时会在该路径上面分泌一种叫做信息素的物质。

蚁群算法求解TSP问题的直观理解就是：

1. m只蚂蚁遍历禁忌表Tabu（mxn）分别走遍n个城市，称为一次迭代
2. 每只蚂蚁根据信息素浓度和启发式因子计算概率p来选择下一座城市
3. 禁忌表Tabu（mxn）经过一次迭代就更新一次
4. 信息素浓度Tau（nxn）经过一次迭代就更新一次

最大最小蚁群算法

最大最小蚁群算法与普通蚁群算法区别不大，主要是每条路径上的信息素浓度都有个最大值最小值，每次更新都保证信息素浓度在[min,max]区间范围内。最小信息素能增加对最优解探索的可能性(exploration)，而最大信息素浓度保证经验对于蚂蚁的启发性(exploitation)。
每次都蒸发，但是每次蒸发后只有最优路径上的信息素会增加。这样的收敛速度会更快

参考

1. https://zh.wikipedia.org/wiki/%E8%9A%81%E7%BE%A4%E7%AE%97%E6%B3%95
2. 段海滨. 蚁群算法原理及其应用[M]. 科学出版社, 2005.
3. https://zhuanlan.zhihu.com/p/95782157
4. https://blog.csdn.net/acsunqi/article/details/76060669