摘要
本文综述了计算智能领域中分布估计算法（Estimation of Distribution Algorithms, EDAs）的核心思想、主要类别及其应用。文章首先介绍了EDA的基本框架与背景，然后依次探讨了一元模型、二元模型和多元模型的代表算法，包括UMDA、PBIL、MIMIC、ECGA、BOA等。接着，讨论了EDA在连续与离散问题上的扩展，以及最新的基于张量网络的方法。最后，总结了EDAs在优化、机器学习和组合问题中的典型应用，分析了当前面临的挑战，并展望了未来的发展方向。
引言
在计算智能（Computational Intelligence）领域，分布估计算法（Estimation of Distribution Algorithms，EDAs）是一类新兴的随机优化方法。与传统的遗传算法（GA）依赖交叉、变异等算子不同，EDAs 通过显式构建概率模型来捕捉优秀解的分布特征，再从模型中采样生成新解，逐步逼近全局最优。本文将系统介绍 EDAs 的基本原理、主要类别、典型算法及其在实际问题中的应用，并展望未来发展方向。
1. 基本原理
核心思想
- 不再直接使用交叉或变异算子；
- 从上一代优良个体中估计概率分布；
- 根据分布采样生成新个体。
典型流程
- 初始化：随机生成初始种群。
- 选择：根据适应度函数选出优秀样本。
- 建模：基于选样本估计概率模型。
- 采样：从概率模型中生成新个体。
- 迭代：返回第 2 步，直至满足终止条件。
2. 一元模型 EDA
2.1 UMDA（Univariate Marginal Distribution Algorithm）
- 模型假设：各变量相互独立；
- 建模方式：统计每个变量的边际分布；
- 优点：实现与计算简单；
- 缺点：无法捕捉变量间依赖，适合弱耦合问题。
2.2 PBIL（Population-Based Incremental Learning）
- 增量更新：用学习率将概率向量向优良样本方向平滑移动；
- 突变机制：在概率向量中加入小规模随机扰动，保持多样性；
- 特点：融合了 EDA 与演化策略的思想，平衡探索与利用。
3. 二元模型 EDA
3.1 MIMIC（Mutual-Information-Maximizing Input Clustering）
- 互信息排序：计算变量对间互信息，确定链式结构；
- 链式建模：沿链路依次估计条件分布；
- 适用场景：捕捉较强的二元依赖关系。
3.2 BMDA（Bivariate Marginal Distribution Algorithm）
- 局部二元模型：仅学习互信息排名前列的二元边缘分布；
- 简化假设：舍弃弱相关对，降低建模复杂度；
- 效果：在中等耦合场景下性能优越。
4. 多元模型 EDA
4.1 ECGA（Extended Compact Genetic Algorithm）
- MDL 原则：最小描述长度指导变量分组；
- 构造块：将高度关联的变量划入同一块，块间独立；
- 优势：在多元依赖与复杂度控制间取得平衡。
4.2 BOA（Bayesian Optimization Algorithm）
- 贝叶斯网络：构造任意拓扑结构的有向无环图；
- 增量搜索：逐步添加/删除边，使用评分函数评估模型；
- 灵活性：可捕捉高阶与非对称依赖。
4.3 EBNA（Estimation of Bayesian Networks Algorithm）
- 评分标准：多采用 BIC、K2 等准则，并加以惩罚项；
- 搜索策略：启发式地在网络结构空间中高效探索；
- 应用：适用于问题规模中等、依赖关系复杂的场景。
5. 连续与混合型 EDA
- EMNA（Estimation Multivariate Normal Algorithm）：假设解向量服从多元高斯分布，估计均值与协方差；
- 混合分布模型：将高斯、伯努利等分布组合，更灵活地表示混合型变量；
- 深度生成模型：最新研究将变分自编码器（VAE）、生成对抗网络（GAN）等引入 EDA，以捕捉复杂非线性关系。
6. 典型应用
组合优化
- 旅行商问题（TSP）、背包问题、作业调度等；
神经网络结构搜索
- 自动设计网络拓扑、超参数优化；
特征选择与超参数调优
- 在机器学习管道中，EDAs 对高维离散/连续混合空间具有优势。
7. 挑战与展望
- 模型复杂度：多元模型虽强，但构建与采样代价高；
- 高阶非线性依赖：传统分布难以表达，需要深度生成模型协同；
- 自适应策略：在线调整模型结构与学习率，以适应搜索阶段需求；
- 可解释性与理论分析：提升对收敛性质与参数选择的理论理解。
未来，随着张量网络、深度概率模型等新技术的融合，EDAs 将在更大规模、更高复杂度的问题中发挥更大潜力。