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