双变量边缘分布算法（BMDA）

名称

双变量边缘分布算法（Bivariate Marginal Distribution Algorithm, BMDA）

分类

查看分类思维导图

双变量边缘分布算法是一类分布估计算法（Estimation of Distribution Algorithm, EDA），隶属于进化计算领域，而进化计算又是计算智能的重要分支。EDA 与遗传算法、进化策略等其他进化算法密切相关。

• 计算智能
  • 进化计算
    • 进化算法
      • 遗传算法
      • 进化策略
      • 分布估计算法
        • 单变量边缘分布算法
        • 双变量边缘分布算法
        • 多变量边缘分布算法

策略

双变量边缘分布算法是一种优化技术，其核心思想是通过从候选解种群中估计双变量概率分布来学习优良解的概率模型。算法以迭代方式从所学习的模型中采样生成新的候选解，筛选其中表现较优的个体，并基于被选中的解更新概率模型。

BMDA 的关键在于刻画问题变量之间的两两依赖关系。通过对双变量边缘分布进行建模，BMDA 能够利用变量之间的相互作用，从而生成融合已选优良解中有利特征的新解。

概率建模

BMDA 为问题中的每一对变量估计一个双变量概率分布。这些双变量分布能够反映变量之间的成对依赖关系，使算法能够生成继承所选解中优良变量组合特征的新解。

采样与选择

在每一次迭代中，BMDA 根据已学习得到的双变量分布采样生成新的候选解种群。该采样过程能够组合上一轮被选中优良解中的有利特征。随后，算法对新解进行适应度评估，并依据适应度值选择其中表现最优的个体。

模型更新

在选出较优解之后，BMDA 基于这些被选中的解对双变量概率分布进行更新。更新过程会调整分布参数，从而提高下一轮生成与当前优良解相似解的概率。上述采样、选择与模型更新过程不断重复，直至满足终止条件。

流程

数据结构

• 种群：候选解的集合。
• 双变量分布：一组概率分布，其中每个分布对应问题中一对变量。

参数

• 种群规模：种群中候选解的数量。
• 选择规模：每轮迭代中被选中的解的数量。
• 最大迭代次数：允许执行的最大迭代次数。

步骤

1. 随机初始化候选解种群。
2. 计算种群中每个解的适应度值。
3. 当终止条件未满足时：
   1. 根据适应度值从种群中选择表现最优的解。
   2. 由所选解估计双变量概率分布。
   3. 根据双变量分布采样生成新的候选解种群。
   4. 评估每个新解的适应度。
   5. 用新种群替换旧种群。
4. 返回找到的最优解。

注意事项

优点

• 能够捕捉变量之间的成对依赖关系，从而更有效地探索搜索空间。
• 通过组合所选优良解中的有利特征生成新解，因而具有较快的收敛速度。
• 适用于具有复杂变量交互关系和多峰适应度景观的问题。

缺点

• 由于需要估计双变量分布，其计算复杂度高于单变量分布估计算法。
• 对于存在高阶依赖关系而非仅有成对依赖的问题，可能难以取得理想效果。
• 算法性能可能对种群规模和选择规模等参数较为敏感。

启发式建议

种群规模

• 初始种群规模通常可设为不少于变量个数的 10 倍。
• 对于高维问题或适应度景观较复杂的问题，可适当增大种群规模。
• 较大的种群规模有助于增强搜索的探索能力，但也可能减缓收敛速度。

选择规模

• 选择规模通常设为种群规模的一定比例，一般可取 10% 至 50%。
• 较大的选择规模可能加快收敛，但也会增加早熟收敛的风险。
• 较小的选择规模有助于维持种群多样性，但可能导致收敛速度下降。

终止条件

• 应结合问题复杂度与可用计算资源设定最大迭代次数。
• 可采用基于最优适应度值在连续若干代中的改进幅度的收敛判据。
• 也可将最大迭代次数与收敛判据结合使用，以平衡探索与开发。

约束处理

• 可引入罚函数、修复机制等约束处理技术，以应对不可行解问题。
• 可调整采样过程，使其更倾向于生成满足约束条件的解。
• 可结合专门的算子或局部搜索方法，以提升解的可行性。

混合策略

• 可考虑将 BMDA 与局部搜索技术相结合，以进一步细化解并增强局部优化能力。
• 可将领域启发知识或问题特定知识融入初始化、采样或选择过程。
• 可将 BMDA 与其他优化算法结合，以发挥各自优势并弥补单一方法的局限。