基于小生境遺傳算法的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)算法研究

1、收稿日期:2006-02-15;修返日期:2006-04-03 基金項(xiàng)目:國(guó)家自然科學(xué)基金資助項(xiàng)目(79990580作者簡(jiǎn)介:黃浩(1971-,男,湖北荊州人,講師,博士研究生,主要研究方向?yàn)閿?shù)據(jù)挖掘、機(jī)器學(xué)習(xí)(hvict ory10163.co m ;宋瀚濤(1940-,男,博導(dǎo),主要研究方向?yàn)閿?shù)據(jù)庫(kù)、數(shù)據(jù)挖掘;陸玉昌(1940-,男,博導(dǎo),主要研究方向?yàn)閿?shù)據(jù)挖掘、機(jī)器學(xué)習(xí).基于小生境遺傳算法的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)算法研究*黃 浩1,宋瀚濤2,陸玉昌3(11對(duì)外經(jīng)濟(jì)貿(mào)易大學(xué)信息學(xué)院,北京100029;21北京理工大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院,北京100081;31清華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系,北京10

2、0084摘 要:在數(shù)據(jù)缺失的情況下討論一種貝葉斯網(wǎng)絡(luò)的結(jié)構(gòu)學(xué)習(xí)算法。該算法結(jié)合了小生境遺傳算法和E M 算法,最后通過(guò)試驗(yàn)說(shuō)明了該算法的有效性。關(guān)鍵詞:貝葉斯網(wǎng)絡(luò);結(jié)構(gòu)學(xué)習(xí);小生境遺傳算法;期望最大化算法中圖分類(lèi)號(hào):TP30116 文獻(xiàn)標(biāo)志碼:A 文章編號(hào):1001-3695(200704-0100-04R esearch on Struct ure Learn i ng A lgorith m of Bayesian N et w orksBased on N iche G enetic A l gorit h mHUANG H ao 1,SONG H an -tao 2,LU Y u -c

3、hang 3(1.S chool o f Infor m ation Technol ogy,Un iversit y of In ternationa lBu si ness&E cono m ics ,B eiji ng 100029,Ch i na;2.S c hool of C o mputer S cience &Technol ogy,B eiji ng In stit u t e of Technol ogy,B ei j i ng 100081,China;3.D e pt .o f Compu ter S cie n ce&Technolo gy,Ts

4、i nghua University ,B ei -jing 100084,Ch i na Abstract :Th is paper researched a learn i ng al gorith m of bayesian net works i n i nco mp lete dataw hich algori th m comb i ned n ichegeneti c al gorith m w ith E M algorit h m.Then t he experm i ent shows the al gorith m i s vali d .Key words :Bayes

5、ian net works ;struct ure l earni ng ;n iche genetic algorith m;E M algorit h m 目前,從完整數(shù)據(jù)中學(xué)習(xí)參數(shù)和網(wǎng)絡(luò)結(jié)構(gòu)以及在固定網(wǎng)絡(luò)結(jié)構(gòu)的前提下從不完整數(shù)據(jù)中學(xué)習(xí)參數(shù)已經(jīng)有比較成熟和相對(duì)完善的方法13。但是,從不完整數(shù)據(jù)集中學(xué)習(xí)網(wǎng)絡(luò)結(jié)構(gòu)仍然是一個(gè)比較困難的問(wèn)題。從不完整數(shù)據(jù)集中學(xué)習(xí)貝葉斯網(wǎng)絡(luò)是具有重要現(xiàn)實(shí)意義的。這是因?yàn)?現(xiàn)實(shí)世界中的大部分?jǐn)?shù)據(jù)經(jīng)常是不完整的。貝葉斯網(wǎng)絡(luò)一個(gè)經(jīng)常被引述的優(yōu)點(diǎn)就是可以用嚴(yán)格的方法對(duì)不完整數(shù)據(jù)進(jìn)行推斷。因此,沒(méi)有理由要求用于訓(xùn)練的數(shù)據(jù)必須是完整的。在從不完整數(shù)據(jù)集中學(xué)習(xí)貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)方面,

6、Fr ied m an 做出了開(kāi)創(chuàng)性的工作4,5。他的方法就是交替進(jìn)行網(wǎng)絡(luò)結(jié)構(gòu)的貪婪搜索過(guò)程和參數(shù)評(píng)估的E M 過(guò)程。其算法的關(guān)鍵在于,只對(duì)當(dāng)前選中的網(wǎng)絡(luò)結(jié)構(gòu)使用E M 算法(SE M 算法,進(jìn)行參數(shù)估計(jì),對(duì)于未被選中的網(wǎng)絡(luò)并不使用E M 算法;之后對(duì)所有的候選結(jié)構(gòu)進(jìn)行評(píng)價(jià),每評(píng)價(jià)一個(gè)當(dāng)前網(wǎng)絡(luò)的鄰居集,只調(diào)用一次E M 算法。因?yàn)镋 M 算法的計(jì)算強(qiáng)度是比較高的,所以能比較顯著地節(jié)省計(jì)算開(kāi)銷(xiāo)。不過(guò),F ried m an 注意到SE M 算法容易陷入局部最大值。為了緩解局部最大值問(wèn)題,通常從新的、隨機(jī)產(chǎn)生的網(wǎng)絡(luò)開(kāi)始多次運(yùn)行搜索算法。一些分析證實(shí)從不完整數(shù)據(jù)中進(jìn)行網(wǎng)絡(luò)結(jié)構(gòu)的搜索是一個(gè)非常困難的問(wèn)

7、題6,7。特別是當(dāng)搜索空間巨大、高維且具有多峰值時(shí),即使多次運(yùn)行確定性搜索方法也不能收到好的效果。為了從復(fù)雜的搜索空間中搜索到好的網(wǎng)絡(luò)結(jié)構(gòu),避免陷入局部最大值,遺傳算法、M C M C 算法等逐漸受到越來(lái)越多的重視。La rranaga 等人討論了利用遺傳算法進(jìn)行結(jié)構(gòu)學(xué)習(xí)8,采用連接矩陣表示網(wǎng)絡(luò)結(jié)構(gòu),設(shè)計(jì)了基于Bayesi an 方法的適應(yīng)度函數(shù)及選擇、重組、變異算子,對(duì)遺傳算法的控制參數(shù)進(jìn)行了性能分析。M yersW.等人改進(jìn)了La rranaga 等人的工作9,10,采用遺傳操作把不完備數(shù)據(jù)轉(zhuǎn)換成完備數(shù)據(jù),同時(shí)遺傳網(wǎng)絡(luò)結(jié)構(gòu)和遺漏的變量值。W.M yers 等人的方法可以避免陷入局部極值,但

8、缺點(diǎn)在于指數(shù)級(jí)地?cái)U(kuò)大了搜索空間;而且遺傳算子把不完備數(shù)據(jù)轉(zhuǎn)換成完備數(shù)據(jù)時(shí),無(wú)法反映遺漏數(shù)據(jù)實(shí)際具有的概率分布,難以保證算法的收斂性。1 遺傳算法遺傳算法(G enetic A lgor it h m,GA 是模擬自然界生物群體進(jìn)化過(guò)程的一種隨機(jī)優(yōu)化方法,具有不依賴(lài)于問(wèn)題模型的特性、尋優(yōu)過(guò)程的自適應(yīng)性、隱含的并行性、解決復(fù)雜非線性問(wèn)題的魯棒性以及對(duì)優(yōu)化目標(biāo)函數(shù)無(wú)須連續(xù)、可微等苛刻條件等優(yōu)點(diǎn),并在許多復(fù)雜優(yōu)化問(wèn)題的應(yīng)用中都找到了令人滿(mǎn)意的解,從而使得該算法在工程領(lǐng)域得到了廣泛應(yīng)用。在遺傳算法中,將n 維決策向量X 用n 個(gè)記號(hào)X i (i =1,2,n所組成的符號(hào)串表示為X =X 1X 2,X n

9、 。其中每個(gè)X i 可以看成一個(gè)遺傳基因,它的所有可能取值稱(chēng)為等位基因。這樣X(jué) 可以看成是由n 個(gè)遺傳基因所組成的染色體。一般情況第24卷第4期2007年4月計(jì)算機(jī)應(yīng)用研究Application R esearc h of C o m putersVo.l 24,N o .4April 2007下,染色體的長(zhǎng)度n 是固定的,但對(duì)某些問(wèn)題n 也可以是變化的。編碼所形成的排列形式是個(gè)體X 的基因型,與之對(duì)應(yīng)的值是個(gè)體X 的表現(xiàn)型。通常個(gè)體的表現(xiàn)型與基因型是一一對(duì)應(yīng)的,但有時(shí)也允許基因型與表現(xiàn)型是多對(duì)一的關(guān)系。對(duì)于每一個(gè)個(gè)體X,要按照一定的規(guī)則確定其適應(yīng)度。個(gè)體X 的適應(yīng)度與其對(duì)應(yīng)的表現(xiàn)型的目標(biāo)函數(shù)

10、值相關(guān)聯(lián),X 越接近目標(biāo)函數(shù)的最優(yōu)點(diǎn),其適應(yīng)度越大;反之,其適應(yīng)度越小11。生物的遺傳過(guò)程主要是通過(guò)染色體之間的重組和染色體變異來(lái)完成的。與此對(duì)應(yīng),遺傳算法中最優(yōu)解的搜索過(guò)程也模仿生物的遺傳過(guò)程,使用遺傳算子作用于群體P (t,得到下一代群體P (t +1。遺傳算子主要包括下面三種:(1選擇。根據(jù)各個(gè)體的適應(yīng)度,按照一定的規(guī)則或方法,從第t 代群體P (t中選擇一些優(yōu)良的個(gè)體遺傳到下一代群體P (t +1中。(2重組。將群體P (t內(nèi)的各個(gè)體隨機(jī)搭配成對(duì);對(duì)每一對(duì)個(gè)體,以某個(gè)概率(稱(chēng)為重組概率交換它們之間的部分染色體。(3變異。對(duì)群體P (t中的每一個(gè)體,以某一概率將某一個(gè)或某一些基因位上的基

11、因值改變成其他等位基因?；镜淖儺愃阕硬僮靼ㄈN:其中兩種是在等位基因中增加一個(gè)父親節(jié)點(diǎn)或刪除一個(gè)父親節(jié)點(diǎn),相當(dāng)于在網(wǎng)絡(luò)結(jié)構(gòu)中增加或刪除一條指向變量的弧;第三種變異算子是逆轉(zhuǎn)一條弧,這可以通過(guò)刪除一條從父親到孩子的弧,添加一條從孩子到父親的弧來(lái)實(shí)現(xiàn)。2 小生境遺傳算法遺傳算法主要的問(wèn)題就是算法最終并不能保證收斂到全局最優(yōu)解,而過(guò)早地收斂到某個(gè)局部極值點(diǎn)。產(chǎn)生這一現(xiàn)象的根源在于每一代群體進(jìn)化完成后,必須通過(guò)選擇算子按照適應(yīng)度優(yōu)先原則挑選出適應(yīng)度較好的個(gè)體形成下一代種群。那么就會(huì)有一部分個(gè)體被淘汰,這可能造成一些有價(jià)值的模式丟失;同時(shí)也會(huì)使得一些早期適應(yīng)度較好的個(gè)體迅速占領(lǐng)種群。這樣就導(dǎo)致無(wú)法得

12、到最優(yōu)解。雖然遺傳操作中的變異算子可以對(duì)早熟現(xiàn)象產(chǎn)生一定的抑制作用,可以增加新模式的產(chǎn)生,但過(guò)高的變異概率會(huì)使算法趨于隨機(jī)搜索,導(dǎo)致算法出現(xiàn)振蕩而不容易收斂,使得搜索性能下降。需要在算法中引入一種機(jī)制,既可以保證種群的多樣性,同時(shí)又能保證算法的高效性。關(guān)于這方面針對(duì)經(jīng)典遺傳算法的改進(jìn)工作已經(jīng)進(jìn)行了很多。其中小生境(N i che技術(shù)與經(jīng)典遺傳算法的結(jié)合取得了很好的效果。在自然界中,/物以類(lèi)聚,人以群分0的小生境現(xiàn)象普遍存在。生物總是傾向于與自己特性、形狀相類(lèi)似的生物生活在一起。受此啟發(fā),近年來(lái)人們將小生境現(xiàn)象引入到遺傳算法中。實(shí)踐證明,這一技術(shù)對(duì)于改善遺傳算法的全局收斂性能具有良好的效果12。

13、基于此,在本文算法中采用了將典型小生境技術(shù)12結(jié)合最優(yōu)保留策略13的最優(yōu)選擇方法來(lái)進(jìn)行種群的選擇。具體思想為:首先隨機(jī)地把整個(gè)群體分解成若干個(gè)小生境(子種群。父代個(gè)體的交叉操作僅限于各個(gè)小生境內(nèi)部獨(dú)立進(jìn)行;子種群之間不進(jìn)行交叉操作。在每個(gè)小生境的交叉操作后立即應(yīng)用最優(yōu)選擇機(jī)制,即小生境中的全體父代個(gè)體和由它 們繁殖的全體子代個(gè)體共同競(jìng)爭(zhēng),從中找出當(dāng)前群體中適應(yīng)度最好的個(gè)體;然后,將除當(dāng)前最佳個(gè)體外的其余個(gè)體按照適應(yīng)度大小進(jìn)行排序,并運(yùn)用輪盤(pán)賭機(jī)制選擇優(yōu)良個(gè)體保留到下一代。若當(dāng)前的最好個(gè)體t c 優(yōu)于迄今為止的最佳個(gè)體t ,則當(dāng)前最差個(gè)體被迄今為止的最佳個(gè)體取代,并復(fù)制當(dāng)前的最好個(gè)體t c 作為

14、迄今為止的最佳個(gè)體t ;否則,僅用迄今為止的最佳個(gè)體t 取代當(dāng)前的最好個(gè)體t c ,變異操作也在各個(gè)小生境中按概率P m 進(jìn)行,對(duì)小生境中的最佳個(gè)體變異時(shí)應(yīng)用(1+1選擇,以保證全局收斂性,對(duì)其他個(gè)體僅作變異,不作選擇。各個(gè)子種群之間也存在競(jìng)爭(zhēng)。首先計(jì)算各個(gè)子種群的平均適應(yīng)度,適應(yīng)度大的子種群能獲得較大種群數(shù)目,而適應(yīng)度較小的子種群就只有較小的種群數(shù)目。但為了保持種群的多樣性,必須限制優(yōu)勢(shì)子種群的規(guī)模以及保護(hù)劣勢(shì)子種群。這樣就需要人為地規(guī)定一個(gè)最大種群規(guī)模S m ax 和最小種群規(guī)模S m in 。如果一個(gè)最小種群規(guī)模的子種群在經(jīng)歷幾代進(jìn)化后,依然無(wú)法改進(jìn)平均適應(yīng)度,則將該子種群淘汰;而且,如

15、果兩個(gè)子種群之間適應(yīng)度分布很接近,那么同樣淘汰其中一個(gè)。當(dāng)一個(gè)子種群被淘汰后,就隨機(jī)生成一個(gè)新的子種群來(lái)代替。一輪進(jìn)化操作完成后,將各個(gè)子種群的最優(yōu)秀的個(gè)體復(fù)制到精華種群中,然后在精華種群中實(shí)施與其他種群相似的進(jìn)化操作,并產(chǎn)生出優(yōu)秀個(gè)體。3 E M-NGA 算法針對(duì)數(shù)據(jù)有缺失的情況,利用E M 算法解決數(shù)據(jù)不完整情況下的結(jié)構(gòu)學(xué)習(xí)。算法的基本思想是:首先從初始群體中任意選擇一個(gè)個(gè)體,也就是一個(gè)初始的網(wǎng)絡(luò)結(jié)構(gòu);再根據(jù)這個(gè)網(wǎng)絡(luò)結(jié)構(gòu)和缺失的數(shù)據(jù)計(jì)算E M 算法中的E 步(求期望的計(jì)算;然后對(duì)E 步的結(jié)果求極大值,得到補(bǔ)充的數(shù)據(jù);在補(bǔ)充完整的數(shù)據(jù)之上進(jìn)行上述的小生境遺傳算法操作;一輪完成后,得到一個(gè)最優(yōu)

16、個(gè)體,在這個(gè)最優(yōu)個(gè)體上,重復(fù)以上的E M 算法。另外,一個(gè)變量可以從沒(méi)有父親到有n -1個(gè)父親。那么,一個(gè)等位基因可以有Emi =1C i n -1種取值。其中m 是每個(gè)變量可以具有的最大父親節(jié)點(diǎn)數(shù)目。由于本文的目標(biāo)是學(xué)習(xí)盡量簡(jiǎn)單的網(wǎng)絡(luò)結(jié)構(gòu),限制變量的父親節(jié)點(diǎn)數(shù)目是合理的。另外,經(jīng)過(guò)交叉和變異操作后,可能產(chǎn)生出非法結(jié)構(gòu),即產(chǎn)生出有向循環(huán)圖。如出現(xiàn)了有向循環(huán)圖,則將其適應(yīng)度設(shè)成一個(gè)較低的值。在算法中允許出現(xiàn)非法結(jié)構(gòu)的原因是,非法結(jié)構(gòu)中可能蘊(yùn)涵著較好的局部結(jié)構(gòu),可以通過(guò)交叉、變異等操作遺傳給下一代。因此,在遺傳操作產(chǎn)生新的個(gè)體后,需要兩步檢查:檢查新個(gè)體是否滿(mǎn)足每個(gè)變量最多有m 個(gè)父親的約定。如果

17、某個(gè)等位基因不滿(mǎn)足約定,有兩種解決方法:隨機(jī)地選擇k 個(gè)父親(0k m ;采用局部?jī)?yōu)化的方法,選出不超過(guò)m 個(gè)父親的最優(yōu)子集。顯然前者盲目性強(qiáng)、效果差,因此本文采用后者。判斷新個(gè)體是否為非法結(jié)構(gòu),并給非法結(jié)構(gòu)的適應(yīng)度賦予一個(gè)較小的值。E M-NGA 示意圖如圖1所示。E M-NGA (E M-N ich i ng GA ,主要針對(duì)M yers W.和F ried -m an 等人的算法進(jìn)行了改進(jìn)。算法的過(guò)程如下:#101#第4期黃 浩等:基于小生境遺傳算法的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)算法研究(1使用精華種群中最優(yōu)秀的個(gè)體(如果是算法首次執(zhí)行,那么就隨機(jī)生成一個(gè)初始網(wǎng)絡(luò)Sc,利用E M算法對(duì)不完整數(shù)據(jù)集

18、D進(jìn)行完備化,得到完整的數(shù)據(jù)集Dc。(2如果算法是首次執(zhí)行,那么就隨機(jī)生成k組初始化網(wǎng)絡(luò)結(jié)構(gòu),形成k個(gè)小生境,每一組保持r個(gè)個(gè)體;否則就直接執(zhí)行(3,進(jìn)行下一輪進(jìn)化。(3對(duì)任意一個(gè)小生境初始群體S$,按概率Pc 和Pm進(jìn)行交叉或變異操作。如果變異操作在該種群的最優(yōu)個(gè)體t上發(fā)生,那么必須在變異前和變異的兩個(gè)個(gè)體中選擇更好的個(gè)體,而其余變異操作后不作選擇。這樣就得到進(jìn)化后的群體S$c。其中,Pc 和Pm分別表示進(jìn)行交叉和變異操作的概率;(4對(duì)于S$c中的每一個(gè)網(wǎng)絡(luò)S,進(jìn)行如下幾步:如果網(wǎng)絡(luò)S不滿(mǎn)足每個(gè)變量最多有m個(gè)父親的約定,則采用局部?jī)?yōu)化方法,選出不超過(guò)m個(gè)父親的最優(yōu)父節(jié)點(diǎn)集合。檢查網(wǎng)絡(luò)S是否包

19、含非法結(jié)構(gòu),即判斷網(wǎng)絡(luò)S中是否存在有向環(huán)。如果網(wǎng)絡(luò)S包含非法結(jié)構(gòu),則給網(wǎng)絡(luò)S賦予一個(gè)較小的適應(yīng)度;否則,按照下面的公式計(jì)算其適應(yīng)度FS :FS=M DL_score(S B Dc 。其中,M DL_score(S B Dc就是網(wǎng)絡(luò)S與數(shù)據(jù)集Dc的M DL評(píng)價(jià)。計(jì)算網(wǎng)絡(luò)S的被選擇概率PS: P S=rank(F S/r j(r j+1/2其中,rank(FS 表示適應(yīng)度FS的等級(jí),它的值根據(jù)FS的大小來(lái)劃分;rj表示進(jìn)化群體的規(guī)模。(5按照S$c中每個(gè)網(wǎng)絡(luò)S的選擇概率PS和輪盤(pán)賭的機(jī)制選取rj個(gè)個(gè)體進(jìn)入下一代,并更新S$;然后從更新的種群中選擇最優(yōu)的個(gè)體t c。如果t c優(yōu)于迄今為止的最佳個(gè)體t

20、,則當(dāng)前最差個(gè)體被迄今為止的最佳個(gè)體取代,并復(fù)制當(dāng)前的最好個(gè)體t c作為迄今為止的最佳個(gè)體t;否則,僅用迄今為止的最佳個(gè)體t取代當(dāng)前的最好個(gè)體t c。(6選出每個(gè)子群中的最優(yōu)秀個(gè)體,記錄到每個(gè)子群中,同時(shí)將最優(yōu)個(gè)體復(fù)制到精華種群。(7計(jì)算各個(gè)子群的平均適應(yīng)度,比較子群的適應(yīng)度相似程度,相似的兩個(gè)子群將淘汰其中一個(gè),隨機(jī)生成另外一個(gè)子群代替;同時(shí)對(duì)種群數(shù)目為Sm i n的子群連續(xù)進(jìn)化的代數(shù)進(jìn)行計(jì)數(shù),超過(guò)預(yù)定代數(shù)的子群將被淘汰。同樣隨機(jī)生成另外一個(gè)子群取而代之。(8在精華種群中進(jìn)行與每個(gè)子群相似的遺傳進(jìn)化操作。(9在精華種群中選取S c,使得FS c =m ax argS(FS。如果FS c &g

21、t;FS c,則Sc=S c。判斷算法終止條件是否滿(mǎn)足。如果滿(mǎn)足則退出;否則,轉(zhuǎn)(1繼續(xù)進(jìn)化。在(4中,判斷網(wǎng)絡(luò)S是否包含有向環(huán),可以用函數(shù)Is_cy-cli c(S實(shí)現(xiàn),如下所示:Function Is_cycli c(S/如果網(wǎng)絡(luò)S中包含有向環(huán),返回/真0;否則,返回/假0For each X I U DoAncestor(X=Get_ancestor(X,X,<If X I Ancestor(XTh en Ret urn(trueReturn(fals e;Functi on Get_ancestor(X,X c,Ancest or(X/變量X的所有祖先,并用Ancestor(X表

22、示For each V I PX cDo/P X c表示變量X c的父節(jié)點(diǎn)集合If V=X ThenAncestor(X=Ancestor(X+V;/V表示由變量V構(gòu)成的集合break;/跳出循環(huán)E l se ifV|An cest or(XThenAncestor(X=Ancestor(X+V;Ancestor(X=Get_ancestor(X,V,An ces t or(X;Return(Ancest or(X;4試驗(yàn)分析在與M yers W.等人的EA算法和F r i ed m an的SE M算法進(jìn)行試驗(yàn)比較時(shí),使用了M yersW.等人9所用的A SI A網(wǎng)絡(luò)。利用A SIA網(wǎng)絡(luò),隨機(jī)

23、生成3000個(gè)訓(xùn)練樣本。算法分別在包含0、5%、15%和30%的缺值數(shù)據(jù)情況下運(yùn)行。實(shí)驗(yàn)結(jié)果是每一種缺值情況下10次運(yùn)行的平均值;算法終止條件也是連續(xù)進(jìn)化2000代。每一次使用學(xué)習(xí)到的最/好0網(wǎng)絡(luò)計(jì)算其對(duì)數(shù)損失。此外,初始進(jìn)化群體由下面的方法獲得:在上述存在缺失數(shù)據(jù)的3000個(gè)樣本中,用一個(gè)計(jì)算機(jī)程序創(chuàng)造一個(gè)假想的完備數(shù)據(jù)集,在完備數(shù)據(jù)集條件下選擇出一些較好的網(wǎng)絡(luò)結(jié)構(gòu)作為初始群體。當(dāng)前的候選網(wǎng)絡(luò)從初始群體中隨機(jī)產(chǎn)生。在試驗(yàn)中,將變異概率和交叉概率分別設(shè)置為0105和015;群體規(guī)模Sm in=30,Sm ax=100。兩種算法的對(duì)數(shù)損失如圖2(a所示。從圖中可以看出,隨著缺值數(shù)據(jù)的增加,兩種算

24、法的預(yù)測(cè)精度都有所下降。EA 和E M-NGA在0、5%和15%的缺值情況下都能發(fā)現(xiàn)比較好的網(wǎng)絡(luò)結(jié)構(gòu)。而當(dāng)缺值數(shù)據(jù)達(dá)到30%時(shí),兩者的預(yù)測(cè)精度顯著下降。整體而言,E M-NGA的性能優(yōu)于M yers W.的EA方法,特別是在有30%缺值數(shù)據(jù)的情況下。圖2(b是對(duì)這三個(gè)算法進(jìn)行收斂速度和精度的比較,在數(shù)據(jù)缺失20%的情況下, 50m in大概進(jìn)化到第5000代。從圖中可以看出,SE M算法執(zhí)行的速度是最快的,收斂速度也是最快的,但與另外兩個(gè)算法比較發(fā)現(xiàn),SE M所學(xué)習(xí)到的精度往往會(huì)差一些。這說(shuō)明SE M 算法陷入了局部極值中,而且數(shù)據(jù)缺失比例越大,出現(xiàn)這種情況的概率就越大。說(shuō)明在數(shù)據(jù)不完整時(shí),解

25、空間會(huì)變得不光滑,會(huì)出現(xiàn)很多局部極值,SE M算法容易陷入局部極值而無(wú)法發(fā)現(xiàn)更好的解。遺傳算法的表現(xiàn)就更魯棒一些。比較E A和E M-NGA發(fā)現(xiàn),最終兩個(gè)算法能收斂到比SE M算法更好的解,但E M-NGA收斂的速度更快,收斂的結(jié)果也更好,而且收斂的一致性更好一些。分析認(rèn)為,E M-NGA在每一代進(jìn)化中都會(huì)記錄下最優(yōu)個(gè)體,這保證了算法最終會(huì)收斂到最優(yōu)解,同時(shí)能加快算法收斂的速度;同時(shí),小生境技術(shù)使得種群的多樣性得到保證,使算法在收斂行為上表現(xiàn)出更好的一致性和穩(wěn)定性。最后通過(guò)試驗(yàn)比較變異概率與交叉概率對(duì)E M-NGA算法的影響,實(shí)驗(yàn)結(jié)果如圖3所示。從圖中可以看出,變異概率的選擇對(duì)算法會(huì)有比較明顯

26、的影響。當(dāng)變異概率達(dá)到011時(shí),算法表現(xiàn)出明顯的收斂不穩(wěn)定情況,而在變異概率為0105和#102#計(jì)算機(jī)應(yīng)用研究2007年0101時(shí),算法都表現(xiàn)了良好的收斂特性,并且變異概率為0101時(shí),收斂更早,而且收斂曲線更平坦;交叉概率對(duì)整個(gè)算法的收斂行為影響并不大,只是在算法開(kāi)始階段會(huì)表現(xiàn)得略微不同。算法中種群數(shù)目的選擇直接參照了文獻(xiàn)8 。參考文獻(xiàn):1COOPER G F ,HERSKOVI TS E.A bayes i an m et h od f or t he i nduc -ti on of p robab ili sti c net w orks from data J.M achine L

27、earning ,1992,9(4:309-347.2H ECKER M AN D.A t u torial on learn i ng b ayes i an n et w or k,M SR -TR-95-06R.S.l :M icrosoftResearch,1995.3LAM W,BACCHUS F .Learn i ng bayes i an belief n et w ork s :an ap -proach based on the M DL p ri nci p l e J .Computati ona l I ntell -i gence ,1994,10(4:269-293

28、.4FR I ED M AN N .The bayes i an stru ctural E M al gorith m:the 14th Con-ference on Uncert a i nty i n Artifi cial Intelligen ce C .San M at eo :M organ K auf mann,1998:80-89.5FRI ED M AN N .Learn i ng belief n et w or k s i n t he presence of m issing values and hidden variables :p roceed i ngs of

29、 t h e 14th Inter n ati on al C on f eren ce on M ach i n e Learn i ngC.N ashville :M organ Kau f m ann ,1997:125-133.6GE I GER D ,M EEK C.G raph i calm odels and exponenti al f am ilies :the 14th Con ference on Uncert a i nty i n A rtifici al I n telli genceC .San M ateo :M organ K auf m ann ,1998:

30、156-164.7SETT I M I R,S M I TH J Q.On t h e geo m etry of bayesian graph icalm o -delsw it h h i dden variab l es :the 14t h Internati onal Joi nt Con-ference on Arti fi cial I n telli genceC .San Francisco :M organ Kau f m ann ,1998:472-479.8LARRANAGA P ,POZ A M.Stru cture l earn i ng of bayesian n

31、et w orks by genetic al gori thm s :a perf or m ance anal ys i s of contro l para m et ers J .I EEE Journal on Pattern A na l ys i s and M achine I n tell -i gence ,1996,18(9:912-926.9M YERS J W,LASKEY K B,DE J ONG K A.L ear n i ng b ayes i an ne-tw ork s fro m i nco mp lete dat a us i ng evol u tio

32、nary al gorith m s :the Genetic and Evo l uti onary C o m putati on Con feren ceC .S an M ateo :M organKau f m ann ,1999:458-465.10M YERS J W,LASKEY K B,LEVI TT T S.Learn i ng bayes i an ne-tw ork s fro m i n co m plete data w it h stochas tic s earch algorit hm s :t he Un -cert a i nty i n Arti fi

33、cial In telli genceC .San Franci sco :M organ Kau-f mann Pub lis h ers ,1999:476-485.11田鳳占.貝葉斯網(wǎng)絡(luò)方法研究D.北京:清華大學(xué),2002.12J ELASI TYM ,DO M B I T .GAS,a con cep t on m odeli ng s peci es i n ge -netic al gorit hm J.Artifici a l Intelligence ,1998,99(1:1-19.13金菊良,楊曉華,丁晶.標(biāo)準(zhǔn)遺傳算法的改進(jìn)方案加速遺傳算法J.系統(tǒng)工程理論與實(shí)踐,2001,2

34、1(4:8-13.(上接第99頁(yè)表2 各實(shí)現(xiàn)結(jié)構(gòu)性能綜合比較等級(jí)平穩(wěn)性能可靠性(當(dāng)p =P i 1P i 2P i 3P i 4P i 5011015018T c 3優(yōu)優(yōu)優(yōu)優(yōu)優(yōu)優(yōu)優(yōu)差T 1中良良良中優(yōu)中差T 2優(yōu)良良良良良差差T 3優(yōu)優(yōu)優(yōu)優(yōu)優(yōu)中差差5 結(jié)束語(yǔ)不同于以往的生物啟發(fā)網(wǎng)絡(luò)安全研究,B M N S M 首次充分考慮了生物界(人類(lèi)的立體特征,為該領(lǐng)域的研究提供了一個(gè)新的研究視角。作為B MN S M 的核心,TNP 模式實(shí)現(xiàn)結(jié)構(gòu)的選擇將直接決定著該模型各項(xiàng)性能的發(fā)揮,通過(guò)對(duì)傳統(tǒng)初級(jí)結(jié)構(gòu)T 1、進(jìn)化結(jié)構(gòu)T 2和T 3,以及高級(jí)結(jié)構(gòu)T c 3的平穩(wěn)性能和可靠性各項(xiàng)指標(biāo)的定量分析比較,得出了T c 3是TN P 模式較理想的實(shí)現(xiàn)結(jié)構(gòu)這一結(jié)論。將來(lái)的研究工作將集中在T c 3的具體實(shí)現(xiàn)上。參考文獻(xiàn):1FORREST S,PERELSON A,ALLEN L ,et a l .Sel-f nonselfd iscri m -i nati on i n a co m puter :p roceed i ngs of t he I EEE Sy m pos i um on Re -search i n Sec u rit y and PrivacyC .LOS A la m ilos :I EEE Co m