C6 群体智能

核心思路：大自然中的一些社会系统尽管由简单的个体组成，却表现出智能的集体行为。称 Agents 为“智能体”。

对问题的智能解决方案，自然地涌现于这些个体的自组织和交流之中。整个系统的行为是自下而上的，遵循简单规则的简单 Agents 生成复杂的结构/行为，且 Agents 不遵循某个领导者的命令。

通信特征：不能全局交换信息，只能局部交换信息。

基本概念

Boid Rules

分离（Separation）
- 避免与邻近同伴太接近。这条规则使得每个个体避免与附近的其他个体碰撞，维持一定的距离。
对齐（Alignment）:
- 与邻近同伴保持相同的移动方向。个体会调整自己的方向和速度，以匹配周围个体的平均方向和速度。
聚集（Cohesion）:
- 向邻近同伴的平均位置移动。这使得个体趋向于向群体的中心移动，促进群体的聚集。

基本构成

Agents 智能体
- Interact with the world and with each other (either directly or indirectly)
Simple behaviours 简单的行为
- e.g. ants, termites, bees, wasps
Communication 通信
- How agents interact with each other. e.g. pheromones of ants

总结来看，个体 Agents 的简单行为 + Agents 群体之间的通信 = 群体 Agents 的复杂涌现行为。

基本特点

分布式，没有中央控制或数据源 Distributed, no central control or data source。
有限的通信。Limited communication。
没有（显式的）环境模型。No (explicit) model of the environment。
对环境存在感知。Perception of environment (sensing)。
对环境变化做出反应的能力。Ability to react to environment changes。

往往采取如下思路来抽象出一种算法来：

通信 Communication

基本的通信思路

计算机通信

在计算机科学中，通信可以通过共享内存或消息传递来实现。共享内存涉及多个处理单元共享相同的内存空间，而消息传递则涉及通过发送和接收消息进行通信。

群体智能中的通信

在群体智能系统中，通信不仅仅是简单的信息传递，而是意味着相互作用。环境提供了一个计算基础设施，其中 Agents 之间发生相互作用。这个基础设施包括 Agents 之间通信的协议以及 Agents 相互作用的协议。

低级通信

涉及简单信号和痕迹的传递，通常是一些基本的信息传递形式。

高级通信

涉及认知 Agents ，通常被视为有意图的系统，更复杂，更灵活。

直接通信 vs. 间接通信

直接通信是指 Agents 之间直接的信息传递，而间接通信可能涉及其他媒介或者通过环境中介来实现。

间接通信

类似 Share Memory 的形式。个体的消息均发送到 Blackboard。

直接通信

这一部分需要做到一个 Actor Language，每个 Actor 接收到一个消息后会做一系列动作。

Speech Acts

言语行为有三个方面：

Locution（言词）= 说话者的物理表达。
Illocution（言外之意）= 说话者的意图含义（履行性的）。
Prelocution（言后之果）= 由言词引起的动作。

也有不少模型在研究这个问题。shared languages，有 KIF, KQML, DAML。service models 的 DAML-S 等。

蚁群算法 ACO

Ant Colony Optimization。基于间接通信和信息素。

简单来说，一只孤立的蚂蚁会随机移动，但当它发现信息素踪迹时，这只蚂蚁很可能会决定跟随该踪迹。这个概率取决于信息素的浓度。

同时，一只寻找食物的蚂蚁会在其路线上沉积信息素。当它找到食物来源（目标）时，它会返回巢穴以加强其踪迹。因此，其他蚂蚁更有可能开始追踪这条踪迹，从而在其上释放更多的信息素。蚂蚁在每条走过的路径上都会留下信息素。如果一条路径比另一条短，那么蚂蚁会更快地在这条路径上往返，并且因此在较短的时间内留下更多的信息素。

这个过程就像一个正反馈循环系统，因为路径上的信息素强度越高，蚂蚁开始穿过它的可能性就越高。

解决 TSP 问题

设第 \(k\) 只蚂蚁在 \(t\) 时刻位于点 \(i\) 上，那么它会等概率地向邻居走：

\[\begin{aligned} p_{i j}^k(t)& = \begin{cases}\frac{\left[\tau_{i j}(t)\right]^\alpha\left[\eta_{i j}(t)\right]^\beta}{\sum_{l \in N_i^k(t)}\left[\tau_{i l}(t)\right]^\alpha\left[\eta_{i l}(t)\right]^\beta}, & j \in N_i^k(t) \\ 0, & j \notin N_i^k(t)\end{cases}\\ \tau_{i j}(t+1)& =(1-\rho) \cdot \tau_{i j}(t)+\Delta \tau_{i j}(t) \\ \Delta \tau_{i j}(t)& =\sum_{k=1}^m \Delta \tau_{i j}^k(t) \\ \Delta \tau_{i j}^k(t)& = \begin{cases}Q / L^k, \text { 第 } k \text { 只蚂蚁在本次遍历中经过路径 } c_i-c_j \\ 0, \text { 其他 }\end{cases} \end{aligned} \]

其中 Q 是信息素总量，L 是总的路径的长度。这个的意思是，我们每次加信息素是以路径为单位加的（从起点回到起点，TSP）。

另外，\(\tau_{ij}\) 是 \(i \to j\) 这条边的信息素，\(\eta_{i j}\) 可以是边权也可以是某种启发式的长度，\(p_{ij}\) 是走 \(i\to j\) 的概率，上角标 \(k\) 表示第 \(k\) 只蚂蚁，\(N_i\) 是 \(i\) 的邻居集合。

大概就这样：

解决 JSSP 问题

Btw，蚁群算法也可以来解决 Job Shop Scheduling (JSSP)，即作业车间调度问题。

转化成图问题即可：

这样一来就还是 TSP 问题了。

一些扩展

接下来是一些基于启发式思路的优化。

1. Elitist Strategy for Ant Systems (EAS)

EAS 特别强调了最佳解决方案的重要性。在EAS中，不仅是所有蚂蚁在其路径上留下信息素，而且历史上找到的最佳路径会获得额外的信息素强化。这意味着最佳路径上的信息素浓度会比其他路径更高，从而更有可能被后续的蚂蚁选择。

特点:

强化历史最佳路径。
加速向最优解的收敛。
增加了算法对于最佳解的搜索强度。

2. Rank-based Ant System (ASRank)

ASRank 根据蚂蚁找到的路径质量对蚂蚁进行排名。在这个系统中，只有排名靠前的蚂蚁（例如，最好的几条路径）被允许在其路径上留下信息素。这样，信息素的更新更加集中于高质量的解决方案。

特点:

排名制度减少了信息素的过度分散。
专注于更有效的路径。
提高了算法的收敛速度和解决方案的质量。

3. MAX-MIN Ant System (MMAS)

MMAS 是一种特别设计来避免过早收敛和探索解空间边界的 ACO 方法。因为 ACO 本身追求快速收敛。在 MMAS 中，信息素的浓度被限制在一个最大值和一个最小值之间。这种限制防止了任何一条路径变得过于“显著”，从而保持了算法的探索能力。相当于是有上下界的蚁群算法。

特点:

信息素浓度有上下限制。
避免过早收敛和探索的不足。
保持了算法的多样性和探索能力。

4. Ant Colony System (ACS)

ACS 是 ACO 的一个高效版本，它引入了局部信息素更新规则和更强的全局更新规则。在 ACS 中，蚂蚁在构建路径时进行局部信息素更新，减少了当前路径上的信息素浓度，鼓励其他蚂蚁探索新路径。而全局更新只由生成最优解的蚂蚁执行，强化了最优路径。

特点:

结合局部和全局信息素更新机制。
强化最优解，同时保持探索新路径的激励。
在快速收敛和多样性探索之间取得了良好的平衡。

粒子群算法 Particle Swarm Optimization (PSO)

PSO 的优先：简单高效。

参考鸟群的模式，“群体”被定义为移动个体的明显无组织的集合（群体）。这些个体倾向于聚集在一起，而每个个体似乎都在随机方向移动。而群体行为的同步性被认为是鸟类努力保持自己与邻居之间最佳距离的函数（避免碰撞，但方向和目标仍和群体一致）。而一个体的移动，往往是根据邻居的移动轨迹来的。

具体而言，是可以在搜索过程中，某个粒子搜索到了较优的路径，即可以把这个路径通信给其他粒子。

基本流程

1. 群体初始化

在PSO中，解决方案的候选群体（称为“粒子”）通过随机分配位置和速度来初始化。这些粒子在问题的解空间中移动，解空间可以被想象为一个高维的“超空间”。
每个粒子代表了解空间中的一个潜在解决方案，其位置代表了解决方案的候选点。

** 2. 个体历史最佳（pBest）、全局最佳（gBest）和局部最佳（lBest）**

每个粒子都会跟踪它在超空间中遇到的“最佳”位置，即它所找到的具有最高适应度（或最优解）的位置。
“pBest”（personal best），代表了个体粒子在迄今为止的搜索过程中的最佳成就。
“gBest”（global best）是整个粒子群中找到的最优解。
在某些 PSO 变体中，还会使用“lBest”（local best），它代表了粒子在一个定义好的邻域内找到的最佳解。

3. 随机加速和移动

在每个时间步，粒子会根据自己的 pBest 和 gBest（或 lBest）的位置来随机地调整其速度和方向。这意味着粒子会“飞向”它自己的最佳位置和整个群体的最佳位置。
这种行为模仿了鸟群或鱼群的社会行为，其中个体通过观察和模仿其他个体来改进自己的行为。

细节

\[\begin{aligned} &v_{i k}^{t+1}=\omega v_{i k}^t+c_1 \xi\left(p_{i k}^t-x_{i k}^t\right)+c_2 \eta\left(p_{g k}^t-x_{i k}^t\right), k=1,2, \cdots, d\\ &x_{i k}^{t+1}=x_{i k}^t+v_{i k}^{t+1}, k=1,2, \cdots, d \end{aligned} \]

关心的实际上是位置和速度。\(k\) 表示的是维度，\(i\) 表示当前粒子，\(t\) 表示当前时间。\(\left(p_{i k}^t-x_{i k}^t\right)\) 是当前位置离 IBest 的距离，\(\left(p_{g k}^t-x_{i k}^t\right)\) 是当前位置和 gBest 的距离。

另外，\(c_1\) 和 \(c_2\) 是 \(>0\) 的参数，\(\eta\) 和 \(\xi\) 是随机函数，\(w\) 是某种惯性权重。这些都是可调的。