趙文強(qiáng) 趙 熙 劉 瀚

（武漢市武昌區(qū)長(zhǎng)虹橋37-1號(hào) 武漢 430064）

基于新型二進(jìn)制自適應(yīng)差分演化算法的貝葉斯網(wǎng)絡(luò)學(xué)習(xí)?

趙文強(qiáng) 趙 熙 劉 瀚

（武漢市武昌區(qū)長(zhǎng)虹橋37-1號(hào) 武漢 430064）

貝葉斯網(wǎng)絡(luò)是處理不確定的專門知識(shí)和推理的最流行的方法，并廣泛應(yīng)用于大量研究領(lǐng)域。貝葉斯網(wǎng)絡(luò)學(xué)習(xí)的主要策略是利用統(tǒng)計(jì)評(píng)分來(lái)選擇最優(yōu)網(wǎng)絡(luò)的候選者。論文提出了基于新型二進(jìn)制自適應(yīng)差分演化算法的貝葉斯網(wǎng)絡(luò)學(xué)習(xí)（BDENBAL），該方法采用一種自適應(yīng)的0∕1矩陣作為比例因子，并通過(guò)交叉和變異算子來(lái)實(shí)現(xiàn)貝葉斯網(wǎng)絡(luò)的學(xué)習(xí)過(guò)程中的信息交換。然后根據(jù)貝葉斯信息標(biāo)準(zhǔn)（BIC）評(píng)分從網(wǎng)絡(luò)空間中選擇貝葉斯網(wǎng)絡(luò)候選者。實(shí)驗(yàn)結(jié)果證明本文提出的方法具有優(yōu)良的性能。

貝葉斯網(wǎng)絡(luò)；差分演化；貝葉斯信息標(biāo)準(zhǔn)

1 引言

隨著人工智能的發(fā)展，Pearl在20世紀(jì)80年代提出了貝葉斯網(wǎng)絡(luò)。如今，貝葉斯網(wǎng)絡(luò)是處理不確定的專門知識(shí)和推理的最流行的方法［1］。由于其強(qiáng)大的概率推理功能，貝葉斯網(wǎng)絡(luò)被應(yīng)用于大量研究領(lǐng)域，例如：專家系統(tǒng)、醫(yī)療系統(tǒng)、制造系統(tǒng)、語(yǔ)音識(shí)別、數(shù)據(jù)挖掘、經(jīng)濟(jì)活動(dòng)分析、軍事對(duì)抗和預(yù)測(cè)［2］。

目前，有兩種策略被應(yīng)用于貝葉斯網(wǎng)絡(luò)學(xué)習(xí)中：一、通過(guò)評(píng)估網(wǎng)絡(luò)節(jié)點(diǎn)間的假定獨(dú)立關(guān)系來(lái)構(gòu)建貝葉斯網(wǎng)絡(luò)［3］；二、利用統(tǒng)計(jì)評(píng)分從網(wǎng)絡(luò)模型空間中選擇典型的候選者。最流行的評(píng)分函數(shù)包括CH評(píng)分［4］、BIC評(píng)分［5］、MDL評(píng)分［6］、AIC評(píng)分［7］等。

由于學(xué)習(xí)貝葉斯網(wǎng)絡(luò)是個(gè)NP難的問(wèn)題［8］，基于啟發(fā)式搜索（例如：隨機(jī)局部搜索、遺傳算法、演化算法）的學(xué)習(xí)算法通常能夠找到近似最優(yōu)貝葉斯網(wǎng)絡(luò)［9］。AMS-EM 學(xué)習(xí)算法采用確定性搜索［10］。AMS-EM的初始網(wǎng)絡(luò)選擇取決于先驗(yàn)概率。選擇不同的初始網(wǎng)絡(luò)結(jié)構(gòu)可能會(huì)造成收斂結(jié)果模型的分布區(qū)不同。因此，AMS-EM可以發(fā)現(xiàn)局部最優(yōu)的網(wǎng)絡(luò)結(jié)構(gòu)。EGA［11］是一個(gè)基于遺傳算法的隨機(jī)搜索算法。和AMS-EM相比，EGA能夠找到最優(yōu)的網(wǎng)絡(luò)結(jié)構(gòu)，因?yàn)樗鼉H編碼網(wǎng)絡(luò)結(jié)構(gòu)并通過(guò)數(shù)學(xué)期望轉(zhuǎn)換不完全數(shù)據(jù)。Friedman將馬爾可夫鏈蒙特卡爾理論（MCMC）應(yīng)用到不完全數(shù)據(jù)的貝葉斯網(wǎng)絡(luò)學(xué)習(xí)中得到EM-MCMC算法［12］，同時(shí)還提出結(jié)構(gòu)化的EM算法（SEM）。SEM算法將EM算法應(yīng)用到網(wǎng)絡(luò)參數(shù)優(yōu)化，并將結(jié)構(gòu)搜索方案應(yīng)用到模型的選擇。

標(biāo)準(zhǔn)差分演化算法（DE）在連續(xù)值搜索空間中具有更快的搜索速度和更高的精確度。DE算法的演化算子會(huì)使該算法很難直接用于離散空間，為了解決此問(wèn)題，Engelbrecht提出二進(jìn)制差分演化算法（BDE）［13］，通過(guò)使用三角函數(shù)實(shí)現(xiàn)了連續(xù)空間到二元空間的轉(zhuǎn)換，標(biāo)準(zhǔn)測(cè)試函數(shù)已證明BDE算法的搜索準(zhǔn)確率要高于二進(jìn)制粒子群優(yōu)化算法。此外，他和Han提出了一種使用邏輯操作代替算術(shù)計(jì)算的新算法來(lái)提高BDE算法在二元空間中的表現(xiàn)。

本文提出了一種用于貝葉斯網(wǎng)絡(luò)學(xué)習(xí)的新型二進(jìn)制自適應(yīng)差分演化算法（BDENBAL）。通過(guò)使用交叉算子和變異算子，BDENBAL算法實(shí)現(xiàn)了貝葉斯網(wǎng)絡(luò)中的信息交換?；贐IC評(píng)分標(biāo)準(zhǔn)，BDENBAL算法從網(wǎng)絡(luò)模型空間中選出了最優(yōu)的典型候選者。

2 背景

2.1 編碼方案

貝葉斯網(wǎng)絡(luò)表示出變量之間的條件概率與有向無(wú)環(huán)圖（DAG）。一個(gè)有向無(wú)環(huán)圖可以表示為（A，B），其中A代表一組頂點(diǎn)，B代表一組邊。一個(gè)貝葉斯網(wǎng)絡(luò)矩陣X（i，j）（i=1，…N，j=1，…N）可以由當(dāng)前的DAG構(gòu)成，如圖1所示。所有矩陣中的元素為0或1。如果點(diǎn)vi和點(diǎn)vj之間存在一條有向邊bij(vi→ vj)，X（i，j）等于1，否則為0。因此，演化算法的熱色體可以被構(gòu)造為(X1,…Xi,…Xd)，其中每一個(gè)遺傳因子都是一個(gè)貝葉斯網(wǎng)絡(luò)矩陣。

2.2 適應(yīng)度函數(shù)

作為選擇模型中的一種典型評(píng)分函數(shù)，貝葉斯信息評(píng)分標(biāo)準(zhǔn)是邊緣似然函數(shù)的大樣本近似［2］。與拉普拉斯近似一致，我們可以獲得大樣本近似G（s|D）來(lái)獲得作為后驗(yàn)概率對(duì)數(shù)的BIC評(píng)分函數(shù)。logG(s|D)可以近似為

上述公式中，D是數(shù)據(jù)集合，s是貝葉斯結(jié)構(gòu)，α*是貝葉斯參數(shù)α的最大似然估計(jì)值，M是樣本數(shù)量。

本文中，BIC評(píng)分被選作二進(jìn)制差分演化貝葉斯網(wǎng)絡(luò)學(xué)習(xí)的適應(yīng)度函數(shù)。在貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)的過(guò)程中，每個(gè)網(wǎng)絡(luò)的候選者對(duì)應(yīng)一個(gè)BIC評(píng)分，學(xué)習(xí)結(jié)果將會(huì)是該網(wǎng)絡(luò)的BIC最大得分。

2.3 循環(huán)規(guī)避

本文中，貝葉斯網(wǎng)絡(luò)矩陣被選作判斷矩陣。貝葉斯網(wǎng)絡(luò)的回路可根據(jù)所有對(duì)角線元素之和來(lái)檢測(cè)。如果貝葉斯網(wǎng)絡(luò)中存在一個(gè)循環(huán)，則總和將不為0，且有循環(huán)的貝葉斯網(wǎng)絡(luò)應(yīng)該被丟棄。

3 算法

本文提出的算法包括更新貝葉斯參數(shù)和在更新后的貝葉斯網(wǎng)絡(luò)的基礎(chǔ)上對(duì)其進(jìn)行選擇。通過(guò)變異算子和交叉算子來(lái)實(shí)現(xiàn)學(xué)習(xí)過(guò)程中的貝葉斯網(wǎng)絡(luò)信息交換。在模型的選擇方面，通過(guò)使用BIC評(píng)分來(lái)達(dá)到貪婪策略的實(shí)現(xiàn)。

3.1 變異操作

標(biāo)準(zhǔn)差分演化算法將基于浮點(diǎn)數(shù)的編碼機(jī)制用于編碼方案。本文提出的BDENBAL算法將一種二元矩陣替代真實(shí)數(shù)字并用于編碼方案中。各元素在各個(gè)位上的值只有1或0。此外，BDENBAL算法在標(biāo)準(zhǔn)差分演化算法中使用邏輯計(jì)算代替了算術(shù)計(jì)算。

對(duì)于某一個(gè)體Si,H;i=1,2,…,NP，如下公式推理可以得到另一個(gè)體Wi,H=(W1i,H+1,W2i,H+1,…,WDi,H+1)：

上述公式中，⊕代表異或運(yùn)算；?代表與運(yùn)算加上或運(yùn)算。

r1，r2和r3是屬于［1，NP］的不同整數(shù)，NP代表群體大小。

Fac代表用于控制變異程度的比例因子。本文中的Fac是和貝葉斯矩陣相同的0∕1矩陣。比例因子Fac可以由如下公式得到：

上述公式中，U1是屬于區(qū)間（0，1）的小數(shù)，R1是屬于區(qū)間（0，1）的隨機(jī)數(shù)字，ε1是閾值。sizeof(DAG)是用來(lái)計(jì)算行數(shù)和列數(shù)的函數(shù)。如果R1小于 ε1，比例因子Fac將生成一個(gè)0∕1矩陣。交叉操作

一個(gè)子代的向量可以由如下公式得到：

其中，對(duì)于 vji,H+1,j∈(1,2,3,…,D)，

上述公式中，CE是相交元素，D代表個(gè)體的長(zhǎng)度，Rb代表隨機(jī)小數(shù)。

3.2 選擇操作

BDENBAL算法在選擇典型的候選者方面提供了一種貪婪策略：

上述公式中，BIC函數(shù)與式（1）相同，如果子代向量vi,H+1的適應(yīng)度值大于父代Si,H的值，下一代Si,H+1將會(huì)被vi,H+1取代。否則，Si,H+1等于Si,H。

3.3 BDENBAL學(xué)習(xí)算法

在BDENBAL算法中，變量Tmp被設(shè)計(jì)用來(lái)緩沖交叉操作生成的貝葉斯網(wǎng)絡(luò)，變量p用來(lái)緩沖子代貝葉斯網(wǎng)絡(luò)。BDENBAL學(xué)習(xí)算法的具體步驟如下：

算法1：BDENBAL算法1：變量：Tmp，p，Loop_M，Loop; ∕初始化2：Loop_M=最大代數(shù)，Loop=0;3：根據(jù)當(dāng)前遺漏值生成變量e;4：while Loop_M＞＝Loop;5：隨機(jī)選擇3個(gè)個(gè)體Sr1,Sr1,Sr1; ∕個(gè)體選擇6：根據(jù)式（2）生成一個(gè)交叉元素Fac 7：當(dāng)j=1時(shí)； ∕變異操作和交叉操作8：根據(jù)式（1）進(jìn)行變異操作；9：根據(jù)式（3）進(jìn)行交叉操作；10：if no Loop in Tmp；11：p{j}=Tmp；12：根據(jù)當(dāng)前子代貝葉斯網(wǎng)絡(luò)和BIC評(píng)分算法，得到BIC評(píng)分。∕BIC評(píng)分13：根據(jù)式（4）進(jìn)行選擇； ∕模型選擇14：Loop=Loop+1；15：End while

4 實(shí)驗(yàn)結(jié)果

本文通過(guò)將SEM算法、EM-MCMC算法、AMS-EM算法、BDENBAL算法分別在MATLAB上實(shí)現(xiàn)的性能進(jìn)行比較，評(píng)價(jià)BDENBAL算法的表現(xiàn)，具體實(shí)驗(yàn)參數(shù)如下表所示。

本文采用平均對(duì)數(shù)損失（LOGLOSS）和適應(yīng)度函數(shù)（BIC）作為性能指標(biāo)。平均對(duì)數(shù)損失可以通過(guò)如下公式計(jì)算：

表1 實(shí)驗(yàn)參數(shù)

1）在100個(gè)訓(xùn)練實(shí)例上的不同算法的性能比較

為了評(píng)價(jià)BDENBAL算法的學(xué)習(xí)能力，我們比較了BDENBAL算法、SEM算法、EM-MCMC算法在4個(gè)節(jié)點(diǎn)、10個(gè)節(jié)點(diǎn)，和32個(gè)節(jié)點(diǎn)條件下的貝葉斯網(wǎng)絡(luò)。圖1～圖3顯示出BDENBAL算法、SEM算法、EM-MCMC算法的LOGLOSS值隨著不同百分比的缺失值（PMV）的變化。PMV在x軸上的對(duì)應(yīng)值為

實(shí)驗(yàn)結(jié)果顯示，所有算法的LOGLOSS值均隨著缺失值百分比的提升而呈遞減趨勢(shì)。在所有情況下，BDENBAL算法的LOGLOSS值均大于SEM算法和EM-MCMC算法；同時(shí)，BDENBAL算法的遞減程度和其他兩種算法相比較小。該實(shí)驗(yàn)結(jié)果證明了和SEM算法、EM-MCMC算法相比，BDENBAL算法擁有更高的性能和預(yù)測(cè)穩(wěn)定性。

圖1 節(jié)點(diǎn)數(shù)為4時(shí)，LOGLOSS值隨不同PMV的變化

圖2 節(jié)點(diǎn)數(shù)為10時(shí)，LOGLOSS值隨不同PMV的變化

圖3 節(jié)點(diǎn)數(shù)為32時(shí)，LOGLOSS值隨不同PMV的變化

圖4～圖6顯示出BDENBAL算法在不同代數(shù)下的適應(yīng)度值變化，PMV值分別從0%～40%中選擇。實(shí)驗(yàn)中由EM算法評(píng)估失蹤的隨機(jī)樣本部分，估計(jì)值會(huì)比隨機(jī)值更加適合。因此，適應(yīng)度值會(huì)隨著PMV值的提高而增大。

圖4 節(jié)點(diǎn)數(shù)為4時(shí)，BIC評(píng)分的變化

2）結(jié)果形式發(fā)表文獻(xiàn)的性能比較

本文同時(shí)將BDENBAL算法和AMS-EM算法、EGA算法進(jìn)行了比較。圖7和圖8顯示出三種算法分別在200、400個(gè)訓(xùn)練實(shí)例樣本上的LOGLOSS值變化。實(shí)驗(yàn)結(jié)果表明，在兩種訓(xùn)練實(shí)例樣本上，AMS-EM算法的LOGLOSS值是最小的，而B(niǎo)DENBAL算法的LOGLOSS值最大。在缺失值相同的情況下，通過(guò)BDENBAL算法得到的貝葉斯網(wǎng)絡(luò)所反映的概率分布要更加準(zhǔn)確。因此，BDENBAL算法擁有更強(qiáng)大的評(píng)估能力并能收斂到全局最優(yōu)解。同時(shí)，三種算法的曲線弧度表明，在缺失值的百分比對(duì)BDENBAL算法、AMS-EM算法、EGA算法的影響程度中，BDENBAL算法受影響程度最小。

圖7 200個(gè)訓(xùn)練實(shí)例上的性能比較

圖8 400個(gè)訓(xùn)練實(shí)例上的性能比較

5 結(jié)語(yǔ)

基于評(píng)分的模型選擇算法是貝葉斯網(wǎng)絡(luò)學(xué)習(xí)最主要的策略之一。本文提出了基于新型二進(jìn)制自適應(yīng)差分演化算法（BDENBAL）的貝葉斯網(wǎng)絡(luò)學(xué)習(xí)，BDENBAL算法通過(guò)交叉和變異算子來(lái)實(shí)現(xiàn)貝葉斯網(wǎng)絡(luò)的學(xué)習(xí)過(guò)程中的信息交換。此外，BDENBAL算法根據(jù)貝葉斯信息標(biāo)準(zhǔn)（BIC）評(píng)分從網(wǎng)絡(luò)空間中選擇貝葉斯網(wǎng)絡(luò)候選者。為了檢驗(yàn)BDENBAL算法的性能，我們?cè)贛atlab環(huán)境下進(jìn)行模擬仿真，并將不同情況下BDENBAL算法、AMS-EM算法、EGA算法和SEM算法的性能進(jìn)行比較和分析，實(shí)驗(yàn)結(jié)果證明BDENBAL算法擁有更加優(yōu)良的性能。

［1］D.Mitra，P.Muller，S.Liang，et al.A Bayesian GraphicalModel for ChIP-Seq Data on Histone Modifications［J］.Journal of the American Statistical Association，2013，108（501）：69-80.

［2］ E.Gyftodimos， PA.Flach.Hierarchical Bayesian Networks：An Approrach to Classification and Learning for Structured Data［J］.Springer Berlin Heidelberg，2004，3052：291-300.

［3］D.Heckerma.A tutorial on learning with Bayesian Networks［J］.Studies in Computational Intelligence，2008，156：33-82.

［4］J.Rissanen.Estimation of structure by minimum description length［J］.Circuits System and Signal Processing，1982，156：3-4.

［5］H.Bozdogan.Model selection and Akaike's Information Criterion（AIC）：The general theory and its analytical extensions［J］.Psychometrika，1987，52（3）：345-370.

［6］N.Dojer.Learning Bayesian Networks Does Not Have to Be NP-Hard［J］.International Symposium on MathematicalFoundationsofComputerScience，2006，4162：305-314.

［7］P.Larranaga，M.Poza and Y.Yurramendi.Structure learning of Bayesian networks by genetic algorithms：a performance analysis of control parameters［J］.IEEE Transactions on Pattern Analysisamp;Machine Intelligence，1996，18（9）：912-926.

［8］N.Friedman，G.Dan and M.Goldszmidt.Bayesian Network Classifiers［J］.MachineLearning，1997，29（2-3）：131-163.

［9］L.Dayou，W.Fei and L.Yinan.Research on genetic algorithm based Bayesian Network structure learning［J］.Journal of Computer Research and Development，2001，38（8）：916-922.

［10］C.Riggelsen.Learning parameters of Bayesian Networks from incomplete data via importance sampling［J］.International Journal of Approximate Reasoning，2006，42（1）：69-83.

［11］J.Pena，J.Lozano and P.Larranaga.An improved Bayesian structural EM algorithm for learning Bayesian networks for clustering［J］.Pattern Recognition Letters，2000，21（8）：779-786.

［12］Yu Zhiwen，Li L，Wong H S，et al.Probabilistic cluster structure ensemble［J］.Information Sciences，2014，267（5）：16-34.

［13］Sihem A，Lehocinem B，Miniaih.A Batch Adsorption of Phenol From Industrial Waste Water Using Cereal By-Products As A New Adsrbent［J］，Energy Procedia，2012，18（4）：1135-1144.

Bayesian Network Learning Based on the New Binary System Adaptive Differential Evolution Algorithm

ZHAO Wenqiang ZHAO XiLIU Han
（No.37-1 Changhong Crossroads，Wuchang District，Wuhan 430064）

The Bayesian network is the most popular way to deal with uncertain knowledge and reasoning，and widely used in plenty of research fields.The strategy of Bayesian network learning is to choose the candidate of the optimal network by using the statistical score.The Bayesian network learning is proposed based on the new binary system adaptive differential evolution algorithm（BDENBAL）.BDENBAL uses a self-adaptive 0∕1 matrix as a proportional factor，And through the cross and mutation operator to realize the information exchange in the learning process of Bayesian network.Then，according to the Bayesian Information Criterion（BIC）scoring standard，the candidate is selected from the network space.The experimental results show that the proposed method has excellent performance.

Bayesian network，differential evolution，BIC

TP301.6

10.3969∕j.issn.1672-9730.2017.10.008

Class Number TP301.6

2017年4月6日，

2017年5月27日

趙文強(qiáng)，男，碩士，研究方向：信號(hào)與信息處理。趙熙，男，碩士，研究方向：可靠性工程。劉瀚，男，碩士，研究方向：動(dòng)力工程。