单变量边缘分布算法（UMDA）

名称

单变量边缘分布算法（Univariate Marginal Distribution Algorithm, UMDA）

分类

查看分类思维导图

单变量边缘分布算法是一种基于概率模型构建的进化算法，属于分布估计算法（Estimation of Distribution Algorithms, EDAs）领域。它与其他分布估计算法关系密切，例如基于种群的增量学习（Population-Based Incremental Learning, PBIL）和紧凑遗传算法（Compact Genetic Algorithm, cGA）。

• 计算智能
  • 生物启发计算
    • 进化计算
      • 分布估计算法
        • 单变量边缘分布算法

策略

UMDA 维护一个概率向量，用于表示搜索空间中优良解的分布。该概率向量通过对学习到的分布进行采样来生成新的候选解。算法以均匀概率分布作为初始状态，即假设每个变量的所有可能取值具有相同的出现概率。随着搜索过程不断推进，概率向量会依据每一代中表现最优的个体进行更新。

UMDA 中的关键信息处理步骤包括：

概率建模

UMDA 对每一代中优良个体的概率分布进行估计。它假设各变量之间相互独立，并分别对每个变量的边缘概率分布进行建模。这种简化处理使得概率分布的学习与采样过程更加高效。

采样

新候选解通过对学习得到的概率分布进行采样而生成。新解中的每个变量都按照其对应的边缘概率独立采样。通过这种方式生成的子代能够继承上一代优良个体所具有的特征。

选择

算法采用某种选择机制，例如截断选择（truncation selection），对父代与子代组成的联合种群进行筛选。表现最优的个体将被用于更新下一代的概率向量。该选择压力会推动搜索逐步向搜索空间中更有前景的区域收敛。

流程

数据结构

• 种群：由多个个体构成的数组，其中每个个体表示为一个决策变量向量。
• 概率向量：用于存储每个决策变量各可能取值概率的向量。
• 最优解：当前找到的最佳解。
• 最优适应度：当前找到的最佳解对应的适应度值。

参数

• 种群规模：种群中的个体数量。
• 迭代次数：算法允许执行的最大迭代轮数。
• 选择比例：用于更新概率向量的被选个体占种群的比例。
• 学习率：概率向量根据被选个体进行更新时的调整速率。

步骤

1. 初始化种群
   1. 对于种群中的每个个体：
      1. 随机初始化其决策变量取值。
      2. 计算该个体的适应度值。
   2. 必要时更新当前最优解和最优适应度。
2. 初始化概率向量
   1. 对于每个决策变量：
      1. 将其各可能取值的初始概率设为均匀分布。
3. 对每一次迭代，执行以下过程：
   1. 选择优良个体
      1. 根据适应度值对种群进行排序。
      2. 按照选择比例选出排名靠前的个体。
   2. 更新概率向量
      1. 对于每个决策变量：
         1. 根据被选个体统计该变量各可能取值的边缘概率。
         2. 按照学习率，将概率向量朝这些边缘概率方向更新。
   3. 采样生成新个体
      1. 对于种群中的每个个体：
         1. 对于每个决策变量：
            1. 根据更新后的概率向量采样得到变量取值。
         2. 计算该新个体的适应度值。
   4. 必要时更新当前最优解和最优适应度。
4. 返回最优解和最优适应度。

注意事项

优点

• 简单性：与其他分布估计算法和进化算法相比，UMDA 概念清晰、实现简便。
• 高效性：由于假设变量之间相互独立，UMDA 即使面对高维问题，也能较高效地完成概率分布的学习与采样。
• 适应性：UMDA 可通过调整概率向量的表示方式和采样机制，适应不同的问题领域。

缺点

• 表达能力有限：变量独立性假设并不适用于所有问题，因此算法在刻画复杂变量交互关系时能力不足。
• 易早熟收敛：当概率向量过度集中于某个次优解附近时，UMDA 可能出现早熟收敛，从而削弱探索能力。
• 参数敏感：UMDA 的性能对种群规模（N）和被选个体数量（M）等参数较为敏感，通常需要仔细调参才能取得较好效果。

启发式建议

种群规模（N）

• 初始种群规模可设为不少于问题变量个数的 10 倍。
• 对于更复杂的问题或高维搜索空间，可适当增大种群规模。
• 在设定种群规模时，应兼顾探索与开发之间的平衡。较大的种群有利于探索，较小的种群则更偏向开发。

选择压力（M）

• 被选个体数量（M）决定了 UMDA 中的选择压力。较大的 M 会带来更强的选择压力，使搜索更加集中于表现最优的区域。
• 一个常见经验是将 M 设为种群规模（N）的约 50%。这有助于在利用优良解与维持多样性之间取得平衡。
• 应根据问题特性调整选择压力。对于局部最优较多的问题，较低的选择压力更有助于保持多样性并避免早熟收敛。

终止准则

• 应根据可用计算资源和问题复杂度设定最大迭代代数，以防算法无限运行。
• 可设定目标适应度值或收敛阈值。当最优适应度达到或超过该值时，算法即可终止。
• 可引入提前停止机制，当种群陷入停滞，或在连续若干代中适应度提升极小的时候，提前结束算法。

概率向量初始化

• 通常应将概率向量初始化为均匀分布，以保证在搜索初期各变量可能取值具有相同机会。
• 若已具备问题相关先验知识，也可以在初始化时适当提高某些更有前景区域对应的概率。
• 除非有充分依据，否则应避免将初始概率设为极端值（0 或 1），以免过早限制搜索范围。

约束问题处理

• 可引入约束处理技术，如罚函数或修复机制，以应对问题中的约束条件。
• 可修改采样过程，使生成的解尽可能满足约束。
• 可在适应度评估中考虑解的可行性，从而引导搜索逐步向可行域集中。