算法的起源#

蚁群自组织行为的双桥实验，蚁群利用遗留在往来路径上的具有挥发性的信息素来进行通信和协调。

假设有一群蚂蚁，蚂蚁们从A点出发，随机选择路线ABD或ACD，这里路线ABD长度为9个时间单位而ACD的长度为18个时间单位。经过9个时间单位后，走ABD的蚂蚁到达终点，走ACD的蚂蚁刚好走到C点。

经过18个时间单位后，走ABD的蚂蚁到达终点后得到食物又返回了起点A，而走ACD的蚂蚁刚好走到D点。假设蚂蚁的在单位时间内释放的信息素是个固定量，这样一来，路线ABD上蚂蚁留下的信息素将是路线ACD上蚂蚁留下的信息素的两倍。很显然这有一个正反馈的过程，最终蚂蚁们都会被信息素较多的路线吸引，选择走ABD。

注意，并不是因为蚂蚁们知道哪条路线长就在哪条路上释放较少的信息素，蚂蚁单位时间释放的信息素是定值。

蚁群算法解决 TSP 问题#

上述蚁群觅食很好的体现出来了寻找食物时的最优路径选择问题，那么，借助这个思想，可以解决其他类似的优化问题。

作为蚁群算法的蚂蚁个体，其运动和通信的简单规则，需要包含以下几个方面：

• 搜索范围: 蚂蚁会以一定的搜索半径进行搜索

• 局部环境: 蚂蚁能感知周围环境的信息

• 觅食规则: 蚂蚁只在其能感知的范围内进行探索和信息素释放

• 移动规则: 蚂蚁会朝信息素最多的方向移动，并且，当周围没有信息素指引的时候，蚂蚁会按照自己原来运动的方向惯性地运动下去。如果蚂蚁发现有它已经经过的地点，则以较大概率进行避让。

• 避障规则: 在蚂蚁的移动方向上有障碍物存在时，蚂蚁会随机选择另一个方向，或者按照信息素的指引继续其觅食行为。

• 通信规则: 信息素，信息素的挥发和蚂蚁的释放是一个正反馈的过程，信息素的浓度越高，蚂蚁就越容易选择这条路径。

TSP 问题

TSP 问题是一种典型的组合优化问题。给定 $n$ 个城市的集合，TSP 问题目标是寻找一条只经过各城一次的且长度最短的闭合路径。

用蚁群算法可以很好的解决 TSP 问题。

解：

Algorithm 蚁群算法解决 TSP

典型的蚁群算法模板为

def ACO_MetaHeuristic():
    while not terminated:
        generateSolutions()
        daemonActions()     
        pheromoneUpdate()   # 更新信息素

信息素更新的三种设置#

有三种基本信息素更新模式：蚁密模型（Ant‑Density）、蚁量模型（Ant‑Quantity）和蚁周模型（Ant‑Cycle）。它们的主要区别在于信息素何时更新（每移动一步或完成整个周游后）以及更新量如何确定（常数、与边长成反比或与整条巡游长度成反比）。其中，蚁密和蚁量模型均为局部更新，前者只按常数沉积、后者根据边长沉积；而蚁周模型采用全局更新，在所有蚂蚁完成一次完整巡游后才统一沉积信息素

停滞现象#

停滞现象（Stagnation behavior）：当所有蚂蚁都选择相同的路径时，系统不再搜索更好的解。原因在于较好路径上的信息素远大于其他边上的，从而使所有蚂蚁都选择该路径。

因此参数 $\alpha$ 和 $\beta$ 的设置非常重要。

• $\alpha$ 越大，信息素的影响越大，容易导致停滞现象。$\alpha$ 取较大值时，意味着在选择路径时，路径上的信息素非常重要；当 $\alpha$ 取较小值时，变成随机的贪婪算法。
• $\beta$ 越大，启发式信息的影响越大，容易导致搜索过度局部化。

蚂蚁数量 $m \approx n$ 时，使用 ant-cycle 模型可以在最少迭代次数内找到最优解。

概述#

粒子群算法源于对鸟群捕食行为的研究。假设有一个区域，所有的鸟都不知道食物的位置，但是它们知道当前位置距离食物还有多远。PSO 算法把每个解看作一只鸟，称为 “粒子 (particle)“，所有的粒子都有一个适应值，每个粒子都有一个速度决定它们的飞翔方向和距离，粒子们追随当前最优粒子在解空间中的搜索。

算法流程#

初始化一群随机粒子，通过迭代找到最优值。在每次迭代过程中，粒子通过跟踪 “个体极值 ($pbest$)” 和 “全局极值 ($gbest$)” 来更新自己的位置。

假设在 $D$ 维搜索空间中，有 $m$ 个粒子，其中

• 第 $i$ 个粒子的位置矢量 $\mathbf{x}_i = [x_{i1}, x_{i2}, \dots, x_{iD}]$，
• 其飞行速度也是一个矢量，记为 $\mathbf{v}_i = [v_{i1}, v_{i2}, \dots, v_{iD}]$，
• 第 $i$ 个粒子搜索到最优的位置为 $\mathbf{p}_i = [p_{i1}, p_{i2}, \dots, p_{iD}]$，
• 整个粒子群搜索到的最优位置为 $\mathbf{p}_{gbest} = [p_{gbest1}, p_{gbest2}, \dots, p_{gbestD}]$

对于第 $i$ 个粒子，它的速度更新公式为

其中 $v_{id}(t+1)$ 表示第 $i$ 个粒子在第 $d$ 维上的新速度，$w$ 是惯性权重，控制粒子当前速度的影响，$c_1, c_2$ 是学习因子（加速常数），分别表示个体认知和群体协作的权重，$rand_1, rand_2$ 是在 $[0, 1]$ 范围内的随机数，增加随机性，$p_{id}$ 表示第 $i$ 个粒子在第 $d$ 维上的历史最优位置，$p_{gbest,d}$ 是全局最优位置在第 $d$ 维上的值，$x_{id}(t)$ 代表第 $i$ 个粒子在第 $d$ 维上的当前位置。

而位置更新公式为

其中，$x_{id}(t+1)$ 是第 $i$ 个粒子在第 $d$ 维上的新位置，$v_{id}(t+1)$ 是第 $i$ 个粒子在第 $d$ 维上的新速度。

Python 实现

import numpy as np
from tqdm import tqdm

class PSO:
    def __init__(self, n_particles, n_dim, options, bounds=None):
        self.n_particles = n_particles
        self.n_dim = n_dim
        self.bounds = bounds

        self.w = options['w']   # 惯性权重
        self.c1 = options['c1'] # 认知系数
        self.c2 = options['c2'] # 社会系数

    def _init_swarm(self):
        # 如果有边界，在边界范围内初始化
        if self.bounds:
            min_bound, max_bound = self.bounds
            self.pos = np.random.uniform(
                low=min_bound,
                high=max_bound,
                size=(self.n_particles, self.n_dim)
            )
        
            velocity_range = np.array(max_bound) - np.array(min_bound)
            self.velocity = np.random.uniform(
                low=-velocity_range,
                high=velocity_range,
                size=(self.n_particles, self.n_dim)
            ) * 0.1 # 初始速度限制在较小范围

        else:
            # 如果没有边界，使用标准初始化
            self.pos = np.random.uniform(
                low=-1,
                high=1,
                size=(self.n_particles, self.n_dim)
            )
            self.velocity = np.random.uniform(
                low=-0.1,
                high=0.1,
                size=(self.n_particles, self.n_dim)
            )

        # 初始化每个粒子个体的最佳位置和适应度
        self.pbest_pos = self.pos.copy()
        self.pbest_cost = np.full(self.n_particles, float('inf'))

        # 初始化全局最佳位置和适应度
        self.gbest_pos = np.zeros(self.n_dim)
        self.gbest_cost = float('inf')

        # 记录每次迭代的最佳适应度值
        self.cost_history = []
        self.pos_history = []

    def reset(self):
        # 重置粒子群到初始状态
        self._init_swarm()

    def optimize(self, objective_func, n_iters=100, verbose=False):
        self.reset()
        for i in tqdm(range(n_iters)):
            # 计算当前粒子群的适应度值
            curr_cost = np.array(objective_func(self.pos))

            # 更新个体最佳
            mask = curr_cost < self.pbest_cost
            self.pbest_pos[mask] = self.pos[mask].copy()    # 是矩阵
            self.pbest_cost[mask] = self.pbest_cost[mask]

            # 更新全局最佳
            min_cost_idx = np.argmin(curr_cost)
            if curr_cost[min_cost_idx] < self.gbest_cost:
                self.gbest_cost = curr_cost[min_cost_idx]
                self.gbest_pos = self.pos[min_cost_idx].copy()

            # 保存历史记录
            self.cost_history.append(self.gbest_cost)
            self.pos_history.append(self.gbest_pos.copy())

            if verbose and i % 10 == 0:
                print(f'Iteration {i}: Best cost = {self.gbest_cost}')

            # 更新速度和位置
            r1 = np.random.random((self.n_particles, self.n_dim))
            r2 = np.random.random((self.n_particles, self.n_dim))

            cognitive = self.c1 * r1 * (self.pbest_pos - self.pos)
            social = self.c2 * r2 * (self.gbest_pos - self.pos)

            self.velocity = self.w * self.velocity + cognitive + social
            self.pos = self.pos + self.velocity

            # 边界处理
            if self.bounds:
                min_bound, max_bound = self.bounds
                self.pos = np.clip(self.pos, min_bound, max_bound)

                # 对于撞到边界的粒子，将其速度反向
                out_of_bounds_lower = self.pos <= min_bound
                out_of_bounds_upper = self.pos >= max_bound
                self.velocity[out_of_bounds_lower | out_of_bounds_upper] *= -0.5
        return self.gbest_cost, self.gbest_pos

参数分析#

特点#

• 属于仿生算法
• 属于全局优化算法
• 属于随机搜索算法
• 隐含并行性
• 根据个体的适配信息进行搜索，因此不要求目标函数具有可微性、连续型等
• 对高维复杂问题，往往会遇到早熟收敛和收敛性差的缺点

改进#

变化的惯性权重：惯性权重随迭代次数的增加而减小

收敛因子模型：收敛因子模型引入了一个额外的收敛因子 $\chi$，用于调整速度更新公式。速度更新公式变为

其中，收敛因子 $\chi = \frac{2}{\lvert 2 - \phi - \sqrt{\phi^2 - 4\phi} \rvert}, \quad \phi = c_1 + c_2, \quad \phi > 4$

应用#

• 神经网络训练：不需要使用梯度信息，多属性情况下训练结果优于 BP 算法，且训练速度非常快（但是高维空间中效果不好，因此不流行）
• 模糊控制、机器人路径规划等
• 组合优化

PSO 求解 TSP 问题#