第8章 分布估计算法

1、第8章分布估计算法,目录,思想起源,1,分布估计算法的思想起源,什么是分布估计算法?EstimationofDistributionAlgorithm(EDA)基于种群的新型进化算法思想起源于遗传算法算法的思想起源改进遗传算法的交叉操作和变异操作,防止破环积木块.采用概率模型和抽样的隐式形式产生新个体.,分布估计算法与遗传算法的流程比较,分布估计算法的发展历史,开山始祖PBIL:(1994Baluja)UMDA:(1996H.Miihlenbeint=0;WhilenotmettheterminationconditiondoBeginSelectasetofpromisingindividu

2、alsD(t)formthecurrentpopulationP(t);EstimatetheprobabilitydistributionoftheselectedsetD(t);GenerateasetofnewindividualsN(t)accordingtotheestimate;CreateanewpopulationP(t+1)byreplacingsomeindividualsofP(t)byN(t);t=t+1;end,一个简单的分布估计算法例子,一个简单的分布估计算法例子,一个简单的分布估计算法例子,一个简单的分布估计算法例子,基于高斯模型的EDA,基于高斯模型的EDA的流

3、程如下:第一步:随机生成初始种群P(0),初始化高斯模型的均值与方差.假设所有变量对应的高斯模型为:(N(1,1),N(2,2),N(D,D)其中D为待求解问题的维数.第二步:根据各维变量对应的高斯模型,抽样产生新种群T(t).第三步:从新种群中选择优秀个体集合S(t).第四步:计算S(t)在各维变量上的均值与方差,对原有的高斯模型进行更新.,高斯模型的更新方法,更新概率模型中的两个重要参数:均值和方差,其中K为优秀个体的个数.xbest,1,xbest,2为最好的两个个体,xworst则为最差的个体.,更新的方式多种多样,也可以直接用优秀个体的均值和方差替代原来的均值与方差.,Popsize

4、,Parentsize,q0,k，LBOUND，UBOUND,基于直方图概率模型的EDA,基于链式概率模型的EDA,MutualInformationMaximizationforInputClustering，MIMIC变量之间的关系是一种链式的关系，即在n维随机变量组成的链中，只有相邻的变量之间才有关系.联合概率密度在形式上产生变化:其中是根据链式关系的一种排列.如何找出最优的?,基于树状概率模型的EDA,CombiningOptimizersWithMutualInformationTrees,COMITCOMIT采用一种树状结构来描述两量变量之间的关系,表达能力比MIMIC更强.关键是

5、如何确立变量之间树状关联关系的结构?采用机器学习领域中Chow和Liu提出的方法构造概率模型,基于贝叶斯网络模型的EDA,采用贝叶斯网络来描述变量之间概率依赖关系(其中节点代表变量，边表示变量之间的概率依赖关系)基于贝叶斯网络的联合概率密度为：,基于贝叶斯网络模型的EDA,关键问题贝叶斯网络的结构如何确定?算法流程,分布估计算法与遗传算法混合,分布估计算法与差分进化算法混合,第一步:从种群中选出M个较优的个体，建立如下概率模型,第二步:产生一个01之间的随机值v，若v，则按照DE方式产生新个体，否则按照EDA的方式取样产生新个体。,第三步:若新个体的适应度大于原个体的的适应度则替换之,第四步:

6、若产生了足够数量的新种群则终止，否则执行第一步,并行分布估计算法(一),种群级别并行化思路:将种群分成多个子种群，每个子种群在不同的机器上运行，然后各个子种群通过迁移等机制进行通信，达到综合信息的目的,并行分布估计算法(二),适应度评估并行化思路:适应度评估通常是算法中最耗时的部分，因而,采用多台机器并行计算种群中的适应度可有效提高算法求解速度,主从模式并行计算,并行分布估计法(三),概率模型构建并行化思路:设计复杂的概率模型需要较大的计算量,并行求解复杂概率模型可有效提高算法计算速度.其他并行机制采样的操作进行并行化混合并行机制,分布估计算法的理论研究,分布估计算法的应用领域(函数优化),有效地保护“积木块”，能够高效求解高维的复杂函数优化问题.在具有先验知识的情况下，可有针对地选择概率模型，从而设计出性能优越的分布估计算法.已成功应用于求解复杂的多峰函数,关联性强的复杂函数优化以及多目标函数优化.,分布估计算法的应用领域(组合优化),分布估计算法的应用领域(生物信息学及其它),分布估计算法在处理高维复杂问题时表现出良好的性能，非常适合于求解含有海量