分布估计算法 | Roberto Santana

分布估计算法 (EDA) 是进化计算领域的一个范式，它通过构建并采样一个包含当前优秀解的概率模型，来取代传统的遗传算法算子（交叉和变异）。我对 EDA 的研究跨越了从理论基础到复杂现实世界应用的广泛领域。我是专著 Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation (Springer, 2002) 的合著者，我的博士论文也致力于 EDA 的研究。

EDA 基础

理论基础

EDA 弥合了概率建模与进化搜索之间的鸿沟。EDA 不是通过交叉和变异算子组合父代解，而是从种群中的优秀个体中学习概率模型，然后从该模型中采样生成新个体。这种方法使变量之间的依赖关系变得显式化，并利用这些关系指导搜索过程。

我的早期研究侧重于 EDA 的理论特性，分析其收敛行为、学习模型的质量以及问题结构与算法性能之间的关系。这包括对连锁学习 (linkage learning) 的研究，以及设计能够识别并利用变量间相互作用的 EDA。

EDA 分类

EDA 可以根据所使用概率模型的复杂度进行分类。一元 EDA（如 UMDA 和 PBIL）假设变量之间相互独立。二元 EDA（如 MIMIC 和 BMDA）可以捕捉成对的依赖关系。多元 EDA（如 BOA、EBNA 和 ECGA）使用完整的概率图模型——贝叶斯网络或马尔可夫网络——来表示变量之间的高阶依赖关系。

离散与组合 EDA

基于贝叶斯网络的 EDA

贝叶斯网络估计算法 (EBNA) 及其变体在 EDA 循环中使用贝叶斯网络作为概率模型。算法从选定的种群中学习贝叶斯网络的结构和参数，然后从学习到的网络中采样生成新的候选解。

针对基于贝叶斯网络的 EDA 的研究解决了结构学习问题（寻找能够精确表示数据依赖关系的社交网络）、学习和采样网络计算成本问题，以及对搜索过程中学习到的模型进行理论分析。

基于马尔可夫网络的 EDA

研究在 EDA 中使用马尔可夫网络（无向图模型）作为概率模型。马尔可夫网络 EDA 可以表示变量之间的对称统计依赖关系，这使其特别适用于具有对称结构的问题。这一研究方向包括为马尔可夫网络 EDA 开发学习算法，并在基准问题上进行评估。

用于组合优化的 EDA

将 EDA 应用于挑战性的组合优化问题，包括置换问题（如二次分配问题、旅行商问题和调度问题）、伪布尔优化问题以及多目标组合优化。该领域的一个关键挑战是为结构化解表示设计合适的概率模型。

连续 EDA

基于高斯分布的连续 EDA

将 EDA 扩展到使用高斯概率分布的连续优化领域。一元高斯 EDA 独立地为每个变量建模高斯分布。多元高斯 EDA（如 EGNA）使用多元高斯分布建模变量间的依赖关系。研究探讨了高斯模型的协方差结构与适应度景观结构之间的关系。

基于 Copula 的连续 EDA

开发在 EDA 循环中使用 Copula 函数建模变量联合分布的算法。Copula 允许分别建模边缘分布和依赖结构，提供了比标准高斯模型更大的灵活性。这一研究方向包括藤 Copula (Vine Copula) EDA，它利用二元 Copula 序列（藤结构）对复杂的多元依赖关系建模。

ACM TELO 2024 →

能源系统的参数优化

将连续 EDA 应用于地热发电厂及其他工程系统的参数优化。目标是优化复杂物理系统的操作参数，以实现效率最大化或成本最小化。连续 EDA 为这类黑盒优化问题提供了一种结构化的处理方法。

CIIS 2024 →

EDA 模型分析

EDA 学习了什么

EDA 研究中的一个核心问题是：在进化搜索过程中学习到的概率模型捕获了哪些信息？研究分析了 EDA 学习到的模型与适应度景观结构、问题中变量间的相互作用以及最优解属性之间的关系。

作为问题表征的 EDA 模型

EDA 学习到的概率模型可以被视为优化问题结构的压缩表征。研究探讨了如何从这些模型中提取有用信息，而不仅仅是利用它们生成新的候选解。这包括使用 EDA 模型识别相关的变量交互、检测问题的对称性，以及为未来的优化运行提供热启动信息 (warm-start)。

应用领域

用于机器学习的 EDA

将 EDA 应用于机器学习任务，包括特征选择、神经架构搜索和超参数优化。EDA 的概率模型能够自然地捕捉特征或架构组件之间的依赖关系，使搜索过程能够利用这些依赖关系进行更高效的探索。

用于科学计算的 EDA

将 EDA 应用于科学计算问题，包括为模拟金融资产或物理过程的随机微分方程估算参数、蛋白质结构预测以及实验设计。EDA 为这些领域的黑盒优化提供了结构化的方法。

Math. & Computers in Simulation 2021 →

精选论文