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