混合魚群優(yōu)化算法的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)

陳夢潔，萬　源，吳克風(fēng)，童恒慶

(1.武漢理工大學(xué) 理學(xué)院，湖北 武漢 430070；2.華中科技大學(xué) 自動化學(xué)院，湖北 武漢 430074)

?

混合魚群優(yōu)化算法的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)

陳夢潔1，萬源1，吳克風(fēng)2，童恒慶1

(1.武漢理工大學(xué) 理學(xué)院，湖北 武漢 430070；2.華中科技大學(xué) 自動化學(xué)院，湖北 武漢 430074)

摘要：針對從數(shù)據(jù)集學(xué)習(xí)貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)準(zhǔn)確率不高的問題，提出了一種基于混合魚群優(yōu)化算法的結(jié)構(gòu)學(xué)習(xí)算法。首先，利用互信息和最大似然樹生成初始無向圖;然后，由無向圖的邊隨機(jī)生成初始種群，將粒子群算法的個(gè)體記憶和交流意識引入魚群算法的行為模式，減小算法搜索行為的盲目性;最后，將優(yōu)勢遺傳算法的變異和交叉算子應(yīng)用于算法的尋優(yōu)過程。仿真實(shí)驗(yàn)結(jié)果驗(yàn)證了改進(jìn)后的算法具有更強(qiáng)的尋優(yōu)能力。

關(guān)鍵詞：貝葉斯網(wǎng)絡(luò)；結(jié)構(gòu)學(xué)習(xí)；粒子群算法；人工魚群算法；自適應(yīng)遺傳算法

0引言

貝葉斯網(wǎng)絡(luò)(Bayesian network，BN)結(jié)合了圖論和概率論，善于解決不確定性知識的表達(dá)和推理問題。BN被廣泛應(yīng)用在人工智能、自動控制和機(jī)器學(xué)習(xí)等領(lǐng)域。BN結(jié)構(gòu)學(xué)習(xí)的方法[1-4]可分為3類：基于條件獨(dú)立性測試的方法、基于評分搜索的方法和混合算法。

由于尋找最優(yōu)貝葉斯網(wǎng)絡(luò)是一個(gè)非確定性多項(xiàng)式(non-deterministic polynomial，NP)難題，網(wǎng)絡(luò)結(jié)構(gòu)空間大小會隨著網(wǎng)絡(luò)節(jié)點(diǎn)個(gè)數(shù)的增加呈指數(shù)增加，因此，BN結(jié)構(gòu)學(xué)習(xí)的方法主要采用啟發(fā)式搜索方法。文獻(xiàn)[3]將基于免疫策略的二進(jìn)制粒子群算法應(yīng)用于BN結(jié)構(gòu)學(xué)習(xí)，算法收斂較快，但準(zhǔn)確度仍待提高。文獻(xiàn)[4]提出了基于改進(jìn)粒子群優(yōu)化算法的BN結(jié)構(gòu)學(xué)習(xí)方法，通過節(jié)點(diǎn)的互信息限制網(wǎng)絡(luò)結(jié)構(gòu)的搜索空間，適用于節(jié)點(diǎn)較少的網(wǎng)絡(luò)結(jié)構(gòu)。文獻(xiàn)[5]提出了基于進(jìn)化算法的BN結(jié)構(gòu)學(xué)習(xí)方法，學(xué)習(xí)效果較好，但是編碼方式較復(fù)雜，對計(jì)算機(jī)性能要求較高，且易陷入局部最優(yōu)。文獻(xiàn)[6]將云自適應(yīng)遺傳算法和魚群算法混合，用于BN結(jié)構(gòu)學(xué)習(xí)，可以避免陷入局部最優(yōu)，但由于尋優(yōu)過程具有隨機(jī)性，初始種群的隨機(jī)性較大，影響了算法的準(zhǔn)確度。

基于文獻(xiàn)[5-6]的方法，本文根據(jù)粒子群算法中粒子對自身經(jīng)歷的最優(yōu)位置和全局當(dāng)前最優(yōu)位置的認(rèn)知意識，在魚群算法的“聚群”和“追尾”行為模式中引入“回溯”和“協(xié)作”行為，將優(yōu)勢遺傳算法的變異和交叉算子應(yīng)用于魚個(gè)體位置的更新過程，形成改進(jìn)的混合魚群優(yōu)化算法。并將算法應(yīng)用于BN結(jié)構(gòu)學(xué)習(xí)中，驗(yàn)證算法的準(zhǔn)確性。

1改進(jìn)的魚群優(yōu)化算法

人工魚群算法[7](artificial fish swarm algorithm，AFSA)通過模擬魚群的聚群、追尾、覓食以及隨機(jī)行為構(gòu)造人工魚。根據(jù)當(dāng)前所處的環(huán)境狀態(tài)，人工魚會選擇“聚群或覓食”和“追尾或覓食”兩種行為模式中更優(yōu)的一種行為模式來執(zhí)行，并在公告板上記錄最佳位置，當(dāng)達(dá)到最大迭代次數(shù)時(shí)，人工魚會聚集在極值周圍，從而實(shí)現(xiàn)全局最優(yōu)。

傳統(tǒng)魚群算法的尋優(yōu)搜索行為具有隨機(jī)性，“聚群或覓食”和“追尾或覓食”兩種行為模式又使得算法搜索行為具有局限性。本文算法根據(jù)粒子群算法[8]中粒子對自身經(jīng)歷的最優(yōu)位置和全局當(dāng)前最優(yōu)位置的認(rèn)知意識，在基本魚群算法的“聚群”和“追尾”行為模式中加入“回溯”和“協(xié)作”行為，擴(kuò)充魚群算法的行為模式，使得魚群行為模式更加全面，增加最優(yōu)位置產(chǎn)生的概率，減小算法搜索行為的盲目性。覓食行為使得魚群可以任意游動到新位置，增加了種群的多樣性，有利于跳出局部最優(yōu)。

2基于混合魚群優(yōu)化算法的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)

2.1初始種群的生成

互信息可以反映變量之間的相關(guān)關(guān)系，互信息越大，表明變量之間的依賴程度越大，變量間存在有向邊的可能性就越大[9]。通過變量之間的互信息，可以排除一些不合理的網(wǎng)絡(luò)結(jié)構(gòu)，從而縮小搜索空間。

其中：I(Xi,Xj)為變量Xi與變量Xj之間的互信息；xm與xn分別為變量Xi與變量Xj的各個(gè)取值；P(xm)為變量Xi的概率；P(xn)為變量Xj的概率；P(xm,xn)為變量Xi與變量Xj之間的概率。

采用文獻(xiàn)[10]提出的最大生成樹法獲得無向圖，以該無向圖為基礎(chǔ)生成初始種群。首先，計(jì)算出任意兩個(gè)節(jié)點(diǎn)之間的互信息；然后，根據(jù)互信息的大小賦予節(jié)點(diǎn)之間的邊權(quán)重；再根據(jù)邊權(quán)重生成最大權(quán)重遍歷樹即最大生成樹，使得生成樹中所有邊的權(quán)重之和最大。

由最大生成樹即無向圖隨機(jī)生成初始種群個(gè)體，故初始種群所對應(yīng)的網(wǎng)絡(luò)結(jié)構(gòu)的邊只能從這里的無向圖中的邊隨機(jī)產(chǎn)生。該無向圖的邊作為優(yōu)化最佳貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)的待選邊，減弱了初始種群對算法的影響，算法的收斂速度也有較大的提高。

2.2評分標(biāo)準(zhǔn)

度量網(wǎng)絡(luò)結(jié)構(gòu)G與樣本數(shù)據(jù)集D匹配程度的函數(shù)稱作評分函數(shù)。貝葉斯信息準(zhǔn)則[11](Bayesian information criterion，BIC)是BN結(jié)構(gòu)學(xué)習(xí)算法常用的評分函數(shù)，依照模型的優(yōu)參對數(shù)似然度和模型復(fù)雜度的罰項(xiàng)來選擇模型，可以避免過度擬合。故采用BIC作為本文算法的適應(yīng)度函數(shù)。

2.3基于自適應(yīng)遺傳算子的魚群位置更新策略

(1)魚個(gè)體在當(dāng)前狀態(tài)X下，當(dāng)視距范圍內(nèi)伙伴數(shù)目n>1且擁擠度m<δ，m是隨機(jī)產(chǎn)生的隨機(jī)數(shù)，且m∈(0,1)，即保證周圍不會過分擁擠的情況下，分別執(zhí)行聚群、追尾、回溯和協(xié)作行為。將遺傳算法中常用的單點(diǎn)交叉應(yīng)用于這4種行為，即選取當(dāng)前個(gè)體與待配對個(gè)體進(jìn)行交叉。若兩個(gè)個(gè)體對應(yīng)的編碼行向量分別為111010101和101010111，隨機(jī)選取一個(gè)交叉位假定為第5位，則交叉后產(chǎn)生的新個(gè)體為111010111和101010101。

(Ⅱ)否則Pc=k1。

同理，追尾行為是以當(dāng)前魚個(gè)體X1與視距范圍內(nèi)最優(yōu)位置的個(gè)體Xb交叉；回溯行為是以當(dāng)前魚個(gè)體X1與自身所經(jīng)歷最優(yōu)位置的個(gè)體Xpb交叉；協(xié)作行為則是以當(dāng)前魚個(gè)體X1與當(dāng)前迭代過程整個(gè)魚群最優(yōu)位置的個(gè)體Xgb交叉。

交叉率Pc的取值采用優(yōu)勢遺傳的思想，使高適應(yīng)度的個(gè)體以較大的交叉率進(jìn)行有利于優(yōu)勢基因的遺傳，與傳統(tǒng)的遺傳算法相比，優(yōu)勢遺傳能夠保留精英個(gè)體的特性[14]。但為了保護(hù)種群多樣性，k1值不宜過小，k1值宜設(shè)定為0.7～1.0，k2值設(shè)定為0.5～0.7。

魚個(gè)體試探進(jìn)行聚群、追尾、回溯和協(xié)作這4種行為后，會分別計(jì)算出4種行為所產(chǎn)生個(gè)體的新適應(yīng)度值。采用行為選擇策略，根據(jù)適應(yīng)度的優(yōu)劣，選擇最有利的行為并執(zhí)行。

(2)當(dāng)n<1或者m≥δ，魚個(gè)體執(zhí)行覓食行為，將遺傳算法的變異算子應(yīng)用于覓食行為。變異過程是隨機(jī)選取一個(gè)變異位，并對變異位的元素進(jìn)行由1變0或由0變1的變換。變異過程本質(zhì)上是對原來的網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行加邊、減邊和反轉(zhuǎn)邊的操作。

(Ⅱ)否則Pm=k4。

變異率Pm的取值表明:在高適應(yīng)度的個(gè)體以較小的變異率進(jìn)行變異以保留優(yōu)良個(gè)體的同時(shí)，低適應(yīng)度的個(gè)體以較高的概率進(jìn)行變異，增大變異出優(yōu)勢個(gè)體的概率，利于優(yōu)勢個(gè)體的產(chǎn)生，跳出局部最優(yōu)。故k3值一般設(shè)定為0.4～0.5，k4值一般設(shè)定為0.3～0.5。

(3)環(huán)路修正

為了保證魚個(gè)體更新位置后對應(yīng)網(wǎng)絡(luò)結(jié)構(gòu)的合法性，需要對非法網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行修復(fù)。具體步驟如下：

步驟1：根據(jù)更新后的網(wǎng)絡(luò)結(jié)構(gòu)，得到網(wǎng)絡(luò)結(jié)構(gòu)對應(yīng)的鄰接矩陣。

步驟2：若矩陣對角線上的元素不都為0，說明網(wǎng)絡(luò)結(jié)構(gòu)存在自循環(huán)，將對角線上值為1的元素替換為0，否則，進(jìn)入步驟3。

步驟3：若矩陣上的元素存在gij=gji=1，則網(wǎng)絡(luò)結(jié)構(gòu)中存在雙向邊，任意選擇其中一個(gè)元素，將其對應(yīng)的值由1替換為0，否則，進(jìn)入步驟4。

步驟4：若矩陣上的元素存在類似于gik=gkj=gji=1的結(jié)構(gòu)，說明網(wǎng)絡(luò)結(jié)構(gòu)存在封閉環(huán)路，隨機(jī)選取閉環(huán)內(nèi)的任意一個(gè)節(jié)點(diǎn)，求出其在閉環(huán)內(nèi)的所有父節(jié)點(diǎn)，并刪除父節(jié)點(diǎn)指向該節(jié)點(diǎn)的邊。

2.4算法的具體實(shí)現(xiàn)步驟

步驟1：初始化魚群種群個(gè)體數(shù)FN、交叉率k1及k2、變異率k3及k4、最大迭代次數(shù)limit等參數(shù)。

步驟2：利用互信息和最大生成樹準(zhǔn)則確定初始無向圖，在無向圖基礎(chǔ)上，生成初始種群。

步驟3：計(jì)算初始種群的所有個(gè)體的BIC得分作為個(gè)體極值，并將最大得分值及個(gè)體記錄在公告板上。

步驟4：While 當(dāng)前迭代次數(shù)≤limit時(shí)

fori=1:FN

步驟5：當(dāng)該編號的魚個(gè)體滿足聚群條件時(shí)，需執(zhí)行“聚群”、“追尾”、“回溯”和“協(xié)作”這4種行為。

步驟6：判斷執(zhí)行4種行為的新個(gè)體是否存在非法結(jié)構(gòu)，若存在，則進(jìn)行環(huán)路修正，否則，保留合法個(gè)體。

步驟7：比較4個(gè)新個(gè)體之間的BIC得分，評定最優(yōu)行為，執(zhí)行并記錄。

步驟8：當(dāng)魚個(gè)體不滿足聚群條件時(shí)，需要執(zhí)行覓食行為，游到新位置。

end

步驟9：記錄當(dāng)前最優(yōu)位置，并更新公告板，迭代次數(shù)加1。

步驟10：當(dāng)達(dá)到最大迭代次數(shù)時(shí)，輸出最優(yōu)貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)及最大得分值。

3仿真實(shí)驗(yàn)

選取貝葉斯基準(zhǔn)網(wǎng)絡(luò)Asia和Alarm進(jìn)行仿真實(shí)驗(yàn)，驗(yàn)證本文算法的有效性，實(shí)驗(yàn)?zāi)康氖歉鶕?jù)數(shù)據(jù)集得到最接近標(biāo)準(zhǔn)網(wǎng)絡(luò)的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)。

表1　本文算法與標(biāo)準(zhǔn)網(wǎng)絡(luò)的BIC評分

分別選取Asia網(wǎng)的1 000組、2 000組、5 000組及10 000組的數(shù)據(jù)集，并將標(biāo)準(zhǔn)網(wǎng)絡(luò)和本文算法各運(yùn)行10次，記錄10次實(shí)驗(yàn)所得的最小BIC評分值，結(jié)果見表1。由表1可知：不管在哪種數(shù)據(jù)集下，10次實(shí)驗(yàn)所得的最小BIC評分值都大于原始結(jié)構(gòu)(標(biāo)準(zhǔn)網(wǎng)絡(luò))的BIC評分值，而且隨著數(shù)據(jù)集樣本量的增加，得分差距變大，說明本文算法的學(xué)習(xí)性能較好。

將本文算法與遺傳魚群算法、離散粒子群算法進(jìn)行比較，驗(yàn)證本文算法在不同數(shù)據(jù)樣本集下的學(xué)習(xí)效果。分別用3種算法對Alarm網(wǎng)絡(luò)學(xué)習(xí)10次，結(jié)果見表2。由表2可知：在與標(biāo)準(zhǔn)Alarm網(wǎng)絡(luò)對比多邊、缺失邊和反向邊的均值時(shí)，本文算法學(xué)習(xí)的網(wǎng)絡(luò)結(jié)構(gòu)與標(biāo)準(zhǔn)網(wǎng)絡(luò)結(jié)構(gòu)的差距最小，特別是在10 000組數(shù)據(jù)集下，差距要明顯小于遺傳魚群算法和離散粒子群算法，驗(yàn)證了本文算法的有效性。

表2　3種算法對Alarm網(wǎng)的學(xué)習(xí)結(jié)果(邊的數(shù)量)

圖1　不同樣本數(shù)據(jù)集下的平均對數(shù)似然　　　損失比較

4結(jié)束語

本文在基本魚群算法的基礎(chǔ)上融入粒子群算法的兩個(gè)重要特征，增強(qiáng)了算法尋優(yōu)的目標(biāo)性，加大了全局搜索的力度，加快了算法收斂。同時(shí)采用優(yōu)勢遺傳理論，使得優(yōu)勢個(gè)體最大限度地被保留，形成改進(jìn)的混合魚群優(yōu)化算法，并應(yīng)用于貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)。仿真實(shí)驗(yàn)結(jié)果驗(yàn)證了本文算法具有更強(qiáng)的學(xué)習(xí)能力和較高的準(zhǔn)確性。下一步工作是采取措施降低算法復(fù)雜度，在小樣本容量的情況下，得到更優(yōu)的網(wǎng)絡(luò)結(jié)構(gòu)。

參考文獻(xiàn)：

[1]LARRANAGA P,KARSHENAS H,BIELZA C,et al.A review on evolutionary algorithms in Bayesian network learning and inference tasks[J].Information sciences,2013,233(2):109-125.

[2]LI Y Y,YANG Y L,ZHU X F,et al.Towards fast and efficient algorithm for learning Bayesian network[J].Wuhan university journal of natural sciences,2015,20(3):214-220.

[3]LI X L,HE X D.A hybrid particle swarm optimization method for structure learning of probabilistic relational models[J].Information sciences,2014,283:258-266.

[4]高曉光,邸若海,郭志高.基于改進(jìn)粒子群優(yōu)化算法的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)[J].西北工業(yè)大學(xué)學(xué)報(bào),2014(5):749-755.

[5]ZHU Y,LIU D,JIA H.A new evolutionary computation based approach for learning Bayesian network[J].Procedia engineering,2011,15:4026-4030.

[6]郭童,林峰.基于混合遺傳魚群算法的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)[J].浙江大學(xué)學(xué)報(bào)(工學(xué)版),2014,48(1):130-135.

[7]XIAO J,ZHENG X,WANG X,et al.A modified artificial fish-swarm algorithm[C]// Intelligent Control and Automation,2006.WCICA 2006.The Sixth World Congress on IEEE,2006:3456-3460.

[8]段其昌,唐若笠,徐宏英,等.粒子群優(yōu)化魚群算法仿真分析[J].控制與決策,2013,28(9):1436-1440.

[9]劉樂樂,田衛(wèi)東.基于屬性互信息熵的量化關(guān)聯(lián)規(guī)則挖掘[J].計(jì)算機(jī)工程,2009,35(14):38-40.

[10]CHOW C,LIU C.Approximation diserete probability distributions with dependence trees[J].IEEE transactions on information theory,1968,14(3):462-467.

[11]DALY R,SHEN Q,AITKEN S.Learning Bayesian networks:approaches and issues[J].Knowledge engineering review,2011,26(2):99-157.

[12]LARRANAGA P,POZA M,YURRAMENDI Y,et al.Structure learning of Bayesian networks by genetic algorithms:a performance analysis of control parameters[J].IEEE transactions on pattern analysis & machine intelligence,1996,18(9):912-926.

[13]趙斌,宿玉佩,蔣念平.一種改進(jìn)型遺傳算法的網(wǎng)格工作流調(diào)度研究[J].河南科技大學(xué)學(xué)報(bào)(自然科學(xué)版),2012,33(3):32-35.

[14]陳世哲,劉國棟,浦欣,等.基于優(yōu)勢遺傳的自適應(yīng)遺傳算法[J].哈爾濱工業(yè)大學(xué)學(xué)報(bào),2007,39(7):1021-1024.

[15]FRIEDMAN N.Learning belief networks in the presence of missing values and hidden variables[C]// Proceedings of the Fourteenth International Conference on Machine Learning.2000:125-133.

基金項(xiàng)目：國家自然科學(xué)基金項(xiàng)目(91324201,81271513)

作者簡介：陳夢潔(1990-),女,河南信陽人,碩士生;萬源(1976-),女,湖北武漢人,副教授,博士,碩士生導(dǎo)師,主要研究方向?yàn)闄C(jī)器學(xué)習(xí)與數(shù)據(jù)挖掘.

收稿日期：2016-01-05

文章編號：1672-6871(2016)04-0041-05

DOI:10.15926/j.cnki.issn1672-6871.2016.04.009

中圖分類號：TP391

文獻(xiàn)標(biāo)志碼：A