局部最优粒子群优化（LBPSO）

名称

局部最优粒子群优化（Local Best Particle Swarm Optimization, LBPSO），又称：

• Lbest 粒子群优化
• 局部最优 PSO
• 局部邻域粒子群优化

分类

查看分类思维导图

局部最优粒子群优化是粒子群优化算法的一种变体，属于群体智能领域，而群体智能又是计算智能的一个分支。

• 计算智能
  • 群体智能
    • 粒子群优化（PSO）
      • 局部最优粒子群优化（LBPSO）

策略

局部最优粒子群优化算法是在标准 PSO 基础上的一种扩展，其核心在于引入局部邻域拓扑来引导搜索过程。在 LBPSO 中，每个粒子并非像原始 PSO 那样直接受整个种群全局最优位置的影响，而是只与粒子群中的一个子集相连，从而形成局部邻域。

局部邻域拓扑

局部邻域拓扑定义了粒子群中粒子之间的连接关系。常见拓扑包括环形拓扑（ring topology），即每个粒子与其最近的 $k$ 个邻居相连；以及 von Neumann 拓扑，即将粒子排列成网格结构，并使每个粒子与其相邻粒子连接。

拓扑结构的选择会影响粒子群中的信息传播方式，以及探索与开发之间的平衡。局部邻域机制使粒子能够更充分地搜索其邻近区域，同时削弱全局最优位置的过强牵引作用，因此通常能够提升种群多样性，并在多峰优化问题上获得更好的性能。

位置与速度更新

与标准 PSO 类似，LBPSO 仍以迭代方式更新每个粒子的位置和速度。但不同之处在于，LBPSO 不再利用全局最优位置来指导搜索，而是使用粒子所在局部邻域中发现的最优位置（lbest）作为引导信息。

速度更新公式同时包含粒子的个体最优位置（pbest）和其局部邻域最优位置（lbest）。随后，再根据更新后的速度计算粒子在搜索空间中的新位置。

收敛与终止

LBPSO 会持续迭代，直到满足给定的终止准则，例如达到最大迭代次数，或找到质量足够高的解。与全局最优 PSO 相比，由于信息是在局部连接中逐步传播的，LBPSO 的收敛速度通常较慢。然而，这种较慢的收敛过程有助于维持种群多样性，并降低过早收敛到次优解的风险。

过程

数据结构

• 粒子（Particle）：表示搜索空间中的一个候选解，包含：
  • 位置（Position）：粒子在搜索空间中的当前位置
  • 速度（Velocity）：决定粒子运动方向和步长的速度向量
  • 个体最优（Personal Best, pbest）：粒子迄今为止找到的最优位置
• 粒子群（Swarm）：由多个粒子组成的集合，其中每个粒子依据所选拓扑与其局部邻域相连接

参数

• 种群规模（Population Size）：粒子群中的粒子数量
• 维度（Dimension）：搜索空间的维数
• 惯性权重（Inertia Weight, $w$）：控制前一时刻速度对当前速度影响程度的参数
• 认知系数（Cognitive Coefficient, $c_1$）：决定粒子向其个体最优位置靠拢程度的参数
• 社会系数（Social Coefficient, $c_2$）：决定粒子向其局部邻域最优位置靠拢程度的参数
• 最大速度（Maximum Velocity, $v_{max}$）：用于限制粒子最大速度，防止其发生过度振荡
• 邻域规模（Neighborhood Size, $k$）：局部拓扑中每个粒子所连接的邻居数量

伪代码

1. 初始化粒子群
   1. 对粒子群中的每个粒子：
      1. 随机初始化粒子的位置和速度
      2. 计算粒子当前位置的适应度
      3. 将粒子当前的位置设为其个体最优位置（pbest）
   2. 根据所选择的邻域拓扑，为每个粒子确定其局部最优位置（lbest）
2. 当终止条件未满足时：
   1. 对粒子群中的每个粒子：
      1. 利用速度更新公式更新粒子速度：
         1. $v = w \cdot v + c_1 \cdot rand() \cdot (pbest - position) + c_2 \cdot rand() \cdot (lbest - position)$
      2. 利用位置更新公式更新粒子位置：
         1. $position = position + v$
      3. 计算粒子新位置的适应度
      4. 若新位置优于粒子的个体最优位置（pbest）：
         1. 更新粒子的个体最优位置（pbest）
   2. 根据新的位置与适应度值，为每个粒子更新其局部最优位置（lbest）
3. 返回粒子群找到的最优解

注意事项

优点

• 探索能力更强：局部邻域拓扑使粒子能够更充分地探索其邻域区域，从而有助于更全面地覆盖搜索空间，并降低早熟收敛风险。
• 多样性更高：由于削弱了全局最优位置的统一牵引作用，LBPSO 能够维持更高水平的种群多样性，这对于多峰问题以及避免陷入局部最优尤为有利。
• 鲁棒性较好：与全局最优 PSO 相比，LBPSO 对初始条件和参数设置通常不那么敏感，因而具有更好的鲁棒性。

缺点

• 收敛速度较慢：局部邻域拓扑会减缓信息在粒子群中的传播速度，因此通常需要更多迭代次数才能达到满意解。
• 计算复杂度更高：维护和更新局部邻域拓扑会带来额外的计算开销，尤其是在粒子规模较大或拓扑较复杂时更为明显。
• 参数敏感性：LBPSO 的性能对邻域拓扑类型及邻域规模的选择较为敏感，因此在不同问题上往往需要仔细调参。

启发式建议

邻域拓扑选择

• 对于局部最优数量较少的问题，可采用环形拓扑，因为它能够在探索与开发之间提供较为均衡的折中。
• 对于局部最优数量较多的问题，或需要更充分局部搜索的情形，可考虑采用 von Neumann 拓扑。
• 应尝试不同的邻域规模（$k$），以寻找局部信息共享与全局信息传播之间的最佳平衡。较小的邻域更有利于局部探索，而较大的邻域会增强全局优良信息的传播作用。

参数调节

• 惯性权重（$w$）通常可设为 0.5 到 0.9 之间，以平衡前一时刻速度与当前吸引力之间的作用。较大的取值更偏向探索，较小的取值更偏向开发。
• 认知系数（$c_1$）和社会系数（$c_2$）应根据问题特征进行调整。较大的认知系数会鼓励粒子更多探索其自身历史最优区域，而较大的社会系数则会促使粒子更积极地向局部邻域最优位置移动。
• 最大速度（$v_{max}$）通常可限制为搜索空间范围的一定比例（例如 10%–20%），以避免粒子跨越最优区域并产生过度振荡。

种群规模与迭代次数

• 可先将种群规模设置为 20–50 个粒子，再根据问题复杂度和维度进行调整。较大的种群能够更充分地搜索空间，但也可能需要更多迭代次数才能收敛。
• 最大迭代次数应依据可用计算资源和期望解质量来设定，并可结合实际收敛行为动态调整。

混合策略

• 可考虑将 LBPSO 与其他方法结合使用，例如局部搜索技术或进化算子，以进一步提升算法性能。例如，对 LBPSO 找到的优良解施加局部搜索过程，有助于细化结果并跳出局部最优。
• 还可尝试采用自适应或自适应演化策略，根据搜索进程和种群多样性动态调整 LBPSO 的参数，从而增强算法在不同阶段的适应能力。