基于贝叶斯优化构建DBN结构优化算法

第29卷第10期系统工程与电子技术Vol, 29 No. 102007年10月Systems Engineering and ElectronicsOct.2007文章编号1001-506X(2007)10-173206基于贝叶斯优化构建DBN结构优化算法肖秦琨'，以，高嵩',高晓光2(1. 西安工业大学电子信息学院，陕西西安710072;2.西北工业大学电子信息学院，陕西西安710072)摘要: 针对动态贝叶斯网络(DBN)结构学习问题,提出了一种基于贝叶斯优化(BOA)的DBN结构寻优算法。首先,从传统进化优化机制的基本理论和基本操作入手,刻划了基于概率模型进化算法的基本思想。其次，通过描述基于概率模型进化算法的构困基础,引出了DBN结构学习机制，即基于BOA的DBN结构寻优算法。BOA算法的关键是根据优良解集学习得到DBN,以及根据DBN推理生成新个体，前者更为重要,依据基于贪婪机理的遗传算法解决动态网络学习,再应用DBN前向模掀完成后一步。仿真结果表明了该算法的可行性。关键词:动态贝叶斯网络;贝叶斯优化算法;结构学习;遣传算法;前行模拟中图分类号: TP 18文献标志码: AConstructing DBN structure based on BOAXIAO Qin-kun'", GAO Song'，GAO Xiao-guang'(1. School of Electromics and Information Engineering, Xi'an Technological Univ, , Xi'an 710072 , China;2. School of Electronics and Informatiom Engineering, Northwestern Polytechrical Univ. , Xi'an 710072 , China)Abstract: An optimal algorithm for dynamic Bayesian networks(DBN) based on Bayesian optimal algorithm(BOA) is developed for learning and constructing DBN structure. Firstly, some basic theories and concepts ofthe probability model evolutionary algorithm are introduced, Secondly, the basic mode for constructing DBN di-agram are described and the mechanism of DBN structure learning based on BOA is clarified. The BOA includestwo parts of main technique, one is to gain the structure and parameter of DBN in term of good solutions, theanother is to produce new group according to DBN. The learning of DBN is done by genetic algorithm based onthe greed mechanism. The inference of DBN is done by a forward- simulation algorithm, Matlab simulation re-sult demonstrates the proposed algorithm is effective.Keywords: DBN; BOA; structure learning; genetics algorithm; forward-simulation algorithm0引言竞争学习机制引入进化算法的自主学习,实验表明,在作业车间调度(JSP)、旅行商等问题的解决上显示了一定的优越贝叶斯网络结构学习是一个组合优化问题,而引人时性。类似的还有Harik等提出的紧致遗传算法(CGA),间关系的动态贝叶斯网络(dynamic Bayesian networks,Muhlenbein的-元边緣分布算法(UMDA).以及分布分解DBN)结构学习,由于其动态性和时效性,使得学习变得更算法(FDA)等。而基于贝叶斯网络学习的贝叶斯优化算加复杂[*] ,这就需要寻找合理且快速的搜索方法。法54)(Bayesian optimization algorithm, BOA)将基于概率研究搜索过程中自动获取问题的固有知识、积累有关.模型进化算法与图形模型相结合,不仅具有运行时占用内搜索空间的属性,并自适应地控制搜索过程,从而得到最优存空间少的特点,且可有效的避免早熟现象,鉴于此,本文解或次优解的启发式搜索算法一直是众多 学者热衷的研究提出基于BOA的DBN结构寻优算法,首先从概率模型进课题。近年来,以遗传算法为基础的基于概率模型进化算化算法的机理人手,进而讨论基于BOA结构学习的总体思法的研究,引起了国内外的广泛兴趣,最具代表的工作有路,最后将问题集中在DBN网络学习与推理的具体算法Baluja 提出的基于种群的增强学习算法(PBIL)4,将简单上,即中国煤化工k前向模拟网络推理收稿日期:2006 -07 - 30;修回日期:2006-10-21.YHCNMHG基金项目:国家自然科学基金重大项目(90205019);|陕西省科研专项(陕西省教育厅07JK277)资助课题作者简介:肖秦琨(1974-),男,讲师,博t,主要研究方向为动态贝叶斯网络,人工智能. E-mail: xingin10000@163. com第10期肖秦琨等:基于贝叶斯优化构建DBN结构优化算法●1733●模型。从宏观上讲,基于图形模型的进化优化机制是基于概1基于 概率模型的进化算法率模型的遗传算法的进一步发展,前者更强调图形模型的建立、度量和新解的生成，后者强调种群分布的计算和估由模式定理及积木块假没可知,进化算法成功的关键计,我们后面讨论的用于DBN结构寻优的的BOA算法即是:好的积木块能够良性地成长(growth)与混合(mixing)。为图形模式下的进化算法。因面传统的进化算法,例如简单遗传算法,对于积木块集中2DBN结构寻优算法概述地驻留于某些个体串的待优化问题更加有效.而当积木块几乎散布于所有个体串的待优化问题效率就比较差。所无论是在静态的贝叶斯网路或动态贝叶斯网络结构以,探索问题的固有结构,以便利用这些信息确保积木块合中,如果对变最的父节点和子节点个数不加限制,这样的園适地累积,就显得非常重要,而且成为构建新型进化机制的形模型就是贝叶斯网络图(Bayesian network, BN).基于切入点。其中方法之一就是利用优良解的概率樸型指导搜BN的进化算法被称为贝叶斯优化算法，简称BOA,同样，索空间的进一步探索,以代替简单遗传算法中的交叉、变异我们可以将其推广,以用于DBN的结构寻优。遗传算子。这就是基于概率模型进化算法的思想来源。为BOA是利用BN匹配进化种群的优良觶集而产生新的了与传统遗传算法的流程比较,给出基于分布估计模式的染色体来体现种群的进化,它适应于问题候选解编码长度固进化算法基本流程见圈1.联结问题(inkage problem)是定、等位基因是有限字母的各类问题,特别有利于具有可加指积木块被破坏问题,最早由Harik 和Goldberg 提出,为性的问题优化，而DBN度量机制的可加性恰满足于这一点。了防止对重要解所在积木块的破坏，主要有两大技术(0,基于BOA的DBN寻优对于种群的进化主要体现在以(1)改变解的表示或改进重组算子;(2)从有前途的个体集下4步;(1)确定优良解集:可利用各种选撣机制从当代种群合(或称为优良解集)中提取信息产生新的个体。第- -种技中选出优良解集。(2)寻找动态网络图:根据优良解集的数术的代表性工作有Goldberg提出的混乱遗传算法(messy.据信息确立基于某种度量值比较好的网络图。(3)产生 新的genetic algorithm, MGA),在MGA中,个体由每个分量的候选解;利用网络图的联合分布产生新的个体集。(4)下代位置与取值共同表示,位暨可以不按次序排列,但并不是所种群的产生:以新的个体集代替 上代种群的某些染色体来更有分量都在个体的表示中出现。由于MGA操作的对象既新种群为新- -代种群。 以上4步反复执行,直到满足算法终有个体,又有模式,所以丧失了只操作个体的隐并行性。同止条件。算法的终止条件可以是运行到-定的代数、种群中，样地,各种重新排序(reordering)和映射(mpping)算子的已具有足够好的解或者算法的进化速度已经非常慢面不值应用,虽然有助于联结问题,却降低了进化的速度或削弱了得继续运行。基于BOA的DBN寻优基本步骤描述如下，选择的竞争性,面引起早熟(premature)现象。有关进化算步骤1随机产生初始种群 P(0)。法的大多数文献集中于第- - 种技术,而体现第二种技术的步骤2从P(1)中选择高于平均适应值的个体作为优进化算法,正是致力于加强进化算法的进化机制研究,以提良解集S(). .高进化算法的适应性、智能性及有效性的贝叶斯优化方法。的DBN.步骤3依据某种度量及约柬构建匹配于 s(t)C数编码D步粟4根据DBN编码的联合分布产生新申集o().随机初始化第1-0代种群步骤5由0(t)代替P(1)中的某些解集,生成1+1种.群P(r+1).[第代种群P(O中个体适应值的评估]步骤6如果不满足算法的终 止准则,转向步骤2.L 从P0种选择优良个体集)上述算法说程可以形象地描述如图2.由图2知，估计&0)的概率分布00)BOA的关键是根据优良解集学习得到DBN,以及根据DBN推理生成新个体。下面我们来详细讨论这两个步骤。根据上述分布产生串集00从O(0代禁P0)中的S0)初始种群 _优良解集动态贝叶斯网络新的种群, 0010011000 1001001 100I 100001 1101010( 100000 1001101011001 厂10011100110010000011001001 10011011011000101100是否满足00001000100001 1001终止进化准则2>100100000100000001中国煤化1.1011000是(结束)-P1BMA4)TYHCN M H GAceI2)图1基于概率模型的进化算法的基本施程图圈2基于BOA的DBN结构学习算法●1734●系统工程与电子技术第29卷.(6)返回(2)。3学习DBN3.3基于贪婪机理 的遗传算法3.1概述如前所述,DBN包含两部分网络框架B=(B,B_),它成功应用基于BOA寻优的关键就是动态贝叶斯网络们分别叫作先验网络和转换网络,如图示。这里用两条染的学习,DBN的学习同静态网络一样,主要包含两个方色体C,C.分别表示先验网络B。和B- ,而G,C.的组合面[0]:(1)结构的学习。对于静态网络，只需要确定某一个编码了一个完整的DBN.另外,一个DBN结构可表示成独立的网络结构,而对于动态网络而言，则需要同时确定链状的形式,每-列某些结点是令- -列某些结 点的父结点。BO和B→网络结构,→旦结构确定,网络结构定义的相应(1)编码(Encoding)图3是时间切片0、1.1+1上的网变量的条件独立与依赖关系也就确定了;(2)参数的学络结构简图.在转换网络中,t时刻的所有结点没有父结点。习。对于完整的贝叶斯网络,其结构所定义的关系必须简言之,我们只编码在时刻t+ 1的结点,图3中,每组第一利用条件概率值确定。所以确定结构以后,需要进行条个成员(基因)是变量X,其他成员(等位基因)是X的父结件概率的学习。在给定度量下学习一个网络的结构是点,记为II (x)。尽管图形法更加简明,染色体~基因~等一个复杂的组合问题。实际上,已经证明,对于多数贝位基因的编码法使得遗传操作更加方便，等位基因编入了叶斯或者非贝叶斯度量,搜索最优网络是NP难的C0]。变量的位置.(Co,C.)合在-起可被看作是表示DBN的一-这是由于BN的数目随着节点数目的增加成天文数字增个染色体,其中每一组是- 个基因,[(x)是等位基因。同.加，例如10个节点的BN,虽然边数最多为45条,等价类样,如果任-个基因位用0或1表示，我们可以将(C,C.)计数为: 118902054495975141,相应网络图的搜索规模表示为二进制编码的基因(见图4)。为:4175163455710941233.因此,为了迅速搜索到质量高的DBN,-方面可以根据x问题的复杂性以及问题的有关先验信息限制其搜索空间,这(x([0]) G :01x101x[](x[+1])0.0.01是“硬”减少搜索空间。另一方面就是“软”减少搜索空间。先验网络编码父节点利用局部结构学习网络结构,即利用决定树、决定图进行学在后，子节点在前( x[]习,或者采取增加网络图边的方法" ,即每增加一条边,便计10算网络图的度量值，进行比较观察,确定是否将这条边加入.:+1]x(1+1]x[0]x()]+1107到网络图中,这是众多文献所采用的贪婪搜索算法。x[0] )转移网络编码(父节点(x1[+1)3.2贪婪算法贪婪算法执行三个基本图形操作,以提高当前网络的先验网络转移网络质量,直到操作不再能提高网络质量。网络结构可以被初图3 DBN 及其编码始化为没有边。在贝叶斯优化算法中,初始结构可以被设所表示的意义置为上一-代学习得到的结构。本章中,网络在每一代都是| 00 x[0], x[0]均不为x[0]父节点从空网络构造。有三个基本算子:(1)增加边。一条边增举例: 01 |x[0]不为x[0]父节点, x*[0]是( X[0]加到网络中,以增加新的依赖。(2) 删除边。为了从现有1|0 x*{0]是x10)父节点, xs[0]不是.1 x[0], x(0|均为x,[0]父节点网络中删除已有的依赖关系,导出新的独立性或增强已有的独立关系,而删除现有网络图的一条边。(3) 反转边。1101100 由编码( X[0])为了改变现有网络中某两个连接节点的相互依赖特性,而可得到图反转其连接边的方向。显然,反转边算子的功能可由应用x[0]x[0] x;[0]X;[0] x;[0]X.[0]一次删除算子后,再应用一次增加边算子代替。标志位父节标志位父节标志位父节图可得点的一到编码(X[0)当没有操作能够提高当前度量值的时候,搜索终止。个组合所有基本算子的运行必须保证BN的的合理性，即不产生图4 DBN 的二进制基因编码示意图循环。因而,引入循环的操作必须被取消。而且,限制终止若B。:1|011|11 1|100于任意节点的边的条数能够限制最终结构的复杂性。上面描述的贪婪算法的伪代码描述如下:可简化为:00→011100(1)初始化网络B(例如空网络图);x.to向x向~ '(2)选择符合约束条件的所有简单图以便进行操作;B.:__ 100100 1|10001 101100 .(3)挑选能最大可能提高网络图度量值的基本算子;中国煤化工对(4)根据上述挑选的算子进行操作;MHcNMH0000(5)在问题的复杂性或变量之间的最大的关联数约束下,如果网络图的度量值不再提高;第10期肖秦琨等:基于贝叶斯优化构建DBN结构优化算法.●1735●B。+ B_的组合编码为:011100 0100001100(x[0})(x[] ) +51+1))(x[0)(x[凹] )- rpt[+1]每个基因的等位基因呈现的数目可能是巨大的。在先(10)(x0) )-rt1+n))(x2[0])(x[] Werl+1)验网络中,其值的变化范围是: 0~n- 1;在转换网络中,其.值的变化范围是:0~ 2n- 1,其中n是其中变量的数目。对(x1[0)(x0]) (i[+tn)(x[1)(x[I) (iltit父结点数目的限制是有道理可盲的，因为结构太复杂时可先验网络S转移网络能导致难以推理下去.因此,某个属于先验网络的等位基因三进制编码:B二进制编码:可以表现出2。。Ca(i) 个可能的值,mo是父结点的最001011 00001010010010000111 00001 1011010大集;类似地，转换网络某基因的等位基因可表现出之0]10110[0]12.om Cxmr(i) 个可能的值,m.是转换网络中变量父结C[.101x1011000,101x.01x.101x0x:(01w叉12x.1x1010点的最大集。1000交叉1100]x川(2)适值函数动态贝叶斯网络结构的测度标准,最常[x业11010见的有BIC测度和BD测度标准,我们在这里应用BD测度+1x031010 a 10100101交叉11101下划线红色基因相互交换少作为DBN结构度量的适值函数。贝叶斯狄利克雷度量x[O11]100(Bayesian Dirichlet metricBD) ,简记为BD度量[°]C.0]x0111010x[10x10]):101x10101心[x101x101x.101BD(B)= p(B)"T(m'(πx) + m(x))(1(((((1x1111110010000[+1 lxrxx [1+11110π rm(x,x)+m(.,x))r(m' (x,x))1二进制编码二进制编码111001 10101101000000 1001001式中，D为对应于s,表示数据集,B为匹配与数据集的网络图,X为网络图中第i个顶点,πx为X,的父顶点取值,工为(x.[0)(x[4) x1[1叭X,的取值，例如对于二进制编码,工∈{0,1).m(zx) =习。m(,批x)相应记号m'(工，mx) ,m'(mx)表示先验网(x[0)(x[] Ax[11代(x[0)| (x[0]) (r[+1)络图的有关信息。.(3)选择初始种群初始种群可随机地产生,或由领城(x10)(xl4) (lttift(x[0] '(x1) 1t1专家根据经验给出:另一种方法是Madigan 提出的一种变体的技术:它将先验分布赋予网络结构的假设,在这种方法中,计算机程序帮助用户产生- -个完整数据的假设集,基于来自领域专家的图像数据,在完整数据的情况下,一些“好”图5 DBN 交叉因子操作过程示意图的结构被选择来构成初始的种群。③变异模式变异 是必须的,它可以产生新的状态，(4)遗传算子的设计①选择模式对要选择的 模式进行排列,每个单体可帮助算法避免局部最优化。它可能改变等位基因的表现以根据其适应度函数值来判定,它作为父代的可能性有多值,这种变异概率几乎为零。在该算法中,等位基因表示变大。显然,选取的可能性并不是与其适应度的绝对值相关.量的父节点的集合,因此等位基因的改变暗示着其父节点因而,这种模式可以避免由超个体所致的算法过早地收敛。的变化。我们引人两类变异操作:增加一个节点和删除- -因为，比较大的适应值总是期望着成为下一代的种群,它们个节点,它们正好符合在表现型中增加和删除-条弧,如图几乎总是被选取。如果用I,(j)来标识在时间t时种群中第6所示。在先验网络中,被加人到等位基因中的节点是在0j个单体,rank [I,(j)]表示它的适应度函数值的排列,入表时间切片上的那些变量。在转换网络中,被加人的节点是示种群的大小,那么单体被选取作为父代的概率P.等于时间切片t- 1或切片t上的变量。P. = rank (I,G))/2(1+ 1)/2(2交叉和变异之后,就完成了一次进化周期。在进入下.②交叉模式交叉操作增加了种群的平均质量,是从一个周期之前,有几点值得注意的地方。①所产生的结构种群的随机配对中,由选作操作算子选取的。在后代的生可能是非法的,可能不能履行其中的约束。先验网络的节产过程中,两个父代的DBN结构根据交叉概率p.通过统点最多中国煤化工节点最多有m父节-的参数化了进行交叉操作。图5表示了交叉操作的过点,因CN MH G情况:一步是检查是程,证明了具有高适应值的局部结构像基因块一样在父代否新的个体是合法的,遇过畀法1secylicnotl1)的检查,并中以更高适应度值被交换。且将非法的结构赋予极低的适应值:另一步是限制父节点●1736●系统工程与电子技术第29卷的数目,为每个节点,我们随机地选取k(011010.10步骤2一个新个体所有变量 的值根据计算次序生C[x10]x0]10成。给定一个变量的父辈的值,这个变量值的分布通过相xJx10x J01变异应的条件概率给定。执行第二步生成每个新个体。则用贝E(+!]x0| 1000变异11(1]x1x1x]+1 x小x[1111010 .101001[1]，1，[+1]叶斯网络推理新个体的算法描述为:1x0101101001 变异11110四心工工工业世山(1)创建变量遗传次序列表;下划线红色基冈变异(2)用贝叶斯网络表示的条件概率以及变量遗传次序0m相当于制除茶边，表生成所有变量的值;翻转一条边相当于先删除条边，再增加一条边，如:[0]到x,[0]弧的变化(3)生成更多个体,返回(2)●图6 DBN 变异因子操作过程示意图5仿真(5)遗传参数的设置参数的设置包括种群的规模、为了检验基于BOA的DBN结构寻优体系的合理性与交叉概率.变异概率以及遗传的代数。种群的规模n的范可行性,在MATLAB6. 1环境中进行了仿真,计算机配置围是30~160;交叉概率- -般在0.8~0.9左右;变异概率比主频P1.4 GHz,256 M内存。我们使用一个熟悉的网络结较小,- -般在0.01~0.2左右;遗传的代数一般根据构造结构(ASIA动态网络)来做验证试验(见图7).构精度的大小不同而有别，遗传的代数愈大,得到的结构愈() +(+))接近于真实的结构。(6)构造的算法由时态函数依赖的定义引理、定理.公理、推论,以及由语义得到的数据依赖[1 ,最后可以TO- 4080求得属性集U.上的时态依赖关系集和条件独立的时态属性集合,作为下面遗传算法构造动态网络结构的输入。算法实现的步骤如下:中国煤化工、O(t1)输入:依赖集D= {A→B,i,j∈n}和条件独立集1=YH. CNMHGP({(M,.i,jEn}.输山:全局最优的结构S.图72时间片段ASIA动态网络(1)初始种群C,C,*,C,(j是种群的个数),设每个第10期肖秦琨等:基于贝叶斯优化构建DBN结构优化算法●1737●所有的结点取值是二进制的。本试验数据来自Phil-收敛性从心小「。ippe LeRay等人编写的BNT Structure Learning Pack-表1 ASIA 部分数据示例agell),时间片段取1~10000,部分ASIA动态网络数据如组别(时间片)表1所示。如图8所示,我们比较了三种算法的寻优曲线，56789101112三种算法在有限的进化代数中依据观测数据均找到了网络结构,其中交叉概率0.8、变异概率0.02,最大生成比例50% ,最大迭代1 000次,运行时间如表2所示。从结果可以看出,基于BOA的寻优算法种群平均适应度在较短的时间内趋于稳定,其最佳适应值在300代左右趋于稳定,而基于概率模型进化算法在400代左右,经典遗传算法在900代左右。且基于BOA算法从起始迭代,最佳适应值与平均22适应值联系密切,以上均说明,本文提出的算法有着良好的0f3100 200 300 400 500 600 700 800 900 100100 200 300 400 500 600 700 800 900 1000进化代教进化代数一:平均适应值; ---最佳适应值一-:平均适应值; ---佳适应值(旧)应用GA进行寻优,(b) 应用基于概率模型进化算法进行寻优(PBIL)(C) BOA算法寻优图8结构寻优算法比较图表2进化算法学习时间比较d for integrating genetic search based function optimitation and算法毛时/sBEST Finess-BICcompetitve learming[J]. School of Computer Science, CarmnegieGA(900代)50. 25BICDBN:- 68 032Mellon University, Report No. CMU- -CS -94- 163, 1994.PBIL(400代)36.59BICDBN;- -76 866[5] Martin Pelikan, David E, Golaberg, et al. The Bayesian optimi-BA(300代)10.5BICDBN:-58 741zation algorithm[C] // Ilinois, Univ. of Ilinois at Urbana-Champaign, IiGAL Report No.98013, 1998.6结束语[6] Pelian M, Goldberg D E, Cantu-Paz E The Bayesian optimize-本文从基于概率模型进化算法出发,提出了基于tion algorithm, population sizing. and time to convergence, lliBOA的DBN结构寻优体系,具体的贡献为:(1)提出了构nois[C]//Univ. of llinois at Urbana-Champaign, IUiGAL Re-造DBN结构的总体思路,即基于BOA的寻优体制;(2)port No.200000 ,2000.提出了基于贪婪算法机制的遗传算法DBN网络学习模[7] Husmeier D. Snitvity and seificitt of iferin genetic regur型,并具体细化到DBN网络结构的编码、适应度函数设latory interactions from microarray experiments with dynamic计遗传算子设计等;(3)进行了相应算法的仿真试验,并bayesian networks[J]. Bioinformatics, 2003,19; 2271 - 2282.得出了相应的结论,为选用合理算法进行DBN结构寻优[8] George Lauger F. Arificial itelligence -structures and strate-提供了思路。gies for complex problem solving, fourth edition[J]. AddisonWesley. ,2002,52 -63.参考文献:[9] jiei Oeendsek Parallel estimation of distribution algorithms,doctoral thesi[]. BRNO Univ. of Technology ,2001:23- 36.[1] Sanghai s, Domingos P, Weld D. Relational dynamic Bayeien[10] Martin pelican, Bayesian optimization algorithm; from single levelnetworks[J]. Artificial Intelligence Research, 2005, 16(2):to hierarchy,doctoral dissertation[C]//Univ. of llinois at Urbanr336 - 338.Champaign, Also IiGALReport No. 2002023, 2002.[2] Kok s, Domingos P. Learning the structure of Markov logic net-works[M]. In ICML'05, Bonn, Germany, 2005, ACM Press:[11] Martin Pelikan, Goldberg David E, et al Bayesian optimization63-75.algorithm, decision graphs and Occam's razor[C]/ Ilinis,[3] Bernard A, Hartemink A J. Informative structure priors; Joint中国煤化工”Iu4CAL Repon No.learning of dynamic regulatory networks from multiple types ofdata[C]/In PSB, 2005; 459-470.[12] P:JYHC N M H Gructure lering package[4] Shumeet Baluja Population based ineremental lerning: A meth-[EB/OL]. http://banquise asi. insa rouen. fr/projects