群智能（Swarm intelligence）

自然界动物群，称之为群。

群的特征：

相互作用的相邻个体的集合
个体的行为简单，既有竞争又有协作
智能化的集体行为（1+1>2）：
- 个体间不仅能够交互信息，还能够处理信息，根据信息改变自身行为
- 没有一个集中控制中心，分布式、自组织
- 作为群体协同工作时，展现出非常复杂的行为特征——智能

任何一种由昆虫群体或其他动物社会行为机制而激发设计出的算法或分布式解决问题的策略都属于群智能算法

典型算法：

粒子群 PSO
蚁群 ACO
人工鱼群 AFSA
人工蜂群 ABCA

算法原理：蚁群觅食

模拟自然界蚁群觅食（从巢穴到食物的最佳路径的行为）的过程。

自然界中，蚂蚁会在觅食路上留下”信息素“来作为前往食物所在地的标记。
信息素会逐渐挥发，蚂蚁倾向于沿着”信息素“浓度更高的路径前往食物所在地。
信息素浓度更高的路径上蚂蚁会更多
最后，几乎所有蚂蚁会选择更短的路径

算法步骤

TSP 问题示例

路径构建/构造解空间

对每只蚂蚁选择下一个城市，直到遍历所有的城市

蚂蚁 \(k\) 从城市 \(i\) 到城市 \(j\) 的概率为：

\[p_{ij}^k = \begin{cases} \frac{\tau_{ij}^\alpha (t)* \eta_{ij}^\beta}{\sum_{s \in \phi_k} \tau_{is}^\alpha (t)* \eta^{\beta}_{is}},& j \in \phi_k \\ 0,& otherwise \end{cases} \]

\(i, j\) 分别为起点和终点
\(\eta_{ij} = 1 / d_{ij}\) 为能见度，是两点 \(i, j\) 距离的倒数
\(\tau_{ij}(t)\) 为时间 \(t\) 时由 \(i\) 到 \(j\) 的信息素强度
\(\phi_k\) 为尚未访问过的节点集合
- 这个尚未访问过的节点集合是什么意思？每只蚂蚁需要存储自己去过哪些城市，直到它走过了所有城市。
\(\alpha, \beta\) 为两个常数，分别是信息素和能见度的加权值。

更新信息素浓度

更新各城市间信息素浓度

更新各城市间信息素浓度
\(t+1\) 次循环，城市 \(i, j\) 之间的信息素浓度为：\(\tau_{ij}(t+1) = \tau_{ij}(t) * (1- \rho) + \Delta \tau_{ij}(t), 0 < \rho < 1 \\ \Delta \tau_{ij}(t) = \sum_{k=1}^m \Delta \tau_{ij}^k(t)\)
\(\Delta \tau_{ij}^k(t)\) 为 t 次循环，蚂蚁 k 在 \((i,j)\) 路径上留下的信息素
\(\Delta \tau_{ij}(t)\) 为 t 次循环，\((i,j)\) 路径上新增的信息素
\(\rho\) 为信息素挥发常数

计算新增信息素浓度

蚁密模型（Ant-Density）：\(\Delta \tau_{ij}^k(t) = \begin{cases} Q,& if (i, j) \in \psi_k(t) \\ 0,& otherwise \end{cases}\)
蚁量模型（Ant-Quantity）：\(\Delta \tau_{ij}^k(t) = \begin{cases} \frac{Q}{d_{ij}},& if (i, j) \in \psi_k(t) \\ 0,& otherwise \end{cases}\)
蚁周模型（Ant-Cycle）：\(\Delta \tau_{ij}^k(t) = \begin{cases} \frac{Q}{L_k(t)},& if (i, j) \in \psi_k(t) \\ 0,& otherwise \end{cases}\)
Q 是信息素常量
\(L_k(t)\) 是第 \(t\) 次循环，蚂蚁 \(k\) 遍历所有城市的总路径长度
\(\psi_k(t)\) 是第 \(t\) 次循环，蚂蚁 \(k\) 遍历所有城市的路径集合