基于种群的增量学习（PBIL）

名称

基于种群的增量学习（Population-Based Incremental Learning, PBIL）

分类

查看分类思维导图

基于种群的增量学习是一种进化计算（Evolutionary Computation）方法，而进化计算是计算智能（Computational Intelligence）的一个分支。PBIL 与遗传算法（Genetic Algorithms）以及分布估计算法（Estimation of Distribution Algorithms, EDAs）关系密切。

• 计算智能
  • 进化计算
    • 进化算法
      • 遗传算法
      • 分布估计算法
        • 基于种群的增量学习

策略

概率模型

基于种群的增量学习维护一个关于解空间的概率模型，该模型通常表示为一个概率向量。该向量描述了解中每个变量取某一特定值的概率。算法通过从这一概率分布中采样来生成新的候选解。

种群采样与评估

PBIL 通过对概率模型进行采样来生成一组候选解种群。随后，利用适应度函数对每个候选解进行评估，以衡量其在求解给定问题时的质量或性能。候选解的适应度值将用于指导概率模型的更新。

概率模型更新

概率模型依据候选解的适应度值进行更新。更新过程通过调整概率向量中的各元素，提高后续迭代中生成高质量解的可能性。通常，这一更新是通过将概率逐步朝向表现最优候选解的取值方向移动来实现的。

迭代与收敛

候选解的采样、适应度评估以及概率模型更新过程会不断重复，直到达到预设的迭代次数或满足收敛判据。随着迭代推进，概率模型会逐渐向解空间中更有前景的区域集中，从而提高生成高质量解的概率。

流程

数据结构：

• 概率向量：表示解空间概率模型的向量。向量中的每个元素对应解中的一个变量，用于描述该变量取某一特定值的概率。
• 种群：由从概率向量中采样生成的一组候选解构成。

参数：

• 种群规模：每次迭代中生成的候选解数量。
• 学习率：依据表现最优候选解更新概率模型时所采用的更新速率。
• 变异概率：对概率向量施加变异的概率，用于维持种群多样性并探索解空间中的新区域。

流程：

1. 将概率向量初始化为各变量取值等概率分布。
2. 重复以下过程，直到达到预设迭代次数或满足收敛条件：
   1. 通过对概率向量进行采样生成一组候选解种群。
   2. 利用适应度函数评估每个候选解的适应度值。
   3. 根据适应度值选出表现最优的候选解。
   4. 根据所选候选解更新概率向量：
      1. 对于解中的每个变量：
         1. 计算所选候选解中该变量取某一特定值的比例。
         2. 利用学习率将概率向量中对应的概率值朝该比例方向更新。
   5. 对概率向量施加变异：
      1. 对于概率向量中的每个元素：
         1. 以等于变异概率的概率，用一个较小的随机扰动修改该元素。
3. 返回迭代过程中找到的最优候选解。

注意事项

优点：

• 与传统遗传算法相比，PBIL 无需在解种群上显式执行交叉、变异等遗传操作，因此计算效率较高。
• PBIL 中的概率模型为解空间提供了一种紧凑表示，从而有利于高效采样与搜索。
• PBIL 适用于高维搜索空间问题，并能够在一定程度上反映变量之间的依赖关系。

缺点：

• 当概率模型过度集中于解空间中的某一区域时，PBIL 可能出现早熟收敛，导致种群多样性下降，并可能错失全局最优解。
• PBIL 的性能对学习率和变异概率等参数较为敏感，因此通常需要针对具体问题进行细致调节。
• 对于具有复杂多峰适应度景观或欺骗性最优解的问题，PBIL 可能表现不佳，因为其概率模型未必能够充分捕捉跳出局部最优所需的信息。

启发式建议

种群规模

• 初始种群规模可设为不少于解空间变量个数的 10 倍。
• 对于搜索空间较大或适应度景观较复杂的问题，可适当增大种群规模，以保证足够的探索能力。
• 在算法后期，也可考虑适当减小种群规模，以便将搜索集中于更有前景的区域。

学习率

• 宜采用较小的学习率（如 0.1 或 0.05），以实现对概率模型的渐进式更新，并维持一定多样性。
• 较大的学习率能够加快收敛，但也更容易导致算法过早收敛到次优解。
• 可在搜索过程中自适应调整学习率，例如前期取较大值以增强探索，后期逐步减小以强化开发。

变异概率

• 变异概率通常可设为较小值（如 0.01 或 0.05），以便对概率模型引入轻微扰动。
• 较高的变异概率有助于跳出局部最优，但也可能降低收敛速度。
• 可根据问题复杂度以及探索与开发之间的平衡需求，对变异概率进行动态调整。

精英保留

• 可通过引入精英保留机制，在各轮迭代中始终保存迄今找到的最优候选解。
• 精英保留能够防止最优解在概率模型更新过程中丢失，并为后续搜索提供稳定参照。

终止准则

• 可根据可用计算资源和问题复杂度设定最大迭代次数。
• 可持续监测若干轮迭代内最优适应度值的改进情况；若长期无显著提升，则可提前终止算法。
• 若事先已知目标适应度水平，也可将其作为终止条件之一。

问题相关考虑

• 应结合具体问题结构，分析变量之间可能存在的依赖关系或相关性，并尽量在概率模型中加以利用。
• 可将领域知识或问题特定启发信息融入概率模型的初始化与更新过程。
• 可尝试不同的候选解表示方式以及概率向量编码形式，以寻找更适合具体问题的解表示方法。