第25章　分布估计算法

25.1　分布估计算法的提出

分布估计算法（Estimation of Distribution Algorithm，EDA）是20世纪90年代初提出的一种启发式优化算法^[76]，[77]。1994年由美国卡耐基大学Baluja提出的用于解决二进制编码优化问题的PBIL（Population-Based Incremental Learning）算法被认为是最早的分布估计算法模型；1996年由M ü hlenbein提出的UMDA（Univariate Marginal Distribution Algorithm）算法给出了分布估计算法的概念。

分布估计算法的提出是为了解决基本遗传算法存在的欺骗问题和连锁问题。在遗传算法执行过程中，根据模式定理可知，短的、低阶的具有较高适应度值的模式将在种群中呈指数增长，就会增加求解时间，这样的问题称为欺骗问题。在遗传算法中，基因的不同排列顺序将直接导致“积木块”的长度发生变化，改变“积木块”的增长速度，从而影响遗传算法的收敛速度。交叉操作往往会破坏“积木块”，这样的问题称为连锁问题。为了解决遗传算法中存在的欺骗问题和连锁问题，人们提出不使用重组操作，通过先从优选的解集中提取信息，其次利用这种信息建立合适的概率分布，最后从概率分布中抽取出新解的方法，可以避免积木块的破坏，达到全局优化的目的。Baluja提出的分布估计算法模型有利于改善基本的遗传算法存在的欺骗问题和连锁问题。因此，分布估计算法又称为基于概率模型的遗传算法。

根据概率模型的学习和采样形式不同，发展了许多不同的实现算法，并用于多目标优化、运筹学、工程优化、模式识别、聚类分析、机器学习和生物信息等领域。

25.2　分布估计算法的基本原理

分布估计算法的基本思想是通过寻找群体的概率模型，指导生成新的群体来代替简单遗传算法中通过交叉和变异算子以引导算法的进化方向。

图25.1给出了一般分布估计算法与基本遗传算法执行过程中，从初始群体到构造新群体的对比关系。在分布估计算法中，没有遗传算法中的交叉和变异等操作，而是通过学习概率模型和采样操作使群体的分布朝着优秀个体的方向进化。从生物进化角度看，遗传算法模拟了个体之间微观的变化，而分布估计算法则是对生物群体整体分布的宏观建模和模拟。

分布估计算法是使用概率分布的方法描述和表示每一代群体。分布中包含了随机变量之间的概率依赖关系，这种关系也是一种基因之间的关系，学习随机变量的分布就等于学习基因之间的关系。在一个概率分布上的采样过程可以生成更有价值的群体和个体。因此，分布估计算法利用每一代的个体，从中学习随机向量的分布，然后在学习到的分布的基础上再生成下一代新个体，如此循环。

根据优化问题的复杂性不同，已提出多种不同的概率模型表示变量之间的关系，基本可归为两类：一类是基于优选解集的统计信息建立优选解集的概率模型；另一类是采用蒙特卡罗方法由概率模型随机采样产生新的种群。根据概率模型所描述变量是离散的还是连续的来分类，又可以分为离散分布估计算法和连续分布估计算法。

25.3　分布估计算法的描述

下面介绍离散变量的分布估计算法中变量无关的分布估计算法描述。

假设随机向量的元素之间是相互独立的，每一个个体的概率仅由每个变量各自的概率来确定，即

二进制编码的优化问题表示的解空间分布概率模型是一个概率向量p（x）=（p（x₁），p（x₂），…，p（x_n）），其中p（x_i）表示第i基因位上取值为1的概率，概率图模型如图25.2所示。

早期的分布估计算法都是针对变量无关的问题的，如基于群体的增量学习算法（PBIL）、单变量边缘分布算法（UMDA）等。1994年Baluja提出了PBIL算法用以解决二进制编码的优化问题。在PBIL算法中，表示解空间分布的概率模型是一个概率向量p（x）=（p（x₁），p（x₂），…，p（x_n）），p（x_i）表示x_i取值为1的概率。其概率模型及新个体描述如下。

（1）设，，…，表示第t代所选择的μ个优秀个体，则概率模型构造方式为

其中，α为学习率；p（x，t）为第t代群体的概率分布。

（2）由p（x_i），i=｛1，2，…，n｝随机采样得到每一个变量值，从而采样得到一个新的解，重复N次获得N个新的个体。

在优化问题中，每个自变量x_i可看作一个随机变量（可以编码为遗传算法中的一个基因），所有随机变量构成一个随机向量x=（x₁，x₂，…，x_n）（对应于遗传算法中的基因串）。这样，每一个体就是该随机向量的一个取值，而一个群体就对应于该随机向量的一个分布。随机向量的分布是群体性能的一个指标，利用这个指标可以紧凑和整体地表示该群体。

25.4　分布估计算法的基本步骤及流程

分布估计算法的基本步骤如下。

（1）t←0，随机产生初始群体Pop（t），其中Pop（t）表示第t代群体。

（2）根据某种选择机制从Pop（t）中选择部分优秀解来组成S（t）。

（3）估计S（t）的分布，并依据此分布产生下一代新个体Pop（t+1）。

（4）若终止条件不满足，则t←t+1，转步骤（2），否则，结束。

分布估计算法的流程如图25.3所示。

下面通过一个简单例子，介绍分布估计算法独特的进化操作过程。

【例25.1】　假设用分布估计算法求解函数的最大值，x∈｛0，1｝ⁿ，n=3。在这个例子中，描述解空间的概率模型用简单的概率向量p=（p₁，p₂，…，p_n）表示，p表示群体的概率分布，p_i∈［0，1］表示基因位置i取1的概率，1-p_i表示基因位置i取0的概率。

（1）初始化群体B₀。初始群体在解空间中按照均匀分布随机产生情况如表25.1所示，概率向量p=（0.5，0.5，0.5）。群体大小为8，通过适应度函数计算各个个体的适应度值。

（2）选择适应度值较高的4个个体更新概率向量p，如表25.2所示。X_s表示选择后的优势群体，概率向量p通过p_i=P（x_i=1|X_s）更新，如p₁=P（x₁=1|X_s）=0.75，这样得到新的概率向量p=（0.75，0.75，0.75）。

（3）由概率向量p产生新一代群体。概率向量描述了各个可能解在空间的分布情况，产生任意解b=（b₁，b₂，…，b_n）的概率为

例如，b=（1，1，0），则P（1，1，0）=0.75×0.75×0.25≈0.14。通过随机采样的方法产生新的群体，如表25.3所示，可以发现新产生的群体的个体适应度有了显著的提高。

至此，分布估计算法完成了一个周期。然后返回步骤（2），从表25.3当前群体中选择最优秀的4个个体，建立新的概率模型p=（1.00，0.75，0.75），然后再对概率模型随机采样产生新一代群体。本例中，最优解为（1，1，1），可以发现随着分布估计算法的进行，（1，1，1）的分布概率由最初的0.125（0.5×0.5×0.5）变为0.42（0.75×0.75×0.75），然后变为0.56（1.00×0.75×0.75），可以看出，适应度高的个体的出现概率越来越大。按照上面的步骤，改变个体在解空间的概率分布，使适应度高的个体分布概率变大，适应度低的个体分布概率变小，如此反复进化，最终将产生待优化问题的最优解。