2022年自创-分布估计算法综述资料 .pdf

《2022年自创-分布估计算法综述资料 .pdf》由会员分享，可在线阅读，更多相关《2022年自创-分布估计算法综述资料 .pdf（21页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、20 中 山 大 学 计 算 机 系2011 分布估计算法(EDA)综述谭维广 州 大 学 城 东 校 区名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 21 页 -摘要分布估计算法(Estimation of Distribution Algorithms,EDA)，是进化计算领域兴起的一种新型的优化算法。在传统的遗传算法中，用种群表示优化问题的一组候选解，种群中的每个个体都有相应的适应值，然后进行选择、交叉和变异等模拟自然进化的操作，反复进行，对问题进行求解；而在分布估计算法中，没有传统的交叉、变异等遗传操作，取而代之的是概率模型的学习和采样。关键词分布估计算法，计算智能，统

2、计学习，概率模型目录一、分布估计算法概述二、分布估计算法的发展历史三、一个简单的分布估计算法四、分布估计算法经典概率模型比较五、分布估计算法的研究热点与应用六、总结七、参考文献名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 21 页 -一、分布估计算法概述分布估计算法(Estimation of Distribution Algorithms,EDA)，是进化计算领域兴起的一种新型的优化算法。在传统的遗传算法中，用种群表示优化问题的一组候选解，种群中的每个个体都有相应的适应值，然后进行选择、交叉和变异等模拟自然进化的操作，反复进行，对问题进行求解；而在分布估计算法中，没有传统的交

3、叉、变异等遗传操作，取而代之的是概率模型的学习和采样。分布估计算法采用统计学习手段从群体宏观的角度建立一个描述解分布的概率模型，然后对概率模型随机采样产生新的种群，如此反复进行，实现种群的进化，直到满足终止条件。根据概率模型的复杂程度以及不同的采样方法，分布估计算法发展了很多不同的具体实现方法，但是都可以归纳为下面两个主要步骤：1)构建描述解空间的概率模型，通过对种群的评估，选择优秀的个体集合，然后采用统计学习等手段构造一个描述当前解集的概率模型。2)由概率模型随机采样产生新的种群，一般的，采用蒙特卡罗方法，对概率模型采样得到新的种群。分布估计算法给人类解决复杂的优化问题提供了新的工具，它通过

4、概率模型可以描述变量之间的相互关系，从而对解决非线性、变量耦合的优化问题更加有效，试验表明，分布估计算法能更加有效的解决高维问题，降低时间复杂性，例如，贝叶斯优化算法(分布估计算法的一种)可以通过与问题规模成多项式数量级的采样求得一类GA(Genetic Algorithm)难问题的最优解。分布估计算法是一种新的启发式搜索策略，是统计学习理论与随机优化算法的结合，与其他智能优化算法的混杂设计，将极大丰富混杂优化算法的研究内容，给优化算法的研究提供了新的思路。遗传算法中的交叉和变异会破坏已经优化好的个体，分布估计算法用建立概率模型和采样两大操作取代了遗传算法中的交叉算子和变异算子，以一种带有“全

5、局操控”性的操作模式解决了遗传算法存在的这一问题。遗传算法和分布估计算法的流程图对比如下：名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 21 页 -否否是是二、分布估计算法的发展历史分布估计算法的概念最先有M hlenbein 于 1996 年提出，但早在1994 年，Baluja 就提出了原始的分布估计算法模型，即PBIL(Population-Based Incremental Learning)算法。Baluja在 1994 至 1995 年间相继发表了三篇文章，系统阐述了PBIL 算法的基本原理和性能，为分布估计算法的发展打下了良好的基础。随后，M hlenbein 于

6、 1996 年提出了另一种经典的分布估计算法：UMDA(Univariate Marginal Distribution Algorithm)。UMDA 与 PBIL 的原理非常类似，只是概率模型的更新方法有所不同。早期对分布估计算法的研究都是围绕二进制编码展开的，而且集中于研究问题变量无关的情形。这类简单的分布估计算法除了PBIL 和 UMDA之外，还有Harik 于 1997 年提出的开始生成初始种群评估种群适应度选择操作交叉操作变异操作评估种群适应度达到结束条件结束开始生成初始种群评估种群适应度选择操作构建概率模型抽样产生新种群评估种群适应度达到结束条件结束名师资料总结-精品资料欢迎下载

7、-名师精心整理-第 4 页，共 21 页 -CGA(Compact Genetic Algorithm)。1997 至 2000 年是 EDA 迅速发展的黄金时期，期间出现了多种经典的研究多变量相关性的分布估计算法，如 MIMIC(Mutual Information Maximizing Input Clustering)、COMIT(Combining Optimizers with Mutual Information Trees)、FDA(Factorized Distribution Algorithm)和 BOA(Bayesian Optimization Algorithm)等。

8、其中，MIMIC由 De Bonet 于 1997 年提出，它采用了一种链式关系来描述变量之间的关系。在MIMIC的基础上，Baluja 于 1997 年提出了另一种双变量相关分布估计算法COMIT，它采用树状结构来描述变量之间的关系。由于MIMIC和 COMIT 所采用的链式和树状结构依然无法完美地表达变量之间的关系，M hlenbein 于 1998 年提出了另一种经典的分布估计算法FDA，它需要预先给定变量之间的依赖关系。BOA 则由 Pelikan 于 1999 年提出，它采用了贝叶斯网络来描述变量之间的关系。上述的几种分布估计算法都是以二进制编码的形式来描述的，最原始的实数编码分布估

9、计算法是Servet 等于 1997 年提出的一种基于均匀分布的实数编码PBIL。该算法以类似二分法搜索的形式逼近最优解，实验表明该算法在搜索过程中容易丢失全局最优解，而且一旦丢失就再也无法找回。随后，Sebag于 1998 年提出了一种基于高斯分布的实数编码PBIL，解决了全局最优解的丢失问题，因而有较好的性能(该算法被简称为PBILc)。与 UMDA对应，Larranaga 于 2000 年提出了UMDAc。此外，日本学者Tsutsui 还于 2001 年提出了一种基于直方图的实数编码分布估计算法HEDA，Ahn 则于 2004 年将 BOA 拓展到实数编码。可见，实数编码的分布估计算法在

10、2000 年前后迅速发展，而高斯分布是其中被应用得最广泛的概率模型。随着实数编码EDA 和多变量相关EDA 的迅速发展，结合 EDA 与其它进化算法的混合分布估计算法(Hybrid EDA)、自适应分布估计算法(Adaptive EDA)、并行分布估计算法(Parallel EDA)以及关于分布估计算法的理论研究都开始踏入EDA 发展的历史舞台，成为了名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 21 页 -当前 EDA 研究的热点。在混合EDA 反面，Pena等提出了结合遗传算法与分布估计算法的GA-EDA，Zhang 等提出了结合差分算法的DE-EDA 以及结合局部搜索算法

11、的EDA/L，Iqbal和 Wang分别提出以不同形式结合粒子群算法的PSO-EDA 等。在自适应分布估计算法方面，Lu 提出了基于聚类分析的自适应EDA，在一定程度上克服了单一高斯分布的EDA 难于求解多峰函数优化问题的缺点；Santana 则提出了采用多种概率模型产生样本的方法。在并行分布估计算法方面，近年来陆续提出了一些并行策略，主要集中于概率模型学习的并行化。随着对分布估计算法的理论研究的不断深入，许多研究者开始采用分布估计算法解决复杂的优化问题。目前，分布估计算法的主要研究领域包括函数优化、组合优化、生物信息、多目标优化和机器学习等。可以预计，拓展分布估计算法的应用将是进化计算领域的

12、又一个研究热点。经过十多年的发展，分布估计算法已经成为当前国际学术界的一个热门课题。其中，权威的国际期刊Evolutionary Computation 于2005 年出版了分布估计算法的专刊；ACM SIGEVO、IEEE CEC 等许多权威国际学术会议都设有分布估计算法的专题讨论。三、一个简单的分布估计算法下面详细描述使用UMDA 分布估计算法优化OneMax 问题的演化过程。UMDA 算法执行步骤如下：第一步：随机产生N 个个体组成一个初始种群，并评估初始种群中所有个体的适应度；第二步：按适应度从高到低的顺序对种群进行排序，并从中选出最优的Se 个个体(SeN)；第三步：分析产生的Se个

13、个体所包含的信息，估计其联合概率分布p(x)。p(x)=p(x|DSe)=p(xi)(in)，其中 n 为解的维数，p(xi)为每维变量的边缘分布。第四步：从构建的概率模型p(x)中采样，得到N 个新样本，构成新种群。此时，若达到算名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 21 页 -法的终止条件则结束，否则执行第二步。UMDA在估计概率模型时，认为变量之间是相互独立的，早期所提出的分布估计算法如 PBIL 和 CGA 都采用变量无关的概率模型。OneMax 问题：对于固定长度为N 的二进制串，OneMax 问题要求找到一个包含1 的个数最多的二进制串，即找到x=(x1,x

14、2,.,xN)，xi0,1，使得 F(x)=xi(1iN)最大化。我们用一个简单的概率向量p=(p1,p2,p3,p4)来表示描述种群分布的概率模型，其中pi表示 xi取 1 的概率，(1-pi)则为 xi取 0 的概率。第一步：产生初始种群。为了使初始种群在定义域内符合均匀分布，我们定义初始化概率向量模型p=(0.5,0.5,0.5,0.5)，然后根据p 产生规模为10 的初始种群，最后根据F(x)=x1+x2+x3+x4计算出初始种群的适应度，最终结果如下：编号x1x2x3x4f 1 2 3 4 5 6 7 8 9 10 1 1 0 0 1 0 1 0 1 1 1 0 1 1 1 1 0

15、0 0 0 0 0 0 1 0 1 1 1 0 0 1 0 0 1 1 0 0 1 0 1 3 1 1 3 3 2 2 2 1 2 第二步：按照种群的适应度从高到低进行排序。从种群中选出适应度较高的5 个个体用名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 21 页 -来更新概率向量模型p。XS表示选择后的优势群体，概率向量p 通过式 pi=P(xi=1|XS)更新，例如 p1=P(x1=1|XS)=0.6，最终得到新的概率向量模型为p=(0.6,0.8,0.6,0.6)。选择操作后的优势群体如下：编号原编号x1x2x3x4f 1 2 3 4 5 1 4 5 6 7 1 0 1

16、0 1 1 1 1 1 0 0 1 0 1 1 1 1 1 0 0 3 3 3 2 2 第三步：根据更新后的概率模型p 产生新的样本，并计算这些样本的适应度。最终得到新一代的种群如下：编号x1x2x3x4f 1 2 3 4 5 6 7 8 9 10 1 0 0 1 0 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 0 0 1 1 1 1 1 1 0 0 0 0 1 1 1 0 0 1 1 0 2 1 3 4 3 1 3 4 3 2 名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 21 页 -通过以上三步，分布估计算法完成了第一代的进化过程。接着重复第二步和第三步完成

17、下一代的进化，最终得到的种群平均适应度和概率模型如下表所示。我们可以看出，随着演化的进行，种群的整体质量不断提高，概率向量逐渐逼近全局最优解。进化代数概率向量种群平均适应度1 2 3 4 5(0.5,0.5,0.5,0.5)(0.6,0.8,0.6,0.6)(0.8,1.0,0.6,0.8)(1.0,1.0,1.0,0.8)(1.0,1.0,1.0,1.0)2.2 2.6 2.9 3.8 4.0 分布估计算法的总体框架如下，各种算法总体框架一样，只是所采用的概率模型(或者编码方式)存在差异。?Estimation of Distribution Algorithms do just that!

18、?Typically they operate as follows:Step 0:Randomly generate a set of individuals(t=0)Step 1:Evaluate the individuals While(not done)Step 2:Select individuals(where)to be parents?Develop a probability distribution/density function,pt,based on the parents Step 3:Create offspring using ptStep 4:Evaluat

19、e the offspring Step 5:The offspring replace the parents(t=t+1)名师资料总结-精品资料欢迎下载-名师精心整理-第 9 页，共 21 页 -Step 6:Goto While 我们再来比较看一下Basic PBIL：算法描述?P initialize probability vector(each position=0.5)?while(generations+limit)for each vector i do for each position j do generate Vi(j)according to P(j)end-do

20、evaluate f(Vi)end-do Vmax=max(f(Vi)update P according to Vmax if random(0,1 Pmutate mutate P end-if?end-while Details?Population replaced by probability vectorP=p1,p2,p?pi:Probability of 1 in the ith bit?Generate n individuals 名师资料总结-精品资料欢迎下载-名师精心整理-第 10 页，共 21 页 -?Update P using the best individual

21、 pi(t+1)=xi+pi(t)(1-),i=1,2,?Mutate P:pi(t+1)=mU0,1)+pi(t+1)(1-m)Example?t=0,P=0.5,0.5,0.5,0.5?Generate 5 individuals 1010,1100,0100,0111,0001?Fitness:2,2,1,3,1?Best individual:0111;=0.1?Update P p1=0.5*(1-0.1)=0.45 p2=p3=p4=0.1*1+0.5*(1-0.1)=0.55 四、分布估计算法经典概率模型比较经过十多年的发展，分布估计算法已经有了许多形式的改进：从求离散问题的分布

22、估计分布估计算法所采用的概率模型变量无关型双变量相关模型多变量相关模型PBIL:Baluja 1994 UMDA:M hlenbein 1996 CGA:Harik 1997 MIMIC:Bonet 1997 COMIT:Baluja 1997 BMDA:Pelikan 1999 FDA:M hlenbein 1999 BOA:Pelikan 1999 ECGA:Harik 1999 名师资料总结-精品资料欢迎下载-名师精心整理-第 11 页，共 21 页 -算法扩展到求连续问题的分布估计算法；从变量无关的分布估计算法扩展到多变量相关的分布估计算法；从单一的分布估计算法扩展到混合其它算法，甚至

23、具有自适应功能的分布估计算法。与此同时，对分布估计算法的机理研究及其收敛性的研究也逐渐开展了起来。早期提出的分布估计算法都是属于变量无关的一类，如PBIL，UMDA和 CGA 等。由于在实际应用中，问题所包含的变量之间往往有关联关系，采用变量无关的分布估计算法求解这类问题无法得到令人满意的效果。针对这个问题，学者们展开了深入地研究，并相继提出了一系列用于求解具有变量相关性的问题分布估计算法。根据这些改进的分布估计算法对变量关联性捕捉能力的差异可以将它们分为三大类，如上图所示。比较经典的概率模型有：链式概率模型，树状概率模型，贝叶斯网络概率模型和高斯概率模型。下面简单介绍树状概率模型、贝叶斯网络

24、概率模型和高斯概率模型。(1)树状概率模型COMIT 是 Baluja 于 1997 年提出的另一种变量相关分布估计算法，是解决双变量相关的分布估计算法，采用一种树状结构来描述变量之间的关系。COMIT采用机器学习领域Chou 和 Liu 提出的方法构造概率模型，并根据 MIMIC 的取样方式从概率模型中产生新样本。COMIT 构建概率模型和采样的路程由以下四步组成：第一步：定义数组A，AXi=a,Xj=b记录所有变量对Xi和 Xj,Xi=a,Xj=b 出现的次数。首先将 AXi=a,Xj=b初始化一个小常量，然后采用增量学习手法不断更新，使得最新出现的权重越大，即更新数组A 时，首先所有值乘

25、以一个挥发因子，然后每出现一个Xi=a,Xj=b，则 AXi=a,Xj=b的值增加 1.0。第二步：根据AXi=a,Xj=b计算变量对Xi和 Xj之间的关联性。关联系数定义为：,(,)(,)(,)log()()ijijija bijP Xa XbI XXP Xa XbP Xa P Xb第三步：根据关联系数信息，构建关联树。其构建过程如下：名师资料总结-精品资料欢迎下载-名师精心整理-第 12 页，共 21 页 -step1：随机选择一个结点v0作为根，令S 为已处理的节点集合，则有S=v0。step2：从s中选择与S 的节点关联系数最大的节点vk加入 S，即 S=vkS。step3：若s转 s

26、tep2，否则结束。第四步：深度优先遍历关联树，产生新样本。(2)贝叶斯网络概率模型贝叶斯网络是描述变量之间概率依赖关系的数学模型，其拓扑结构为一个有向无环图(DAG)，其中每个节点代表一个变量，而每条边则表示变量之间的依赖关系。贝叶斯网络提供了一种把联合概率分布分解为局部概率分布的方法。假设 X=X1，X2，.Xn 为随机变量集，x=x1,x2,x3xn 表示变量的集合，则基于贝叶斯网络的联合概率为：11121211()(|)(|)(|)()nnnnP xP xxxP xxxP xxP x由于贝叶斯网络可以很好地描述变量之间的复杂依赖关系，Pelikan 等人与 1999 年提出基于贝叶斯网

27、络的分布估计算法(BOA)。BOA采用贝叶斯网络概率模型，采样时根据贝叶斯网络拓扑结构图从父节点刀子节点依次采样生成样本。其中，构建贝叶斯网络模型的过程暴扣网络结果的学习和参数的学习两个过程。Pelikan 等人的研究表明，BOA 在求解复杂优化问题时取得了很好地效果，其算法流程伪代码如下：/BOA 伪代码Procedure BOA D 0Generate N individuals randomly l=1 while not met stopping criterion do Se(l)select SeN individuals from Dl-1 according to a sele

28、ction method Construct the network B using a chosen metric and constraints 名师资料总结-精品资料欢迎下载-名师精心整理-第 13 页，共 21 页 -Generate a set of new individuals T(l)according to the joint distribution encoded by B Create a new population Dl by replacing some individuals from Dl-1 with O(l)l=l+1 end while end proc

29、edure(3)高斯概率模型高斯分布又称正态分布，通常记为N(,2)，其中为分布的均值，为分布的方差。高斯概率模型是实数编码分布估计算法的经典概率模型。PBIL 和 UMDA 对应的实数编码分布估计算法PBILc 和 UMDAc所采用的概率模型都是高斯概率模型。此外，多元高斯模型也是解决多变量相关的实数编码分布估计算法常采用的概率模型。下面以PBILc 为例，介绍高斯概率模型解决连续空间的优化问题的流程。PBILc 对每个变量，xj定以一个一元高斯分布N(j,j2)，然后根据每个N(j,j2)在整个定义域空间产生一个样本。构建概率模型的过程主要包括j,j的确定，j约束了样本的中心，而 j则控制

30、着样本的多样性。随着种群的进化，j将逐渐逼近全局最优解的位置，而j将越来越小，从而使种群聚集在全局最优解的附近。具体地说，PBILc 的求解过程由下面四步组成。第一步：随机产生初始种群并计算种群中所有个体的适应度，同时根据下面的公式初始化概率模型。名师资料总结-精品资料欢迎下载-名师精心整理-第 14 页，共 21 页 -10=120 ()NijNijV ijNV ijN其中，V ij为种群中个体i的变量 xj的值，N 为种群的规模。第二步：采用线性学习方式更新高斯分布的均值。设在t 代时，xj对应的高斯分布的均值为 jt，则有：1,1,2(1)()ttbestbestworstjjjjjxx

31、x其中 为学习因子，,1bestjx，,2bestjx和worstjx分别表示种群中最优个体、次优个体和最差个体所对应的 xj值。第三步：采用线性学习方式更新高斯分布的方差。设在第t 代时，xj对应的高斯分布的方差为tj，则有：110(1)()/KttjjjkkxxK其中，jkx为种群按适应度从大到小排名第1k的个体的xj值，x为选出的K 个较优种群的jkx的均值，即：11()/KjkkxxK第四步：根据更新的高斯分布产生样本。让我们用高斯概率模型来解决下面的函数优化问题：f(x)=x2,where-2.0 x 2.0Randomly Generate an Initial Populatio

32、n?Phenotype Fitness?Person 1:0.331 Fit:?名师资料总结-精品资料欢迎下载-名师精心整理-第 15 页，共 21 页 -?Person 2:-0.835 Fit:?Person 3:1.339 Fit:?Person 4:-0.300 Fit:?Person 5:0.488 Fit:?Person 6:-1.591 Fit:?Evaluate Initial Population?Phenotype Fitness?Person 1:0.331 Fit:0.110?Person 2:-0.835 Fit:0.697?Person 3:1.339 Fit:1.

33、793?Person 4:-0.300 Fit:0.900?Person 5:0.488 Fit:0.238?Person 6:-1.591 Fit:2.531 Select best 2 of 6,and the worst of 6?Phenotype Fitness?Person 1:0.331 Fit:0.110?Person 2:-0.835 Fit:0.697?Person 3:1.339 Fit:1.793?Person 4:-0.300 Fit:0.900?Person 5:0.488 Fit:0.238?Person 6:-1.591 Fit:2.531 Calculate

34、joint density function(Gaussian)名师资料总结-精品资料欢迎下载-名师精心整理-第 16 页，共 21 页 -?Phenotype Fitness?Person 1:0.331 Fit:0.110?Person 3:1.339 Fit:1.793?Person 6:-1.591 Fit:2.531?xavg=-0.184,=1.199Generate samples according to the Gaussian Distribution N(,2)Return to step 2 util the criterion is satisfied.五、分布估计算

35、法的研究热点与应用分布估计算法的研究方兴未艾，在算法设计、理论研究和实际应用方面仍需要做很多工作。作为一种新型的优化技术，分布估计算法的核心是解空间的概率模型，针对特定的优化问题，综合考虑搜索空间的结构、概率模型的学习算法、样本产生算法等，选择合适的概率模型，是发挥分布估计算法性能的关键所在。分布估计算法的本质是统计学习与进化算法的结合，通过统计学习手段对群体中的数据进行分析和建模，以挖掘搜索空间结构的相关知识，更好提高搜索效率。实际上，在进化计算领域，采用机器学习的方法分析数据、指导搜索已经成为设计新算法的趋势。但是值得注意的是，统计学习的引入也会给进化计算带来了新的时间和空间开销，因此在科

36、学研究或工程应用中，必须平衡统计学习和进化搜索的关系，设计算法的目的是更精确、快速的求解问题。下面将分别介绍分布估计算法研究领域的不足之处和研究热点：1)分布估计算法与其他搜索技术的混杂。智能混杂算法是当前智能优化算法的研究热点，可以融合多种优化算法的优势，提高算法的性能。目前文献中，已经出现了很多种基于分布估计算法的混杂算法，例如独立成分分析(ICA)与 EDA 的混杂，DE(Differentialevolution)名师资料总结-精品资料欢迎下载-名师精心整理-第 17 页，共 21 页 -算法与 EDA 的结合，传统遗传算法与EDA 的结合，再励学习加强EDA 算法的搜索能力，爬山算法

37、加强 EDA 的局部寻优能力，基于最大熵理论的EDA，采用集成学习方法增强EDA 性能等等。还有很多与 EDA 相关的混杂算法，这里不一一列举。其他智能手段与分布估计算法的混杂，将提高EDA 算法的搜索能力，更好的平衡算法的收敛性和群体多样性。2)分布估计算法的理论研究。分布估计算法的理论研究相对比较薄弱，并且目前的研究工作仅仅局限于二进制编码分布估计算法。目前的研究大都对EDA 算法进行了假设，例如算法迭代无限次、种群规模无穷大、概率模型精确反映问题结构，而在实际中这种假设是不成立的。理论研究的热点包括EDA 算法的收敛性分析、时空复杂性分析等。探讨EDA 算法与传统遗传算法之间的关系、深入

38、了解EDA 算法适合解决哪类问题(即问题结构与概率模型的关系)也是值得研究的问题。EDA 算法理论基础方面仍需要做很多的工作，以更好的分析和挖掘这种算法的潜力。3)针对多目标优化和多模态优化的分布估计算法的研究。多目标优化算法是当前进化计算领域的研究热点。随着分布估计算法的发展，以及该算法在解决问题时所表现的优越性能，人们开始着手设计解决多目标优化问题的分布估计算法。多目标 EDA 算法的基本思想是：将多目标进化算法(MOEA)中处理多目标优化的策略引入到EDA 算法中，并结合EDA 算法的特点设计求解 Parato解集更有效的算子。例如，mBOA 将 NSGA-II 中的选择策略与BOA 算

39、法相结合，在试验中用 mBOA 解决欺骗的多目标优化问题表现出了比NSGA-II 更好的性能；H.Li 等提出了混杂的多目标EDA 算法，采用了加权平均的方法将多目标问题转化为单目标问题；Laumanns等人将多目标进化算法SPEA2 的选择策略引入到BOA 中，用于解决多目标的01背包问题；D.Thierens等人的工作是将连续域的分布估计算法进行扩展，解决连续域多目标优化问题，采用混杂的高斯分布表示Pareto解集的分布，并设计了专门的截断选择算子，保持群名师资料总结-精品资料欢迎下载-名师精心整理-第 18 页，共 21 页 -体的多样性。在多模态优化方面，代表性工作是Pena.J.M等

40、人提出的 UEBNA 算法，用于解决二进制编码的多模态优化问题，其特点在于设计了贝叶斯网络的无监督学习策略，避免基因流失，试验分析表明了该算法在解决多模态优化问题的优良性能。4)强化分布估计算法的研究。分布估计算法的核心是概率图模型。但是我们可以看到，随着待解决问题的复杂化和概率图模型的复杂化，分布估计算法中概率模型的学习占用了大部分的时间和空间开销，这必然将成为分布估计算法发展的瓶颈。因此，强化和改进分布估计算法是该领域研究的难点和热点。这方面的发展趋势主要包括分布估计算法的并行化、稀疏的概率模型学习策略、针对特定问题的专家知识的引入和辅助建模。分布估计算法的并行化可以分为以下几种：a)概率

41、模型学习的并行化。这部分研究主要集中在概率模型比较复杂的BOA 算法方面。b)采样过程的并行化。群体中的个体是由概率模型随机采样产生的，一般的，个体之间是相互独立的，因此群体的产生可以并行进行。这方面的研究较少，主要有Pelikan 等研究了 BMDA 算法中采样的并行化。除此之外，进化计算领域广泛研究的基于多种群的并行化策略、Island 模型并行化、适应值函数的并行化计算等都可以引入到分布估计算法的研究领域。稀疏的概率模型学习策略的基本思想是，在BOA 算法中，贝叶斯网络的结构每隔若干代更新一次，贝叶斯网络的参数每一代都更新，这样由于参数学习的间复杂度远远低于结构学习，稀疏建模将提高分布估

42、计算法的效率。将先验知识引入到分布估计算法的概率模型学习中，主要工作包括：Baluja S。提出将专家知识引入到分布估计算法中，以减少概率模型学习带来的时间开销；Wright A.等通过“联结关系”检测算法，得到变量之间的相互关系，即概率模型的结构，在后续的进化过程中仅仅需要进行概率模型的参数学习。5)分布估计算法在非二进制编码领域的研究。EDA 算法源于对二进制编码的遗传算法的研究，因此大部分研究成果针对二进制编码的优化问题。实际上，大量的优化问题是多值离名师资料总结-精品资料欢迎下载-名师精心整理-第 19 页，共 21 页 -散的组合优化问题、排列优化问题和连续优化问题，特别是在排列优化

43、和连续优化问题上，EDA 算法的研究进展相对缓慢。连续域 EDA 算法研究的难点在于，对于复杂的多峰的、强耦合的、非线性连续优化问题，需要复杂的连续域概率图模型表示解空间分布，目前所采用的简单高斯分布、线性关系的高斯图模型仍有不足；但是复杂的概率图模型也会给算法的时间复杂性带来问题。6)分布估计算法的应用。试验分析表明分布估计算法在求解问题时表现出了比一般遗传算法更好的性能，应用分布估计算法解决工程和科学中的复杂优化问题具有很大的潜力。目前，分布估计算法已经在众多领域得到了成功的应用，例如，基于EDA 算法的汽车齿轮机械结构的优化设计、采用贝叶斯优化算法进行特征选择、不精确图形的模式匹配、基于

44、 EDA 算法的软件测试、EDA 算法在癌症分类中的应用、生物信息学中的特征提取、军事天线的优化设计等等。分布估计算法的应用已经渗透到了模式识别、运筹学、工程优化、机器学习和生物信息等众多领域。毋庸置疑，使用分布估计算法解决在科学研究和工程应用中碰到的优化问题将是未来几年的研究热点。六、总结分布估计算法是进化计算领域内一个崭新的分支，由于这种算法能够显式的表示变量之间的关系，能快速、准确、可靠的解决传统遗传算法束手无策的一类优化问题，在短短的几年时间内，引起了国际学术界的广泛关注，因此分布估计算法成为国际进化计算领域的研究热点，也逐渐成为解决实际工程优化问题的热门工具。分布估计算法是遗传算法和

45、统计学习的结合，通过统计学习的手段建立描述解空间个体分布的概率模型，然后对概率模型随机采样产生新的群体，如此反复进行，实现群体的进化。分布估计算法中没有传统的交叉、变异等遗传操作，通过对整个群体建立数学模型，直接描述整个群体的进化趋势，是对生物进名师资料总结-精品资料欢迎下载-名师精心整理-第 20 页，共 21 页 -化“宏观”层面上的数学建模。分布估计算法给人类解决复杂的优化问题提供了新的工具，它通过概率模型可以描述变量之间的相互关系，从而对解决非线性、变量耦合的优化问题更加有效。分布估计算法的研究将极大丰富混杂智能优化算法的研究内容，给优化问题的求解提供新的思路，具有巨大的科研价值和应用潜力。七、参考文献1 张军，詹志辉等 编著。计算智能。2 周树德，孙增圻。分布估计算法综述。自动化学报第33 卷，第2 期，2007年 2 月。3 网络资源，分布估计算法。名师资料总结-精品资料欢迎下载-名师精心整理-第 21 页，共 21 页 -