因子分解分布算法（FDA）

名称

因子分解分布算法（Factorized Distribution Algorithm, FDA）

分类

查看分类思维导图

因子分解分布算法是一种基于概率模型构建的进化算法，属于分布估计算法（Estimation of Distribution Algorithms, EDAs）范畴，而分布估计算法又隶属于更广义的进化计算与优化领域。

• 计算智能
  • 进化计算
    • 进化算法
      • 分布估计算法（EDAs）
        • 因子分解分布算法（FDA）

策略

因子分解分布算法通过迭代更新优良解的概率模型来进行搜索，该模型基于当前种群中的优秀个体构建。该模型采用因子分解表示方式来刻画变量之间的依赖关系，从而能够更加准确、高效地探索搜索空间。

概率建模

在每次迭代中，FDA 通过估计被选个体的联合概率分布来构建概率模型。该模型将联合分布分解为边缘概率与条件概率的乘积形式，以反映变量之间的依赖关系。这种分解通常借助图模型来表示，例如贝叶斯网络或马尔可夫随机场。

采样与选择

在完成概率模型构建后，FDA 从该模型中采样生成新种群。采样过程会利用已学习到的变量依赖关系，使新个体能够继承被选父代中具有潜力的模式。随后，依据具体问题的适应度函数对生成的个体进行评估。

模型更新与迭代

在新个体完成评估后，FDA 选择其中表现最优的个体，用以更新下一轮迭代中的概率模型。该选择过程旨在逐步将模型推向包含高质量解的搜索空间区域。算法不断重复上述过程，直到满足终止条件，例如达到最大代数或找到满意解。

流程

1. 初始化：
   1. 设置种群规模（N）、选择规模（S）以及最大迭代代数（G）。
   2. 随机生成包含 N 个个体的初始种群。
2. 计算种群中每个个体的适应度值。
3. 当终止条件未满足时，重复以下过程：
   1. 根据适应度从种群中选择 S 个个体。
   2. 构建所选个体的概率模型：
      1. 估计所选个体的联合概率分布。
      2. 将该分布分解为边缘概率与条件概率的乘积形式。
      3. 使用图模型表示该分解结构（如贝叶斯网络或马尔可夫随机场）。
   3. 从概率模型中采样生成 N 个新个体。
   4. 计算每个新个体的适应度值。
   5. 用新个体替换当前种群。
   6. 更新迭代代数计数器。
4. 返回搜索过程中找到的最优个体。

数据结构

• 种群：由 N 个个体组成的数组，每个个体表示一个候选解。
• 概率模型：用于对所选个体联合概率分布进行因子分解的图模型，例如贝叶斯网络或马尔可夫随机场。

参数

• 种群规模（N）：种群中个体的数量。
• 选择规模（S）：用于构建概率模型的被选个体数量。
• 最大迭代代数（G）：基于迭代次数设定的终止条件。

注意事项

优点

• 能够捕捉变量之间的依赖关系，从而更准确地刻画搜索空间中有前景的区域。
• 通过概率建模维持种群多样性，从而降低早熟收敛的风险。
• 能够通过学习并利用变量交互关系，使搜索过程自适应于问题结构。

缺点

• 构建概率模型并从中采样的计算复杂度较高，尤其是在变量较多且依赖关系复杂的问题中更加明显。
• FDA 的性能依赖于概率模型的质量，因此通常需要对模型进行精心设计与调参。
• 对于高度多峰或欺骗性较强的适应度景观，算法可能表现不佳，因为其依赖于“优良解具有共同模式”这一假设。

启发式建议

种群规模

• 初始种群规模可设置为不少于问题变量个数的 10 倍。
• 对于高维问题或变量依赖关系复杂的问题，可适当增大种群规模。
• 在设定种群规模时，应综合考虑探索能力与计算效率之间的权衡。

选择规模

• 选择规模应在保持多样性与聚焦潜在优良区域之间取得平衡。
• 一个常见经验是选择约占种群规模 50% 的个体。
• 可通过实验不同的选择规模，确定适合具体问题的最佳取值。

概率模型构建

• 应采用能够有效刻画变量依赖关系的图模型，例如贝叶斯网络或马尔可夫随机场。
• 需要同时考虑模型复杂度以及模型学习与采样的计算代价。
• 若问题具有已知或可假设的结构，可将这些先验知识融入概率模型的设计中。

终止条件

• 应根据可用计算资源和问题复杂度设置最大迭代代数。
• 可结合其他终止条件，例如收敛检测或最小适应度阈值。
• 在算法运行过程中应持续监测其搜索进展，并在必要时调整终止条件。

混合化

• 可考虑将 FDA 与局部搜索技术结合，以进一步改进概率模型生成的解。
• 可引入问题领域相关的启发式信息或算子，以增强搜索过程并提升解的质量。
• 可尝试不同的混合策略，并评估其对算法性能的影响。