文档介绍：第 8 章分布估计算法
(Estimation of Distribution Algorithms , EDA)
了解分布估计算法的研究背景,熟练掌握分布估计算法的设计流程和思想,理解对于分布估计算法的改进角度和改进方法,并能理解分布估计算法的实际应用。
1
分布估计算法
分布估计算法又称为基于概率模型的遗传算法(Probabilistic Model Building ic Algorithms , PMBGA) ,是 20 世纪90 年代初提出的一种新型的启发式算法。它结合了统计学****理论和遗传算法的原理,通过构建概率模型、采样和更新概率模型等操作实现群体的进化。
分布估计算法的思想起源于遗传算法,但却有与遗传法截然不同的进化模式。从一定意义上说,遗传算法是在“微观”层面上对生物进化进行模拟,而分布估计算法则是在“宏观”的层面上来控制算法搜索。是一种全新的进化模型。
2
分布估计算法
照"积木块假设"的观点,遗传算法的演化过程是对种群染色体中的大量“积木块”进行选择和重组操作,通过组合出更多好的“积木块”来逐步搜索出全局最优解的过程。
实践证明,遗传算法在求解“积木块”紧密相连的问题时表现出了很好的性能,但是在求解“积木块”松散分布的问题时性能却很差。这是因为算法中的交叉操作经常会破坏“积木块”从而导致算法趋于局部收敛或者早熟
3
分布估计算法
为了解决遗传算法中"积木块"被破坏的问题,提出了许多改进方案。这些方案可以分为两大类别:
一类是通过学****解的结构,发现"积木块"并避免"积木块"的破坏。这类改进的遗传算法称为连锁学****遗传算法(Linkage Learning ic Algorithm)
另一种带有"全局操控"性的操作模式替换掉遗传算法中对"积木块"具有破坏作用的遗传算子,这就是分布估计算法。
和遗传算法的算法结构相比,分布估计算法没有交叉算子和变异算子,取而代之的是建立概率模型和采样两大操作。
4
5
分布估计算法是一种基于种群的随机优化算法,
它首先需要生成一个初始种群,
然后通过建立概率模型和采样等操作使种群得到不断的进化,直到达到结束条件。
建立概率模型和采样是分布估计算法的核心步骤,也是 EDA 与 GA 的最大不同之处。
由于分布估计算法没有"交叉"和"变异"操作,因而通常不用基因来描述个体所包含的信息,取而代之的是变量(Variables) 。
6
分布估计算法通过分析较优群体所包含的变量,构建符合这些变量分布的概率模型,
然后基于该概率模型再产生新的种群。
因为概率模型是由种群中优势群体建立起来的,所以基于该模型产生的新种群在整体质量上将优于原来的种群。
由此推断,种群的整体质量经过多次迭代后将不断得到提高。
分布估计算法就是按照这种形式将当前最优解一步一步地逼近全局最优解的。
7
经典的分布估计算法UMDA 的执行步骤
第一步: 随机产生 N 个个体来组成一个初始种群,并评估初始种群中所有个体的适应度。
第二步: 按适应度从高到低的顺序对种群进行排序,并从中选出最优的 Se 个个体(Se≤ N) 。
第三步: 分析所选出的 Se 个个体所包含的信息,估计其联合概率分布 p (x) 。
其中,n 为解的维数,p (xi) 为每维变量的边缘分布。
9
经典的分布估计算法UMDA 的执行步骤(续)
第四步: 从构建的概率模型 p (x) 中采样,得到 N 个新样本,构成新种群。此时,若达到算法终止条件则结束,否则执行第二步。
注意:UMDA 在估计概率模型时,认为变量之间是独立不相关的。
定义 OneMax 问题: 对于固定长度为 N 的二进制串, OneMax 问题要求找到一个包含 1 的个数最大的二进制串,即找到 x =(x1, x2 , …, xn ) , xn ∈{ 0, 1} ,使得
最大化。
10