基于貝葉斯優(yōu)化構建DBN結構優(yōu)化算法

第29卷第10期系統工程與電子技術(shù)Vol, 29 No. 102007年10月Systems Engineering and ElectronicsOct.2007文章編號1001-506X(2007)10-173206基于貝葉斯優(yōu)化構建DBN結構優(yōu)化算法肖秦琨'，以，高嵩',高曉光2(1. 西安工業(yè)大學(xué)電子信息學(xué)院，陜西西安710072;2.西北工業(yè)大學(xué)電子信息學(xué)院，陜西西安710072)摘要: 針對動(dòng)態(tài)貝葉斯網(wǎng)絡(luò )(DBN)結構學(xué)習問(wèn)題,提出了一種基于貝葉斯優(yōu)化(BOA)的DBN結構尋優(yōu)算法。首先,從傳統進(jìn)化優(yōu)化機制的基本理論和基本操作入手,刻劃了基于概率模型進(jìn)化算法的基本思想。其次，通過(guò)描述基于概率模型進(jìn)化算法的構困基礎,引出了DBN結構學(xué)習機制，即基于BOA的DBN結構尋優(yōu)算法。BOA算法的關(guān)鍵是根據優(yōu)良解集學(xué)習得到DBN,以及根據DBN推理生成新個(gè)體，前者更為重要,依據基于貪婪機理的遺傳算法解決動(dòng)態(tài)網(wǎng)絡(luò )學(xué)習,再應用DBN前向模掀完成后一步。仿真結果表明了該算法的可行性。關(guān)鍵詞:動(dòng)態(tài)貝葉斯網(wǎng)絡(luò );貝葉斯優(yōu)化算法;結構學(xué)習;遣傳算法;前行模擬中圖分類(lèi)號: 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引言競爭學(xué)習機制引入進(jìn)化算法的自主學(xué)習,實(shí)驗表明,在作業(yè)車(chē)間調度(JSP)、旅行商等問(wèn)題的解決上顯示了一定的優(yōu)越貝葉斯網(wǎng)絡(luò )結構學(xué)習是一個(gè)組合優(yōu)化問(wèn)題,而引人時(shí)性。類(lèi)似的還有Harik等提出的緊致遺傳算法(CGA),間關(guān)系的動(dòng)態(tài)貝葉斯網(wǎng)絡(luò )(dynamic Bayesian networks,Muhlenbein的-元邊緣分布算法(UMDA).以及分布分解DBN)結構學(xué)習,由于其動(dòng)態(tài)性和時(shí)效性,使得學(xué)習變得更算法(FDA)等。而基于貝葉斯網(wǎng)絡(luò )學(xué)習的貝葉斯優(yōu)化算加復雜[*] ,這就需要尋找合理且快速的搜索方法。法54)(Bayesian optimization algorithm, BOA)將基于概率研究搜索過(guò)程中自動(dòng)獲取問(wèn)題的固有知識、積累有關(guān).模型進(jìn)化算法與圖形模型相結合,不僅具有運行時(shí)占用內搜索空間的屬性,并自適應地控制搜索過(guò)程,從而得到最優(yōu)存空間少的特點(diǎn),且可有效的避免早熟現象,鑒于此,本文解或次優(yōu)解的啟發(fā)式搜索算法一直是眾多 學(xué)者熱衷的研究提出基于BOA的DBN結構尋優(yōu)算法,首先從概率模型進(jìn)課題。近年來(lái),以遺傳算法為基礎的基于概率模型進(jìn)化算化算法的機理人手,進(jìn)而討論基于BOA結構學(xué)習的總體思法的研究,引起了國內外的廣泛興趣,最具代表的工作有路,最后將問(wèn)題集中在DBN網(wǎng)絡(luò )學(xué)習與推理的具體算法Baluja 提出的基于種群的增強學(xué)習算法(PBIL)4,將簡(jiǎn)單上,即中國煤化工k前向模擬網(wǎng)絡(luò )推理收稿日期:2006 -07 - 30;修回日期:2006-10-21.YHCNMHG基金項目:國家自然科學(xué)基金重大項目(90205019);|陜西省科研專(zhuān)項(陜西省教育廳07JK277)資助課題作者簡(jiǎn)介:肖秦琨(1974-),男,講師,博t,主要研究方向為動(dòng)態(tài)貝葉斯網(wǎng)絡(luò ),人工智能. E-mail: xingin10000@163. com第10期肖秦琨等:基于貝葉斯優(yōu)化構建DBN結構優(yōu)化算法●1733●模型。從宏觀(guān)上講,基于圖形模型的進(jìn)化優(yōu)化機制是基于概1基于 概率模型的進(jìn)化算法率模型的遺傳算法的進(jìn)一步發(fā)展,前者更強調圖形模型的建立、度量和新解的生成，后者強調種群分布的計算和估由模式定理及積木塊假沒(méi)可知,進(jìn)化算法成功的關(guān)鍵計,我們后面討論的用于DBN結構尋優(yōu)的的BOA算法即是:好的積木塊能夠良性地成長(cháng)(growth)與混合(mixing)。為圖形模式下的進(jìn)化算法。因面傳統的進(jìn)化算法,例如簡(jiǎn)單遺傳算法,對于積木塊集中2DBN結構尋優(yōu)算法概述地駐留于某些個(gè)體串的待優(yōu)化問(wèn)題更加有效.而當積木塊幾乎散布于所有個(gè)體串的待優(yōu)化問(wèn)題效率就比較差。所無(wú)論是在靜態(tài)的貝葉斯網(wǎng)路或動(dòng)態(tài)貝葉斯網(wǎng)絡(luò )結構以,探索問(wèn)題的固有結構,以便利用這些信息確保積木塊合中,如果對變最的父節點(diǎn)和子節點(diǎn)個(gè)數不加限制,這樣的園適地累積,就顯得非常重要,而且成為構建新型進(jìn)化機制的形模型就是貝葉斯網(wǎng)絡(luò )圖(Bayesian network, BN).基于切入點(diǎn)。其中方法之一就是利用優(yōu)良解的概率樸型指導搜BN的進(jìn)化算法被稱(chēng)為貝葉斯優(yōu)化算法，簡(jiǎn)稱(chēng)BOA,同樣，索空間的進(jìn)一步探索,以代替簡(jiǎn)單遺傳算法中的交叉、變異我們可以將其推廣,以用于DBN的結構尋優(yōu)。遺傳算子。這就是基于概率模型進(jìn)化算法的思想來(lái)源。為BOA是利用BN匹配進(jìn)化種群的優(yōu)良觶集而產(chǎn)生新的了與傳統遺傳算法的流程比較,給出基于分布估計模式的染色體來(lái)體現種群的進(jìn)化,它適應于問(wèn)題候選解編碼長(cháng)度固進(jìn)化算法基本流程見(jiàn)圈1.聯(lián)結問(wèn)題(inkage problem)是定、等位基因是有限字母的各類(lèi)問(wèn)題,特別有利于具有可加指積木塊被破壞問(wèn)題,最早由Harik 和Goldberg 提出,為性的問(wèn)題優(yōu)化，而DBN度量機制的可加性恰滿(mǎn)足于這一點(diǎn)。了防止對重要解所在積木塊的破壞，主要有兩大技術(shù)(0,基于BOA的DBN尋優(yōu)對于種群的進(jìn)化主要體現在以(1)改變解的表示或改進(jìn)重組算子;(2)從有前途的個(gè)體集下4步;(1)確定優(yōu)良解集:可利用各種選撣機制從當代種群合(或稱(chēng)為優(yōu)良解集)中提取信息產(chǎn)生新的個(gè)體。第- -種技中選出優(yōu)良解集。(2)尋找動(dòng)態(tài)網(wǎng)絡(luò )圖:根據優(yōu)良解集的數術(shù)的代表性工作有Goldberg提出的混亂遺傳算法(messy.據信息確立基于某種度量值比較好的網(wǎng)絡(luò )圖。(3)產(chǎn)生 新的genetic algorithm, MGA),在MGA中,個(gè)體由每個(gè)分量的候選解;利用網(wǎng)絡(luò )圖的聯(lián)合分布產(chǎn)生新的個(gè)體集。(4)下代位置與取值共同表示,位暨可以不按次序排列,但并不是所種群的產(chǎn)生:以新的個(gè)體集代替 上代種群的某些染色體來(lái)更有分量都在個(gè)體的表示中出現。由于MGA操作的對象既新種群為新- -代種群。 以上4步反復執行,直到滿(mǎn)足算法終有個(gè)體,又有模式,所以喪失了只操作個(gè)體的隱并行性。同止條件。算法的終止條件可以是運行到-定的代數、種群中，樣地,各種重新排序(reordering)和映射(mpping)算子的已具有足夠好的解或者算法的進(jìn)化速度已經(jīng)非常慢面不值應用,雖然有助于聯(lián)結問(wèn)題,卻降低了進(jìn)化的速度或削弱了得繼續運行?；贐OA的DBN尋優(yōu)基本步驟描述如下，選擇的競爭性,面引起早熟(premature)現象。有關(guān)進(jìn)化算步驟1隨機產(chǎn)生初始種群 P(0)。法的大多數文獻集中于第- - 種技術(shù),而體現第二種技術(shù)的步驟2從P(1)中選擇高于平均適應值的個(gè)體作為優(yōu)進(jìn)化算法,正是致力于加強進(jìn)化算法的進(jìn)化機制研究,以提良解集S(). .高進(jìn)化算法的適應性、智能性及有效性的貝葉斯優(yōu)化方法。的DBN.步驟3依據某種度量及約柬構建匹配于 s(t)C數編碼D步粟4根據DBN編碼的聯(lián)合分布產(chǎn)生新申集o().隨機初始化第1-0代種群步驟5由0(t)代替P(1)中的某些解集,生成1+1種.群P(r+1).[第代種群P(O中個(gè)體適應值的評估]步驟6如果不滿(mǎn)足算法的終 止準則,轉向步驟2.L 從P0種選擇優(yōu)良個(gè)體集)上述算法說(shuō)程可以形象地描述如圖2.由圖2知，估計&0)的概率分布00)BOA的關(guān)鍵是根據優(yōu)良解集學(xué)習得到DBN,以及根據DBN推理生成新個(gè)體。下面我們來(lái)詳細討論這兩個(gè)步驟。根據上述分布產(chǎn)生串集00從O(0代禁P0)中的S0)初始種群 _優(yōu)良解集動(dòng)態(tài)貝葉斯網(wǎng)絡(luò )新的種群, 0010011000 1001001 100I 100001 1101010( 100000 1001101011001 廠(chǎng)10011100110010000011001001 10011011011000101100是否滿(mǎn)足00001000100001 1001終止進(jìn)化準則2>100100000100000001中國煤化1.1011000是(結束)-P1BMA4)TYHCN M H GAceI2)圖1基于概率模型的進(jìn)化算法的基本施程圖圈2基于BOA的DBN結構學(xué)習算法●1734●系統工程與電子技術(shù)第29卷.(6)返回(2)。3學(xué)習DBN3.3基于貪婪機理 的遺傳算法3.1概述如前所述,DBN包含兩部分網(wǎng)絡(luò )框架B=(B,B_),它成功應用基于BOA尋優(yōu)的關(guān)鍵就是動(dòng)態(tài)貝葉斯網(wǎng)絡(luò )們分別叫作先驗網(wǎng)絡(luò )和轉換網(wǎng)絡(luò ),如圖示。這里用兩條染的學(xué)習,DBN的學(xué)習同靜態(tài)網(wǎng)絡(luò )一樣,主要包含兩個(gè)方色體C,C.分別表示先驗網(wǎng)絡(luò )B。和B- ,而G,C.的組合面[0]:(1)結構的學(xué)習。對于靜態(tài)網(wǎng)絡(luò )，只需要確定某一個(gè)編碼了一個(gè)完整的DBN.另外,一個(gè)DBN結構可表示成獨立的網(wǎng)絡(luò )結構,而對于動(dòng)態(tài)網(wǎng)絡(luò )而言，則需要同時(shí)確定鏈狀的形式,每-列某些結點(diǎn)是令- -列某些結 點(diǎn)的父結點(diǎn)。BO和B→網(wǎng)絡(luò )結構,→旦結構確定,網(wǎng)絡(luò )結構定義的相應(1)編碼(Encoding)圖3是時(shí)間切片0、1.1+1上的網(wǎng)變量的條件獨立與依賴(lài)關(guān)系也就確定了;(2)參數的學(xué)絡(luò )結構簡(jiǎn)圖.在轉換網(wǎng)絡(luò )中,t時(shí)刻的所有結點(diǎn)沒(méi)有父結點(diǎn)。習。對于完整的貝葉斯網(wǎng)絡(luò ),其結構所定義的關(guān)系必須簡(jiǎn)言之,我們只編碼在時(shí)刻t+ 1的結點(diǎn),圖3中,每組第一利用條件概率值確定。所以確定結構以后,需要進(jìn)行條個(gè)成員(基因)是變量X,其他成員(等位基因)是X的父結件概率的學(xué)習。在給定度量下學(xué)習一個(gè)網(wǎng)絡(luò )的結構是點(diǎn),記為II (x)。盡管圖形法更加簡(jiǎn)明,染色體~基因~等一個(gè)復雜的組合問(wèn)題。實(shí)際上,已經(jīng)證明,對于多數貝位基因的編碼法使得遺傳操作更加方便，等位基因編入了葉斯或者非貝葉斯度量,搜索最優(yōu)網(wǎng)絡(luò )是NP難的C0]。變量的位置.(Co,C.)合在-起可被看作是表示DBN的一-這是由于BN的數目隨著(zhù)節點(diǎn)數目的增加成天文數字增個(gè)染色體,其中每一組是- 個(gè)基因,[(x)是等位基因。同.加，例如10個(gè)節點(diǎn)的BN,雖然邊數最多為45條,等價(jià)類(lèi)樣,如果任-個(gè)基因位用0或1表示，我們可以將(C,C.)計數為: 118902054495975141,相應網(wǎng)絡(luò )圖的搜索規模表示為二進(jìn)制編碼的基因(見(jiàn)圖4)。為:4175163455710941233.因此,為了迅速搜索到質(zhì)量高的DBN,-方面可以根據x問(wèn)題的復雜性以及問(wèn)題的有關(guān)先驗信息限制其搜索空間,這(x([0]) G :01x101x[](x[+1])0.0.01是“硬”減少搜索空間。另一方面就是“軟”減少搜索空間。先驗網(wǎng)絡(luò )編碼父節點(diǎn)利用局部結構學(xué)習網(wǎng)絡(luò )結構,即利用決定樹(shù)、決定圖進(jìn)行學(xué)在后，子節點(diǎn)在前( x[]習,或者采取增加網(wǎng)絡(luò )圖邊的方法" ,即每增加一條邊,便計10算網(wǎng)絡(luò )圖的度量值，進(jìn)行比較觀(guān)察,確定是否將這條邊加入.:+1]x(1+1]x[0]x()]+1107到網(wǎng)絡(luò )圖中,這是眾多文獻所采用的貪婪搜索算法。x[0] )轉移網(wǎng)絡(luò )編碼(父節點(diǎn)(x1[+1)3.2貪婪算法貪婪算法執行三個(gè)基本圖形操作,以提高當前網(wǎng)絡(luò )的先驗網(wǎng)絡(luò )轉移網(wǎng)絡(luò )質(zhì)量,直到操作不再能提高網(wǎng)絡(luò )質(zhì)量。網(wǎng)絡(luò )結構可以被初圖3 DBN 及其編碼始化為沒(méi)有邊。在貝葉斯優(yōu)化算法中,初始結構可以被設所表示的意義置為上一-代學(xué)習得到的結構。本章中,網(wǎng)絡(luò )在每一代都是| 00 x[0], x[0]均不為x[0]父節點(diǎn)從空網(wǎng)絡(luò )構造。有三個(gè)基本算子:(1)增加邊。一條邊增舉例: 01 |x[0]不為x[0]父節點(diǎn), x*[0]是( X[0]加到網(wǎng)絡(luò )中,以增加新的依賴(lài)。(2) 刪除邊。為了從現有1|0 x*{0]是x10)父節點(diǎn), xs[0]不是.1 x[0], x(0|均為x,[0]父節點(diǎn)網(wǎng)絡(luò )中刪除已有的依賴(lài)關(guān)系,導出新的獨立性或增強已有的獨立關(guān)系,而刪除現有網(wǎng)絡(luò )圖的一條邊。(3) 反轉邊。1101100 由編碼( X[0])為了改變現有網(wǎng)絡(luò )中某兩個(gè)連接節點(diǎn)的相互依賴(lài)特性,而可得到圖反轉其連接邊的方向。顯然,反轉邊算子的功能可由應用x[0]x[0] x;[0]X;[0] x;[0]X.[0]一次刪除算子后,再應用一次增加邊算子代替。標志位父節標志位父節標志位父節圖可得點(diǎn)的一到編碼(X[0)當沒(méi)有操作能夠提高當前度量值的時(shí)候,搜索終止。個(gè)組合所有基本算子的運行必須保證BN的的合理性，即不產(chǎn)生圖4 DBN 的二進(jìn)制基因編碼示意圖循環(huán)。因而,引入循環(huán)的操作必須被取消。而且,限制終止若B。:1|011|11 1|100于任意節點(diǎn)的邊的條數能夠限制最終結構的復雜性。上面描述的貪婪算法的偽代碼描述如下:可簡(jiǎn)化為:00→011100(1)初始化網(wǎng)絡(luò )B(例如空網(wǎng)絡(luò )圖);x.to向x向~ '(2)選擇符合約束條件的所有簡(jiǎn)單圖以便進(jìn)行操作;B.:__ 100100 1|10001 101100 .(3)挑選能最大可能提高網(wǎng)絡(luò )圖度量值的基本算子;中國煤化工對(4)根據上述挑選的算子進(jìn)行操作;MHcNMH0000(5)在問(wèn)題的復雜性或變量之間的最大的關(guān)聯(lián)數約束下,如果網(wǎng)絡(luò )圖的度量值不再提高;第10期肖秦琨等:基于貝葉斯優(yōu)化構建DBN結構優(yōu)化算法.●1735●B。+ B_的組合編碼為:011100 0100001100(x[0})(x[] ) +51+1))(x[0)(x[凹] )- rpt[+1]每個(gè)基因的等位基因呈現的數目可能是巨大的。在先(10)(x0) )-rt1+n))(x2[0])(x[] Werl+1)驗網(wǎng)絡(luò )中,其值的變化范圍是: 0~n- 1;在轉換網(wǎng)絡(luò )中,其.值的變化范圍是:0~ 2n- 1,其中n是其中變量的數目。對(x1[0)(x0]) (i[+tn)(x[1)(x[I) (iltit父結點(diǎn)數目的限制是有道理可盲的，因為結構太復雜時(shí)可先驗網(wǎng)絡(luò )S轉移網(wǎng)絡(luò )能導致難以推理下去.因此,某個(gè)屬于先驗網(wǎng)絡(luò )的等位基因三進(jìn)制編碼:B二進(jìn)制編碼:可以表現出2。。Ca(i) 個(gè)可能的值,mo是父結點(diǎn)的最001011 00001010010010000111 00001 1011010大集;類(lèi)似地，轉換網(wǎng)絡(luò )某基因的等位基因可表現出之0]10110[0]12.om Cxmr(i) 個(gè)可能的值,m.是轉換網(wǎng)絡(luò )中變量父結C[.101x1011000,101x.01x.101x0x:(01w叉12x.1x1010點(diǎn)的最大集。1000交叉1100]x川(2)適值函數動(dòng)態(tài)貝葉斯網(wǎng)絡(luò )結構的測度標準,最常[x業(yè)11010見(jiàn)的有BIC測度和BD測度標準,我們在這里應用BD測度+1x031010 a 10100101交叉11101下劃線(xiàn)紅色基因相互交換少作為DBN結構度量的適值函數。貝葉斯狄利克雷度量x[O11]100(Bayesian Dirichlet metricBD) ,簡(jiǎn)記為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二進(jìn)制編碼二進(jìn)制編碼111001 10101101000000 1001001式中，D為對應于s,表示數據集,B為匹配與數據集的網(wǎng)絡(luò )圖,X為網(wǎng)絡(luò )圖中第i個(gè)頂點(diǎn),πx為X,的父頂點(diǎn)取值,工為(x.[0)(x[4) x1[1叭X,的取值，例如對于二進(jìn)制編碼,工∈{0,1).m(zx) =習。m(,批x)相應記號m'(工，mx) ,m'(mx)表示先驗網(wǎng)(x[0)(x[] Ax[11代(x[0)| (x[0]) (r[+1)絡(luò )圖的有關(guān)信息。.(3)選擇初始種群初始種群可隨機地產(chǎn)生,或由領(lǐng)城(x10)(xl4) (lttift(x[0] '(x1) 1t1專(zhuān)家根據經(jīng)驗給出:另一種方法是Madigan 提出的一種變體的技術(shù):它將先驗分布賦予網(wǎng)絡(luò )結構的假設,在這種方法中,計算機程序幫助用戶(hù)產(chǎn)生- -個(gè)完整數據的假設集,基于來(lái)自領(lǐng)域專(zhuān)家的圖像數據,在完整數據的情況下,一些“好”圖5 DBN 交叉因子操作過(guò)程示意圖的結構被選擇來(lái)構成初始的種群。③變異模式變異 是必須的,它可以產(chǎn)生新的狀態(tài)，(4)遺傳算子的設計①選擇模式對要選擇的 模式進(jìn)行排列,每個(gè)單體可幫助算法避免局部最優(yōu)化。它可能改變等位基因的表現以根據其適應度函數值來(lái)判定,它作為父代的可能性有多值,這種變異概率幾乎為零。在該算法中,等位基因表示變大。顯然,選取的可能性并不是與其適應度的絕對值相關(guān).量的父節點(diǎn)的集合,因此等位基因的改變暗示著(zhù)其父節點(diǎn)因而,這種模式可以避免由超個(gè)體所致的算法過(guò)早地收斂。的變化。我們引人兩類(lèi)變異操作:增加一個(gè)節點(diǎn)和刪除- -因為，比較大的適應值總是期望著(zhù)成為下一代的種群,它們個(gè)節點(diǎn),它們正好符合在表現型中增加和刪除-條弧,如圖幾乎總是被選取。如果用I,(j)來(lái)標識在時(shí)間t時(shí)種群中第6所示。在先驗網(wǎng)絡(luò )中,被加人到等位基因中的節點(diǎn)是在0j個(gè)單體,rank [I,(j)]表示它的適應度函數值的排列,入表時(shí)間切片上的那些變量。在轉換網(wǎng)絡(luò )中,被加人的節點(diǎn)是示種群的大小,那么單體被選取作為父代的概率P.等于時(shí)間切片t- 1或切片t上的變量。P. = rank (I,G))/2(1+ 1)/2(2交叉和變異之后,就完成了一次進(jìn)化周期。在進(jìn)入下.②交叉模式交叉操作增加了種群的平均質(zhì)量,是從一個(gè)周期之前,有幾點(diǎn)值得注意的地方。①所產(chǎn)生的結構種群的隨機配對中,由選作操作算子選取的。在后代的生可能是非法的,可能不能履行其中的約束。先驗網(wǎng)絡(luò )的節產(chǎn)過(guò)程中,兩個(gè)父代的DBN結構根據交叉概率p.通過(guò)統點(diǎn)最多中國煤化工節點(diǎn)最多有m父節-的參數化了進(jìn)行交叉操作。圖5表示了交叉操作的過(guò)點(diǎn),因CN MH G情況:一步是檢查是程,證明了具有高適應值的局部結構像基因塊一樣在父代否新的個(gè)體是合法的,遇過(guò)畀法1secylicnotl1)的檢查,并中以更高適應度值被交換。且將非法的結構賦予極低的適應值:另一步是限制父節點(diǎn)●1736●系統工程與電子技術(shù)第29卷的數目,為每個(gè)節點(diǎn),我們隨機地選取k(011010.10步驟2一個(gè)新個(gè)體所有變量 的值根據計算次序生C[x10]x0]10成。給定一個(gè)變量的父輩的值,這個(gè)變量值的分布通過(guò)相xJx10x J01變異應的條件概率給定。執行第二步生成每個(gè)新個(gè)體。則用貝E(+!]x0| 1000變異11(1]x1x1x]+1 x小x[1111010 .101001[1]，1，[+1]葉斯網(wǎng)絡(luò )推理新個(gè)體的算法描述為:1x0101101001 變異11110四心工工工業(yè)世山(1)創(chuàng )建變量遺傳次序列表;下劃線(xiàn)紅色基岡變異(2)用貝葉斯網(wǎng)絡(luò )表示的條件概率以及變量遺傳次序0m相當于制除茶邊，表生成所有變量的值;翻轉一條邊相當于先刪除條邊，再增加一條邊，如:[0]到x,[0]弧的變化(3)生成更多個(gè)體,返回(2)●圖6 DBN 變異因子操作過(guò)程示意圖5仿真(5)遺傳參數的設置參數的設置包括種群的規模、為了檢驗基于BOA的DBN結構尋優(yōu)體系的合理性與交叉概率.變異概率以及遺傳的代數。種群的規模n的范可行性,在MATLAB6. 1環(huán)境中進(jìn)行了仿真,計算機配置圍是30~160;交叉概率- -般在0.8~0.9左右;變異概率比主頻P1.4 GHz,256 M內存。我們使用一個(gè)熟悉的網(wǎng)絡(luò )結較小,- -般在0.01~0.2左右;遺傳的代數一般根據構造結構(ASIA動(dòng)態(tài)網(wǎng)絡(luò ))來(lái)做驗證試驗(見(jiàn)圖7).構精度的大小不同而有別，遺傳的代數愈大,得到的結構愈() +(+))接近于真實(shí)的結構。(6)構造的算法由時(shí)態(tài)函數依賴(lài)的定義引理、定理.公理、推論,以及由語(yǔ)義得到的數據依賴(lài)[1 ,最后可以TO- 4080求得屬性集U.上的時(shí)態(tài)依賴(lài)關(guān)系集和條件獨立的時(shí)態(tài)屬性集合,作為下面遺傳算法構造動(dòng)態(tài)網(wǎng)絡(luò )結構的輸入。算法實(shí)現的步驟如下:中國煤化工、O(t1)輸入:依賴(lài)集D= {A→B,i,j∈n}和條件獨立集1=YH. CNMHGP({(M,.i,jEn}.輸山:全局最優(yōu)的結構S.圖72時(shí)間片段ASIA動(dòng)態(tài)網(wǎng)絡(luò )(1)初始種群C,C,*,C,(j是種群的個(gè)數),設每個(gè)第10期肖秦琨等:基于貝葉斯優(yōu)化構建DBN結構優(yōu)化算法●1737●所有的結點(diǎn)取值是二進(jìn)制的。本試驗數據來(lái)自Phil-收斂性從心小「。ippe LeRay等人編寫(xiě)的BNT Structure Learning Pack-表1 ASIA 部分數據示例agell),時(shí)間片段取1~10000,部分ASIA動(dòng)態(tài)網(wǎng)絡(luò )數據如組別(時(shí)間片)表1所示。如圖8所示,我們比較了三種算法的尋優(yōu)曲線(xiàn)，56789101112三種算法在有限的進(jìn)化代數中依據觀(guān)測數據均找到了網(wǎng)絡(luò )結構,其中交叉概率0.8、變異概率0.02,最大生成比例50% ,最大迭代1 000次,運行時(shí)間如表2所示。從結果可以看出,基于BOA的尋優(yōu)算法種群平均適應度在較短的時(shí)間內趨于穩定,其最佳適應值在300代左右趨于穩定,而基于概率模型進(jìn)化算法在400代左右,經(jīng)典遺傳算法在900代左右。且基于BOA算法從起始迭代,最佳適應值與平均22適應值聯(lián)系密切,以上均說(shuō)明,本文提出的算法有著(zhù)良好的0f3100 200 300 400 500 600 700 800 900 100100 200 300 400 500 600 700 800 900 1000進(jìn)化代教進(jìn)化代數一:平均適應值; ---最佳適應值一-:平均適應值; ---佳適應值(舊)應用GA進(jìn)行尋優(yōu),(b) 應用基于概率模型進(jìn)化算法進(jìn)行尋優(yōu)(PBIL)(C) BOA算法尋優(yōu)圖8結構尋優(yōu)算法比較圖表2進(jìn)化算法學(xué)習時(shí)間比較d for integrating genetic search based function optimitation and算法毛時(shí)/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結束語(yǔ)[6] Pelian M, Goldberg D E, Cantu-Paz E The Bayesian optimize-本文從基于概率模型進(jìn)化算法出發(fā),提出了基于tion algorithm, population sizing. and time to convergence, lliBOA的DBN結構尋優(yōu)體系,具體的貢獻為:(1)提出了構nois[C]//Univ. of llinois at Urbana-Champaign, IUiGAL Re-造DBN結構的總體思路,即基于BOA的尋優(yōu)體制;(2)port No.200000 ,2000.提出了基于貪婪算法機制的遺傳算法DBN網(wǎng)絡(luò )學(xué)習模[7] Husmeier D. Snitvity and seificitt of iferin genetic regur型,并具體細化到DBN網(wǎng)絡(luò )結構的編碼、適應度函數設latory interactions from microarray experiments with dynamic計遺傳算子設計等;(3)進(jìn)行了相應算法的仿真試驗,并bayesian networks[J]. Bioinformatics, 2003,19; 2271 - 2282.得出了相應的結論,為選用合理算法進(jìn)行DBN結構尋優(yōu)[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