estimationofdistributionalgorithm分布估计算法.ppt

,主要思想就是把自然进化算法和构造性数学分析方法相结合,以指导对问题空间的有效搜索。分布估计算法本质上是一种基于概率模型的新型进化算法,遗传算法与统计学习相结合,是自然计算的又一典型实现模式。它通过对当前找到的较优个体集合建立概率模型来引导算法下一步的搜索范围,并从所获得的较优解的概率分布函数中抽样产生出新的个体。2分布估计算法概述个体模拟生物个体而对问题中对象的一种称呼。种群由若干个个体组成。概率模型用于描述取值域中优秀个体分布情况的一系列函数或其他数学工具(包括概率密度函数、条件概率、边缘概率等等)。3遗传算法的不足构造块:群体中高于平均适应度的低阶、短距离的模式,它们是构成问题解的基本部分。连锁问题:构造块中的确定位之间存在连锁依赖关系,而简单遗传算法在进行交叉操作时不具备分辨和学习构造块中这种关系的能力,因此不可避免的造成构造块的损坏,把这种损坏称之为连锁问题。结论:由于高阶、长距离构造块在交叉操作时的损坏概率较大,简单遗传算法在求高阶、长距离构造块的问题时,容易陷入局部最优或发生早熟。4分布式估计算法与传统遗传算法遗传算法是对于个体进行遗传操作(交叉、变异等),“微观”层面模拟生物的进化。分布估计算法是对于整个群体的分布建立一个概率模型,通过这个概率模型来描述进化的方向,是“宏观”层面的模拟。5分布式估计算法与传统遗传算法图EDA算法与GA算法的流程对比6分布式估计算法基本流程步骤1:初始群体,并对每一个个体进行估值(适应度值计算);步骤2:根据个体估值,按照一定的选择策略从群体中选择较优的个体;步骤3:根据选择的个体估计概率分布,建立相应的概率模型;步骤4:根据上一步估计得出的概率分布,采样产生新一代个体,并重新对每一个新个体进行适应度估值;步骤5:如果某准则满足,则算法停止;否则,、随机抽样技术,是一种随机模拟方法,以概率和统计理论方法为基础的一种计算方法,是使用随机数(或更常见的伪随机数)来解决很多计算问题的方法,实现统计模拟或抽样。基本思想:要生成分布函数为F(x)的随机数,可先生成U(0,1)的随机数U,则可以得到随机数9基于不同概率模型的EDA离散的分布估计算法变量无关的EDAEDA的最简单情况是假设所有的随即变量都是独立的。也就是所有基因之间没有关系,个体使用二进制编码,即:从群体中学习离散随机变量概率分布的算法比较简单,这是一个基于基数的方法。在一个离散随机变量的分布上的采样可以通过轮盘赌的方式实现10