分布估计算法及其性能研究

1、文章编号:1671-8836(2005)S2-0125-04分布估计算法及其性能研究丁才昌,方 勃,鲁小平(武汉大学计算机学院,湖北武汉430072)摘 要:在传统的遗传算法中,不合适的的参数设置会降低解的质量,于是在解决一些优化问题时传统的遗传算法被分布估计算法所取代.将分布估计算法按其复杂性归纳成几种模型,分别描述了它们的实现方法和求解问题的能力和效率.关 键 词:分布估计算法;概率模型;组合优化问题中图分类号:TP301 文献标识码:A一些研究者从概率统计的观点出发,将构造性模型引入进化算法的研究,形成一类基于概率分布的进化算法,称为分布估计算法(EstimationofDis-trib

2、utionAlgorithms),简称为EDAs.本文介绍分布估计算法的研究概况,分析其产生的背景和基本思想.在此基础上,按照算法模型的复杂度将其归纳成几种类型.分别分析了它们的实现方法和求解问题的能力和效率.具有挑战性的难题,对于一定规模的问题,此组合数将是一个天文数字.2 分布估计算法2.1 一阶分布估计算法为了克服GA因交叉重组导致的连锁问题,人们提出是否可以不使用重组操作,而是通过从优选的解集合中提取信息,然后利用这种信息的分布概率产生新的解,由此实现算法的连锁学习.这种将构造性概率模型引入进化算法的思想形成概率分析进化算法的理论依据.EDAs算法的概念最早可以追溯到Ackley于19

3、87年提出的一个学习算法,在此算法中他引入了一个具有重要意义的数据结构即基因向量,通过来自群体的正负反馈信息操作此向量.文中有一个直观的比拟,即把长度为L的基因向量比做由L个成员组成的政府,群体数据比做选民的投票结果,依据此结果评判群体(选民)对向量(政府)的满意程度.这一算法的意义是首次应用了群体中基因的概率分布分析和评价解的质量.Syswerda在文献2中提出了/基于基因位的模拟交叉0(bit-basedsimulatedcross,BSC)操作来产生新群体的思想.BSC操作利用群体级的统计方法替代GA的交叉重组,其基本思想描述如下:对于当前群体,统计染色体中第i个基因位为1的个体数量;同

4、样也统计第i个基因位为0的个体数量.对11 连锁学习问题收稿日期:2005-09-20126武汉大学学报(理学版)第51卷这些数据和适应度函数值加权统计,作为产生后代的依据,即按照统计值概率分配新个体的基因位值为1或0.BSC实际上把GA的选择和交叉结合成一个操作,其创新意义是利用样点边缘概率分布计算取代GA的重组操作来产生新的群体.Baluia巧妙地结合上述两者的思想,构思了利用一个概率向量表示群体的染色体,并用它记录群体在结构中每一基因位置为/10或为/00的比例,初始概率向量的每一位值为0.5(表示该基因位为0和1的概率均等),通过搜索过程逐步朝向0或1逼近.并利用此向量产生新的个体,再

5、依据这些新个体的适应度值修改概率向量,使之最后逼近最优解.这种称为/基于群体的增量学习0(population-basedincreasedlearning,PBIL)的算法,一般被认为是概率分析算法的原型,它对EDAs的研究和发展具有重要意义.为此本文作者用C伪代码给出基本的PBIL算法如下:/*初始化概率向量Pfor(i=1;i=L;i+)Pi=0.5;while(NOTTERMINATIONCONDITION) /*利用概率向量产生N个样点,计算样点的适应度;for(i=1;i=1;i-)for(j=1;j=L;j+)Pj=Pj*(1.0-)+Best-solution-vec-tors

6、ij*(); return(best-solution-vectors)算法中的参数M表示排序后的前M个解用于修改概率向量;表示学习速率,它决定完成搜索过.Harik3等人提出了压缩遗传算法(compactgeneticalgorithm,CGA)的概念.CGA算法的基本思路和PBIL类似,用一个概率向量P(长度为染色体长度L)模拟群体的性质,采用基于基因位的交叉模拟染色体的交叉.概率向量各元素Pi(1iL)的初值为0.5,表示当前群体中染色体包含的二进制位/00和/10的比例服从均匀分配,若采用淘汰选择,则依据概率向量选择两个个体A和B,评价A和B的适应度,分辨出其中适应度较大者winner

7、和较小者loser,然后将winner按基因位和当前的概率向量元素进行交叉.EDAs算法中的一个重要问题是连锁学习即如何识别和混合高阶的构造块,这一问题引出EDAs中建立分布和学习分布的两个基本问题.首先研究并提出高阶连锁学习的EDAs算法是称为/相互信息最大输入聚合0的算法(mutualinformationmax-imizinginputclustering,MIMIC算法)基本思想如下:设4.该算法的(1)(2)P(X)=P(X1,X2,Xn)是随机变量集合X=(X1,X2,Xn)上的联合概率分布,即有:P(X)=P(X1|X2,Xn)P(X2|X3,Xn)P(Xn-1|Xn)P(Xn)

8、(3)若式(3)中只考虑序偶条件概率P(XI|Xi)和无条件概率P(XI),则可定义PcP(X)=PcP(Xm1,Xm2,Xnm)的分布为P(X)=PcP(Xm1|Xm2)PcPPcXm2|Xm3),PcP(Xnm-1|Xnm)PcP(Xnm)(4)(4)式中的P=(m1,m2,mn)是集合(1,2,n)上的一个排列.为使PcP(X)和分布P(X)最为接近,只需保证Kullback-Liebler散度D(P(X)PcP(X)第S2期丁才昌等:分布估计算法及其性能研究127D(P(X)PcP(X)=-h(P(X)+h(Xm1|Xm2)+h(Xm2|Xm3)+h(Xnm-1|Xnm)+h(Xnm)

9、(5)(5)式中的h表示熵,由于式中第1项与排列P无关,最优的P是分布P(X)中序偶熵之和最小的排列.基于这一原理,MIMIC通过简单的贪婪算法寻找最佳的排列P,然后依据此排列的分布产生新的样点,如此重复,直到满足终止条件.MIMIC的实现过程可以用一个链式有向图表示排列顺序,注意这种图除首结点和尾结点外,其他结点的入度和出度都为1.图中每一结点表示一个变量,对应一个染色体的一个基因位.产生新样点时,首先利用单变量统计频度产生它的第1个基因,所有其它的基因则通过计算其上一基因的条件概率依次生成,实际上这是从(5)式中最后一项开始往前计算.MIMIC的特点是基于双变量边缘分布和贪婪搜索的连锁学习

10、算法.和MIMIC类似的另一个基于双变量边缘分布的EDAs算法是用树结构表示分布的算法;这种称为相关树(dependencytree)的结构使得树中父子结点的相关信息最大.树中根结点的值首先利用单变量边缘分布产生,树中其它的叶结点的值则依据其父结点的条件概率产生.事实上,链是一种特殊的树,因此比较MIMIC的链式分布,树型结构分布的精确度更高.此外,这种算法可以使用一种多项式复杂性的最大分支算法搜索最好的相关树.择评价分布和学习分布产生新的后代.如果用图表示分布模型,我们发现,一阶EDAs是一个边集为0的图;而二阶EDAs则对应有向链、有向树和有向森林,它们的共同特点是结点(变量)的入度不超过

11、1.自然地,人们想到可以用更为复杂的图结构来表示多变量间的相关性,以求解高阶问题.Bayes优化算法5(Bayesianoptimalalgorithm,BOA)便是在这种背景下产生的EDAs算法.Bayes网络是一无环有向图,它可以对所给的数据进行描述,又可以产生与所给定数据性质相同的数据,因此常用于对离散或连续变量的多项式数据建模6.Bayes网络图中一个结点代表一个变量;两个结点之间的边代表变量之间的关系,若结点Xi存在一条指向Xj的边,则称Xi是Xj的父结点.上述Bayes网络可以用数学公式表示如下:P(X)=i=1FP(Xni|FX)i(6)式(6)中X=(X1,X2,X3,Xn)是

12、随机变量向量,FXi表示结点Xi的父结点(即有边指向Xi的结点)集合;P(XiFX)是Xii的条件概率;P(X)/P(是联合概率分布.由Bayes规则可知:P(XiFXi)=P(Xi,FXiFX)i(7)3 分布估计算法研究趋势EDAs算法的研究尽管起步时间不长,但理论和应用表明它是一类很有前途的优化进化算法.在进化计算领域内,称能够快速(quickly)、可靠(relia-bly)和精确(accurately)求解问题的算法为/胜任算法0(competentalgorithm),因此EDAs总的研究趋势是朝这一目标发展.本文认为比较其他的进化算,128武汉大学学报(理学版)第51卷面的研究会

13、有更大的进展.EDAs的理论研究分为建立概率分析模型和利用模型搜索结构两个方面,对应上述算法中的第3和第4步骤.研究适合多变量的概率分析模型将是EDAs重要的题目,目前理论上对Bayes网络的研究十分活跃,如何将这些成果应用于EDAs值得做进一步的工作.EDAs中的各种参数的选择(如群体规模,选择机制和选择比例等)等等都是需要研究的问题.总之,EDAs算法的研究还处于起步阶段,无论是模型、搜索算法,还是实验方法都还有许多有待解决的问题.这一领域开辟新的研究方向.参考文献:1 AckleyDH.AConnectionistMachineforGeneticHill-ClimbingM.Bosto

14、n:KluwerAcademicPub-lisher,1987.2 SyswerdaG.SimulatedCrossoverinGeneticAlgo-rithsM.SanMateo,CA:MorganKaufmann,1993.3 HarikG,GoldbergDE.LinkagelearningA.In:BelewR.FoundationsofGeneticAlgorithmsC.SanMateo,CA:MorganKaufmann,1996.4 BonetJD.MMIC:FindingOptimabyEstimatingProbabilityDensitiesM.Cambridge:Th

15、eMITPress,19975 PelikanM,GoldbergDE.BOA:TheBayesianOpti-mizationAlgorithmR.Urbana:UniversityofIllinoisatUrbanaChampaign,IlliGALGeneticAlgorithmLa-boratory,1998,(5):55-67.6 HeckermanD.LearnBayesianNetwork:TheComb-inationofKnowIedgeandStatisticalDataJ.MachineLearning,1995,20(5):197-204.7 PelikanM.ASurveyofOptimizationbyBuildingandUsingProbabilisticModelsR.Urbana:Univer-sityofIllinoisatUrbanaChampaign,IlliGALGeneticAlgorithmLabora