第8章-分布估计算法.ppt

,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,Company,Logo,*,Click to edit Master title style,第,8,章分布估计算法,目录,思想起源,1,发展历史,2,基本原理,3,改进研究,4,应用领域,2,分布估计算法的思想起源,什么是分布估计算法,?,Estimation of Distribution Algorithm(EDA),基于种群的新型进化算法,思想起源于遗传算法,算法的思想起源,改进遗传算法的交叉操作和变异操作,防止破环积木块,.,采用概率模型和抽样的隐式形式产生新个体,.,3,分布估计算法与遗传算法的流程比较,4,分布估计算法的发展历史,开山始祖,PBIL,:(1994 Baluja),UMDA,:(1996 H.Miihlenbein&Paass),早期的算法专注于二进制编码,MIMIC,:(1997 J.S.D.Bonet),COMIT,:(1997 S.Baluja),FDA,:(1999 HM Uhlenbein),BOA,:(1999 M.Pelikan),逐渐扩展到连续分布估计算法,PBILc,(Sebag,1998),UMDAc,(Larraaga,P.,et al,2000),CEDGA,(Q.Lu,2005),FWH&FHH,(Tsutsui et al,2001),sur-shr-HEDA,(N.Ding,et al,2006),5,分布估计算法的发展历史,混合分布估计算法,EDA,与粒子群优化的混合,EDA,与遗传算法的混合,EDA,与差分进化算法的混合,并行分布估计算法,主从模式,岛屿模型,收敛性证明,应用领域越来越广泛,6,分布估计算法的通用流程,Randomly generated the initial population,P,(0);,t,=0;,While,not met the termination condition,do,Begin,Select a set of promising individuals,D,(,t,)form the current population,P,(,t,);,Estimate the probability distribution of the selected set,D,(,t,);,Generate a set of new individuals,N,(,t,)according to the estimate;,Create a new population P(t+1)by replacing some individuals of,P,(,t,)by,N,(,t,);,t,=,t,+1;,end,7,一个简单的分布估计算法例子,8,一个简单的分布估计算法例子,9,一个简单的分布估计算法例子,10,一个简单的分布估计算法例子,11,基于高斯模型的,EDA,基于高斯模型的,EDA,的流程如下,:,第一步,:,随机生成初始种群,P,(0),初始化高斯模型的均值,与方差,.,假设所有变量对应的高斯模型为,:,(,N,(,1,1,),N,(,2,2,),N,(,D,D,),其中,D,为待求解问题的维数,.,第二步,:,根据各维变量对应的高斯模型,抽样产生新种群,T,(,t,).,第三步,:,从新种群中选择优秀个体集合,S,(,t,).,第四步,:,计算,S,(,t,),在各维变量上的均值与方差,对原有的高斯模型进行更新,.,12,高斯模型的更新方法,更新概率模型中的两个重要参数,:,均值和方差,其中,K,为优秀个体的个数,.,x,best,1,x,best,2,为最好的两个个体,x,worst,则为最差的个体,.,更新的方式多种多样,也可以直接用优秀个体的均值和方差替代原来的均值与方差,.,13,Popsize,Parentsize,q,0,k,，,LBOUND,，,UBOUND,基于直方图概率模型的,EDA,14,基于链式概率模型的,EDA,Mutual Information Maximization for Input Clustering,，,MIMIC,变量之间的关系是一种链式的关系，即在,n,维随机变量组成的链中，只有相邻的变量之间才有关系,.,联合概率密度在形式上产生变化,:,其中,是根据链式关系的一种排列,.,如何找出最优的,?,15,基于树状概率模型的,EDA,Combining Optimizers With Mutual Information Trees,COMIT,COMIT,采用一种树状结构来描述两量变量之间的关系,表达能力比,MIMIC,更强,.,关键是如何确立变量之间树状关联关系的结构,?,采用机器学习领域中,Chow,和,Liu,提出的方法构造概率模型,16,基于贝叶斯网络模型的,EDA,采用贝叶斯网络来描述变量之间概率依赖关系,(,其中节点代表变量，边表示变量之间的概率依赖关系,),基于贝叶斯网络的联合概率密度为：,17,基于贝叶斯网络模型的,EDA,关键问题,贝叶斯网络的结构如何确定,?,算法流程,18,分布估计算法与遗传算法混合,19,分布估计算法与差分进化算法混合,第一步,:,从种群中选出,M,个较优的个体，建立如下概率模型,第二步,:,产生一个,01,之间的随机值,v,，若,v,，则按照,DE,方式产生新个体，否则按照,EDA,的方式取样产生新个体。,第三步,:,若新个体的适应度大于原个体的的适应度则替换之,第四步,:,若产生了足够数量的新种群则终止，否则执行第一步,20,并行分布估计算法,(,一,),种群级别并行化,思路,:,将种群分成多个子种群，每个子种群在不同的机器上运行，然后各个子种群通过迁移等机制进行通信，达到综合信息的目的,21,并行分布估计算法,(,二,),适应度评估并行化,思路,:,适应度评估通常是算法中最耗时的部分，因而,采用多台机器并行计算种群中的适应度可有效提高算法求解速度,主从模式并行计算,22,并行分布估计法,(,三,),概率模型构建并行化,思路,:,设计复杂的概率模型需要较大的计算量,并行求解复杂概率模型可有效提高算法计算速度,.,其他并行机制,采样的操作进行并行化,混合并行机制,23,分布估计算法的理论研究,研究者,说明,Markus Hohfeld(1997)63,证明,PBIL,在解决线性的二进制优化问题时，可以收敛到全,局最优解，解非线性问题可能会陷入局部最优。,H.Muhlenbein(1998)64,对,UMDA,的收敛性进行分析，假设种群无穷大。,H.Muhlenbein(1998)65,对,FDA,的收敛性进行分析。,M.Pelikan(2001)66,对,BOA,解决,OneMax,问题的收敛性进行分析。,Q.F.Zhang(2004)67,对种群规模无穷大的,EDA,进行数学建模，分析了,EDA,算法,达到全局收敛的一些条件。,R.Rastegar(2005)68,分析了种群规模无穷大的,EDA,要达到全局收敛所需要的代,数。,Tianshi Chen(2007)69,对早期的两个分布估计算法：,UMDA,和增量,UMDA,进行时,间复杂度的分析。,Jiri Ocenasek(2006)70,提出用熵来度量分布估计算法收敛性的方法，并在此基础,上分析了,EDA,终止的条件。,24,分布估计算法的应用领域,(,函数优化,),有效地保护“积木块”，能够高效求解高维的复杂函数优化问题,.,在具有先验知识的情况下，可有针对地选择概率模型，从而设计出性能优越的分布估计算法,.,已成功应用于求解复杂的多峰函数,关联性强的复杂函数优化以及多目标函数优化,.,25,分布估计算法的应用领域,(,组合优化,),应用（中文）,英文,参考文献,旅行商问题,Traveling Salesman Problem,Larra,aga(2002)33,作业调度问题,Job Shop Scheduling Problem,Larra,aga(2002)33,、,Jarboui(2008)38,护士调度问题,Nurse Scheduling Problem,U.Aickelin(2006)39,网络控制,Network Control,H.B.Li(2008)37,最大团问题,Maximum Clique Problem,Q.F.Zhang(2005)34,核反应堆燃料管理问题,Nuclear Reactor Fuel Management,S.Jiang(2006)36,最大分集问题,Maximum Diversity Problem,Wang(2009)35,26,分布估计算法的应用领域,(,生物信息学及其它,),分布估计算法 在处理高维复杂问题时表现出良好的性能，非常适合于求解含有海量信息的生物信息学领域的问题。,基因结构分析,DNA,微阵列数据的分类和聚类分析,蛋白质结构预测与蛋白质设计,分布估计算法在多目标优化、机器学习、模式识别和聚类分析等领域也取得了成功的应用,.,27,Thank you!,28,