第8章 分布估计算法

第8章分布估计算法目录思想起源1发展历史2基本原理3改进研究4应用领域５分布估计算法的思想起源什么是分布估计算法?EstimationofDistributionAlgorithm(EDA)基于种群的新型进化算法思想起源于遗传算法算法的思想起源改进遗传算法的交叉操作和变异操作,防止破环积木块.采用概率模型和抽样的隐式形式产生新个体.X3X2X4Y3Y2Y4......交叉操作*X2X3*****是好模式,这个交叉操作破环了好模式分布估计算法与遗传算法的流程比较InitializationEvaluationSelectionCrossoverMutationInitializationEvaluationConstructionofProbabilisticModelSamplingofNewPopulation(GA)(EDA)SelectionTerminateEndYNTerminateEndYNStartStart分布估计算法的发展历史开山始祖PBIL:(1994Baluja)UMDA:(1996H.Miihlenbein&Paass)早期的算法专注于二进制编码MIMIC:(1997J.S.D.Bonet)COMIT:(1997S.Baluja)FDA:(1999HMUhlenbein)BOA:(1999M.Pelikan)逐渐扩展到连续分布估计算法PBILc(Sebag,1998)UMDAc(Larrañaga,P.,etal,2000)CEDGA(Q.Lu,2005)FWH&FHH(Tsutsuietal,2001)sur-shr-HEDA(N.Ding,etal,2006)分布估计算法的发展历史混合分布估计算法EDA与粒子群优化的混合EDA与遗传算法的混合EDA与差分进化算法的混合并行分布估计算法主从模式岛屿模型收敛性证明应用领域越来越广泛分布估计算法的通用流程RandomlygeneratedtheinitialpopulationP(0);t=0;WhilenotmettheterminationconditiondoBeginSelectasetofpromisingindividualsD(t)formthecurrentpopulationP(t);EstimatetheprobabilitydistributionoftheselectedsetD(t);GenerateasetofnewindividualsN(t)accordingtotheestimate;CreateanewpopulationP(t+1)byreplacingsomeindividualsofP(t)byN(t);t=t+1;end一个简单的分布估计算法例子1101110101010111100011011101010101111000ProbabilisticModel111111101111001101011.00.50.50.51.0CurrentPopulation一个简单的分布估计算法例子11011101010101111000ProbabilisticModel111111101111001101011.00.50.50.51.0CurrentPopulation11011101010101111000SelectedIndividuals一个简单的分布估计算法例子1101110101010111100011111110111100110101CurrentPopulation11011101010101111000SelectedIndividualsProbabilisticModel1.00.50.50.51.0一个简单的分布估计算法例子11011101010101111000CurrentPopulation11011101010101111000SelectedIndividualsProbabilisticModel1.00.50.50.51.011111110111100110101GeneratednewIndividuals基于高斯模型的EDA基于高斯模型的EDA的流程如下:第一步:随机生成初始种群P(0),初始化高斯模型的均值µ与方差σ.假设所有变量对应的高斯模型为:(N(µ1,σ1),N(µ2,σ2),…,N(µD,σD))其中D为待求解问题的维数.第二步:根据各维变量对应的高斯模型,抽样产生新种群T(t).第三步:从新种群中选择优秀个体集合S(t).第四步:计算S(t)在各维变量上的均值与方差,对原有的高斯模型进行更新.高斯模型的更新方法更新概率模型中的两个重要参数:均值和方差1,1,2(1)()ttbestbestworstjjjjjxxx110(1)(())/KttjjjkkxxK其中K为优秀个体的个数.xbest,1,xbest,2为最好的两个个体,xworst则为最差的个体.更新的方式多种多样,也可以直接用优秀个体的均值和方差替代原来的均值与方差.StartInitializeParametersgen=0InitializePopulationandEvaluatetheirfitenssgen=gen+1SelectExcellentIndividualsBuildHistogrammodelsGeneratenewoffspringandEvaluatetheirfitnessReplacementItisStop?EndYesNoPopsize,Parentsize,q0,k，LBOUND，UBOUNDLBOUNDUBOUNDLBOUNDUBOUNDLBOUNDUBOUNDXminXmaxLBOUNDUBOUNDLBOUNDUBOUND基于直方图概率模型的EDA基于链式概率模型的EDAMutualInformationMaximizationforInputClustering，MIMIC变量之间的关系是一种链式的关系，即在n维随机变量组成的链中，只有相邻的变量之间才有关系.联合概率密度在形式上产生变化:其中π是根据链式关系的一种排列.如何找出最优的π?12231()(|...)(|...)...(|)()nnnnnpXpXXXpXXXpXXpX12231ˆ()(|)(|)...(|)()iiiiinininpXpXXpXXpXXpX基于树状概率模型的EDACombiningOptimizersWithMutualInformationTrees,COMITCOMIT采用一种树状结构来描述两量变量之间的关系,表达能力比MIMIC更强.关键是如何确立变量之间树状关联关系的结构?采用机器学习领域中Chow和Liu提出的方法构造概率模型基于贝叶斯网络模型的EDA采用贝叶斯网络来描述变量之间概率依赖关系(其中节点代表变量，边表示变量之间的概率依赖关系)基于贝叶斯网络的联合概率密度为：x1x2x3x4x5x611121211()(|,...,)(|,...,)....(|)()nnnnPxPxxxPxxxPxxPx基于贝叶斯网络模型的EDA关键问题贝叶斯网络的结构如何确定?算法流程//功能：BOA伪代码procedureBOAD0GenerateNindividualsrandomlyl=1whilenotmetstoppingcriteriondoSe(l)selectse≤NindividualsfromDl-1accordingtoaselectionmethodConstructthenetworkBusingachosenmetricandconstraintsGenerateasetofnewindividualT(l)accordingtothejointdistributionencodedbyBCreateanewpopulationDlbyreplacingsomeindividualsfromDl-1withO(l)l=l+1endwhileendprocedure分布估计算法与遗传算法混合第t代种群采用遗传算法从种群中产生新种群采用分布估计算法从种群中产生新种群第t+1代种群分布估计算法与差分进化算法混合第一步:从种群中选出M个较优的个体，建立如下概率模型1ˆˆ()(;,)nkkkiiiipxNx第二步:产生一个0~1之间的随机值v，若v≤α，则按照DE方式产生新个体，否则按照EDA的方式取样产生新个体。第三步:若新个体的适应度大于原个体的的适应度则替换之第四步:若产生了足够数量的新种群则终止，否则执行第一步并行分布估计算法(一)种群级别并行化思路:将种群分成多个子种群，每个子种群在不同的机器上运行，然后各个子种群通过迁移等机制进行通信，达到综合信息的目的topologyUMDAMIMICEBNAPADA并行分布估计算法(二)适应度评估并行化思路:适应度评估通常是算法中最耗时的部分，因而,采用多台机器并行计算种群中的适应度可有效提高算法求解速度MasterSlaves主从模式并行计算并行分布估计法(三)概率模型构建并行化思路:设计复杂的概率模型需要较大的计算量,并行求解复杂概率模型可有效提高算法计算速度.其他并行机制采样的操作进行并行化混合并行机制分布估计算法的理论研究研究者说明MarkusHohfeld(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要达到全局收敛所需要的代数。TianshiChen(2007)[69]对早期的两个分布估计算法：UMDA和增量UMDA进行时间复杂度的分析。JiriOcenasek(2006)[70]提出用熵来度量分布估计算法收敛性的方法，并在此基础上分析了EDA终止的条件。……分布估计算法的应用领域(函数优化)有效地保护“积木块”，能够高效求解高维的复杂函数优化问题.在具有先验知识的情况下，可有针对地选择概率模型，从而设计出性能优越的分布估计算法.已成功应用于求解复杂的多峰函数,关联性强的复杂函数优化以及多目标函数优化.分布估计算法的应用领域(组合优化)应用（中文）英文参考文献旅行商问题TravelingSalesmanProblemLarrañaga(2002)[33]作业调度问题JobShopSchedulingProblemLarrañaga(2002)[33]、Jarboui(2008)[38]护士调度问题NurseSchedulingProblemU.Aickelin(2006)[39]网络控制NetworkControlH.B.Li(2008)[37]最大团问题MaximumCliqueProblemQ.F.Zhang(2005)[34]核反应堆燃料管理问题NuclearReactorFuelManagementS.Jiang(2006)[36]最大分集问题MaximumDiversityProblemWang(2009)[35]分布估计算法的应用领域(生物信息学及其它)分布估计算法在处理高维复杂问题时表现出良好的性能，非常适合于求解含有海量信息的生物信息学领域的问题。基因结构分析DNA微阵列数据的分类和聚类分析蛋白质结构预测与蛋白质设计分布估计算法在多目标优化、机器学习、模式识别和聚类分析等领域也取得了成功