Python 蚁群算法的理解

智慧可能体现在个体，也可能体现在群体
四大算法简单过了3 个，剩下一个蚁群算法个人平时用不着，所以就简单记一点点想法吧

信息素

Pheromone，单个蚂蚁的智力是有限的，但是蚂蚁觅食时可以通过信息素来交流并强化个体的经验，以至于整个群体看起来就具有了智慧一样。

探索与记忆

蚂蚁在走过的路径上会留下信息素，于是后来的蚂蚁更倾向于沿着信息素浓度高的方向前进，于是某一条路径便会不断加强，不论该路径是不是正确的。然而正如上面说的，蚂蚁的选择是一个概率问题，所以总是会有少部分蚂蚁会选择信息素较少，或者没有信息素的方向前进，如此，整个种群开始的行进路径应当是类似于树状的搜索过程。

在$t$ 时刻，每一只蚂蚁从$i$ 位置有一定概率跑到下一个位置$j$：

$$P^k_{ij}(t) = \begin{cases} \frac{\tau^\alpha_{ij}(t) \times \eta^\beta_{ij}(t)}{\sum\limits_{k \in K_{allow}}[\tau^\alpha_{ik}(t) \times \eta^\beta_{ik}(t)]} && k \in K_{allow} \\ 0 && k \notin K_{allow} \end{cases} \tag{1}$$

$(1)$式并不是标准形态，但是个人觉得这样更容易理解一些。其中：

• $P^k_{ij}(t)$ 表示某一只蚂蚁从点$i$ 转移到点$j$ 的概率
• $\tau$ 表示$i~j$ 这条路径上的信息素浓度
• $\eta$ 表示$i~j$ 这条路径上的$cost$，一般为距离的倒数
• $\alpha$ 表示信息素浓度对蚂蚁决策的影响
• $\beta$ 表示蚂蚁愿意寻求新的更短路径的意愿
• $K_{allow}$ 表示允许去的所有位置，例如还未到访过的城市，或者上下左右四个点的坐标等

那么单个蚂蚁有必要记住自己的路径吗？在旅行商问题中，这是必须的，应为要求蚂蚁不能重复经过两座城市，所以要记清楚自己已经经过了哪些城市。但是对于探索类的问题，则只需有短期的记忆即可，比如不要返回刚来的的道路。

而$i~j$ 路径上的信息素的更新则遵循以下原则：

$$\tau_{ij}(t) = (1-\rho)\tau_{ij}(t-1) + \Delta\tau_{ij} \tag{2}$$

其中$\rho$ 表示信息素的挥发速率，$\Delta\tau_{ij} = \sum\limits_{k=1}^{n}\Delta\tau_{ij_k}$ 表示所有在$i~j$ 路径上经过的蚂蚁释放的信息素的和

而算法中，蚂蚁释放信息素有以下三种策略：

$$\Delta\tau_{ij_k} = \begin{cases} \frac{Q}{L_k} && cycle-based \\ \frac{Q}{d_{ij}} && quantity-based \\ Q && density-based \end{cases} \tag{3}$$

分别对应路径密度、局部密度和常数密度，使用时可根据实际情况选择。

遗忘与挥发

信息素会随着时间挥发。如果一条路径少有蚂蚁经过，那么她就会慢慢被遗弃掉，这么看起来很像神经细胞的突触机制，用多了就形成永久的通道。

反馈与返程

理论上来说，蚂蚁找到食物后会返回巢穴，这一过程应该更能加强整个种群的学习速率；当然也可以设计当蚂蚁找到食物后就立刻返回巢穴，理论上也能够有不错的效果。而cycle-based 模型则与反馈机制有着异曲同工之妙。

实现

为了实现蚁群算法，我们肯定需要以下信息：

• 种群数量、迭代次数、挥发速率等各种参数
• 信息素浓度表：是一个二维对称矩阵
• $costs$表：同样是一个二维对称矩阵，用于表示路径的代价
• 蚂蚁位置表：蚂蚁的当前位置
• 每个蚂蚁自己的记忆，主要是历史路径，此数据可以是数组或者链表，长度也未必确定

整个算法的迭代是以时间为依据的，每一个时刻根据蚂蚁的位置更新上面的部分信息。所以对蚂蚁种群的遍历还是不可或缺的，在旅行商问题中兴许可以通过矩阵运算来加速也未可知。

通过面向对象的方法可能解释起来更形象，但是矩阵运算毫无疑问要更高效。