陳海洋, 尚珊珊, 任智芳, 劉 靜, 張 靜

(西安工程大學(xué)電子信息學(xué)院,西安,710048)

貝葉斯網(wǎng)絡(luò)(bayesian network,BN)是基于概率推理的圖形化網(wǎng)絡(luò),通過數(shù)據(jù)統(tǒng)計(jì)、建模分析、計(jì)算推理來解決不確定性和不完整性問題[1-2],主要應(yīng)用于故障溯源、醫(yī)學(xué)診斷、軍事智能等領(lǐng)域[3-7]。BN的基本理論研究分為3個(gè)方面:結(jié)構(gòu)學(xué)習(xí)、參數(shù)學(xué)習(xí)和推理,其中,結(jié)構(gòu)學(xué)習(xí)作為BN的基礎(chǔ)與核心,目的是從數(shù)據(jù)中獲得最能體現(xiàn)變量間關(guān)系的有向無環(huán)圖。目前,結(jié)構(gòu)學(xué)習(xí)的方法主要分3種:①基于約束的方法[8-9],通過適配測(cè)試函數(shù)來判斷變量間的依賴關(guān)系,并作為約束進(jìn)行結(jié)構(gòu)學(xué)習(xí);②基于評(píng)分函數(shù)的方法[10-11],將學(xué)習(xí)到的模型與已知信息的擬合程度進(jìn)行量化,根據(jù)評(píng)分函數(shù)打分,分值最高的為最優(yōu)結(jié)構(gòu);③混合的方法[12-13],首先根據(jù)方法①初始化網(wǎng)絡(luò),然后選擇適合的搜索策略,通過方法②繼續(xù)更新尋找最優(yōu)解。由于特定需求或者特殊環(huán)境等因素的限制,如涉及軍事防御等重要場(chǎng)合的戰(zhàn)場(chǎng)態(tài)勢(shì)評(píng)估、可獲得數(shù)據(jù)較少的電力系統(tǒng)設(shè)備故障分析以及罕見疾病診斷等領(lǐng)域,數(shù)據(jù)的獲取相對(duì)困難,因此,需要在小數(shù)據(jù)集條件下對(duì)BN結(jié)構(gòu)學(xué)習(xí)展開研究。小數(shù)據(jù)集下的BN結(jié)構(gòu)學(xué)習(xí)主要是通過引入專家經(jīng)驗(yàn)或領(lǐng)域知識(shí)形成約束,進(jìn)而結(jié)合優(yōu)化算法將先驗(yàn)約束融入到結(jié)構(gòu)學(xué)習(xí)中[14-15],以此來提高BN結(jié)構(gòu)學(xué)習(xí)的準(zhǔn)確度。

Seyedali Mirjalili學(xué)者于2015年提出了蟻獅優(yōu)化算法(ant lion optimizer,ALO)[16],因其求解精度高、參數(shù)調(diào)節(jié)容易的特點(diǎn),被廣泛應(yīng)用于眾多工程領(lǐng)域[17-18]。文獻(xiàn)[19]采用具有自適應(yīng)的柯西變異算子使得蟻獅個(gè)體受局部極值點(diǎn)約束力下降,快速跳出局部最優(yōu),提高了搜索效率;文獻(xiàn)[20]針對(duì)蟻獅算法探索與開發(fā)能力不平衡的缺點(diǎn),提出了具有自適應(yīng)邊界與最優(yōu)引導(dǎo)的萊維飛行改進(jìn)算法,提高了收斂速度和全局搜索能力。上述改進(jìn)方法雖然使蟻獅優(yōu)化算法的性能得到優(yōu)化,但是無法結(jié)合各種形式的先驗(yàn)知識(shí),不適用于數(shù)據(jù)量較小的BN結(jié)構(gòu)學(xué)習(xí)。

針對(duì)蟻獅算法易陷入局部最優(yōu)的缺點(diǎn),同時(shí)為了有效利用小數(shù)據(jù)集,本文對(duì)蟻獅算法進(jìn)行改進(jìn)并應(yīng)用于BN結(jié)構(gòu)學(xué)習(xí)過程,提出基于改進(jìn)蟻獅優(yōu)化的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)算法(improved sigmoid function and fusion of the BBO mechanism and the ant lion algorithm,ISB-ALO)。

1 相關(guān)概念

1.1 互信息

互信息(mutual information,MI)可以衡量節(jié)點(diǎn)間的關(guān)聯(lián)程度?；バ畔⒅翟酱?關(guān)聯(lián)性越強(qiáng),互信息值為零時(shí),節(jié)點(diǎn)相互獨(dú)立。變量X和Y之間的互信息用I(X,Y)表示,且對(duì)任意兩個(gè)離散隨機(jī)變量X和Y,有I(X,Y)>0,表達(dá)式如式(1)所示:

I(X,Y)=H(X)+H(Y)-H(X,Y)

(1)

(2)

(3)

(4)

1.2 BN結(jié)構(gòu)表達(dá)以及sigmoid函數(shù)

貝葉斯網(wǎng)是一個(gè)有向無環(huán)圖,其中,將節(jié)點(diǎn)視為隨機(jī)變量,節(jié)點(diǎn)的連接邊表示變量之間的因果關(guān)系,高曉光等在文獻(xiàn)[21]中提出有向無環(huán)圖及其位置表示的方法如圖1所示。

圖1 有向無環(huán)圖及其位置表示

圖1對(duì)應(yīng)的矩陣G(n,n)中,元素gij的取值與各節(jié)點(diǎn)連接關(guān)系用式(5)表示:

(5)

式中:gij是G(n,n)中第i行第j列的元素。

由式(5)可知,矩陣元素只能用0和1表示,但算法迭代時(shí)數(shù)值復(fù)雜多變,因此有學(xué)者用sigmoid函數(shù)對(duì)其進(jìn)行轉(zhuǎn)換,式(6)為sigmoid函數(shù)表達(dá)式:

(6)

式中:Vij∈[-Vmax,+Vmax],通常Vmax取4。

1.3 基本蟻獅算法

ALO模擬蟻獅對(duì)螞蟻的狩獵機(jī)制來實(shí)現(xiàn)尋優(yōu),精英蟻獅的位置相當(dāng)于優(yōu)化問題的解,蟻獅通過捕獵高適應(yīng)度的螞蟻實(shí)現(xiàn)對(duì)近似最優(yōu)解的更新和保存,該過程被模擬為以下5個(gè)部分:

1)螞蟻隨機(jī)游走機(jī)制

根據(jù)式(7)的隨機(jī)游走機(jī)制定義螞蟻的位置:

(7)

式中:Csum是計(jì)算累積和的函數(shù);n是迭代最大次數(shù);t是隨機(jī)游走的步長(zhǎng);r(t)是一個(gè)[0,1]之間的隨機(jī)函數(shù)。

2)蟻獅構(gòu)建陷阱

螞蟻的隨機(jī)游走受蟻獅陷阱的影響為:

(8)

(9)

3)蟻獅捕捉螞蟻

一只螞蟻只會(huì)被困在一只選定的蟻獅陷阱中,優(yōu)化過程中利用輪盤賭策略根據(jù)適應(yīng)度來選擇螞蟻。蟻獅建立與其適應(yīng)度成比例的陷阱,對(duì)適應(yīng)度高于自己的螞蟻進(jìn)行捕獵。

4)蟻獅重駐陷阱

狩獵完成后,為增加捕獵的機(jī)會(huì),蟻獅會(huì)將位置更新到適應(yīng)度高于自己的螞蟻的位置:

(10)

5)精英機(jī)制

每次迭代中的最佳蟻獅被保存下來作為精英蟻獅。每個(gè)螞蟻的游走都會(huì)受到由輪盤賭選出的蟻獅與精英蟻獅的影響:

(11)

2 ISB-ALO算法構(gòu)建

2.1 互信息約束算法的初始結(jié)構(gòu)

為了縮小蟻獅算法搜索范圍,提高搜索效率,引入互信息約束。首先,根據(jù)式(1)～式(4)計(jì)算出各節(jié)點(diǎn)之間的互信息,根據(jù)互信息值的大小判斷出最優(yōu)BN結(jié)構(gòu)的候選邊。其次,將選定的邊作為約束,加入隨機(jī)生成的網(wǎng)絡(luò)中,初始化螞蟻和蟻獅的位置,生成基于蟻獅算法的結(jié)構(gòu)搜索空間。

2.2 小數(shù)據(jù)集下sigmoid函數(shù)的改進(jìn)

ALO中螞蟻與蟻獅的位置更新可看作BN結(jié)構(gòu)變化的過程。在對(duì)矩陣元素進(jìn)行二值轉(zhuǎn)換時(shí),由于受sigmoid函數(shù)速度邊界Vmax的限制,部分超出取值范圍的數(shù)據(jù)可能丟失,因此,為提高結(jié)構(gòu)學(xué)習(xí)的效率、充分利用小數(shù)據(jù)集,提出對(duì)數(shù)據(jù)劃分更詳細(xì)的轉(zhuǎn)換方法:先根據(jù)式(12)將矩陣G(n,n)中的元素gij投影在sigmoid函數(shù)的自變量范圍內(nèi),再利用sigmoid函數(shù)將G(n,n)轉(zhuǎn)換為元素在[0,1]之間的矩陣G′(n,n),進(jìn)而根據(jù)式(13)通過蟻獅精英機(jī)制尋優(yōu)。

(12)

(13)

2.3 融合BBO機(jī)制的蟻獅算法

生物地理算法(biogeography-based optimization,BBO)[22]中,動(dòng)物根據(jù)適應(yīng)度的高低選擇遷入與遷出。將BBO中遷入率與遷出率視為與個(gè)體適應(yīng)度相關(guān)的線性函數(shù),對(duì)算法中遷入、遷出、消亡等過程,分別建立遷移算子、變異算子、清除算子,并融合到蟻獅算法迭代過程中,來平衡局部最優(yōu)與全局最優(yōu)的關(guān)系。

2.3.1 遷移算子

在BBO的基礎(chǔ)上引入遷移算子,用根據(jù)遷出率選擇的螞蟻替換輪盤賭選出的螞蟻。螞蟻i的適應(yīng)度比重與遷入率、遷出率的函數(shù)關(guān)系分別見式(14)和式(15),模型見圖2,遷移算子流程見表1。

表1 遷移算子流程

圖2 物種遷移模型

(14)

λ=1-μ

(15)

式中:ft為螞蟻i的適應(yīng)度;Sfit為總適應(yīng)度;λ為遷入率;μ為遷出率;σ為極小值常數(shù)。

2.3.2 變異算子

在BBO中,螞蟻的適應(yīng)度在總適應(yīng)度中占比越高,陷入局部最優(yōu)的可能性越大,因此,用互信息約束的螞蟻取代根據(jù)變異概率選擇的螞蟻,來減小陷入局部最優(yōu)的概率,定義變異概率公式見式(16),變異算子流程表2。

表2 變異算子流程

(16)

式中:Ps為變異概率;λj(j=0,1,…,i-1)為遷入率;μj(j=1,2,…,i)為遷出率。

2.3.3 清除算子

清除算子根據(jù)適應(yīng)度的大小選擇被替代的螞蟻,若螞蟻j的適應(yīng)度值等于螞蟻i,則用加入互信息約束的螞蟻替代i,清除算子流程見表3。

表3 清除算子流程

2.4 ISB-ALO算法

ISB-ALO算法流程見圖3。

圖3 算法流程圖

3 仿真結(jié)果及分析

3.1 算法驗(yàn)證

為了驗(yàn)證本文ISB-ALO算法的尋優(yōu)性能,用4個(gè)具有單峰、多模態(tài)、高維和低維等特點(diǎn)且理論極值均為0的測(cè)試函數(shù)驗(yàn)證,將該算法的尋優(yōu)曲線與混沌粒子群算法、鳥群算法、混合蟻獅算法進(jìn)行對(duì)比,各算法參數(shù)設(shè)置見表4,迭代次數(shù)均為2 000次,實(shí)驗(yàn)結(jié)果見圖4。

(a)Ackley函數(shù)

表4 實(shí)驗(yàn)參數(shù)設(shè)置

測(cè)試函數(shù)如下:

1)Ackley函數(shù)

(17)

2)booth函數(shù)

xi∈[-5.12,5.12]

(18)

3)Sphere函數(shù)

(19)

4)Zakharov函數(shù)

xi∈[-5,10]

(20)

根據(jù)圖4可知:混沌粒子群算法以及混合蟻獅算法在迭代未結(jié)束時(shí)就停止更新,而鳥群算法以及ISB-ALO算法可以不斷迭代直至最優(yōu)值。由于引入了BBO機(jī)制,ISB-ALO算法搜索能力較鳥群算法更強(qiáng),不同測(cè)試函數(shù)下該算法的尋優(yōu)結(jié)果均優(yōu)于對(duì)比算法,且不會(huì)陷入局部最優(yōu)解。

為了避免實(shí)驗(yàn)的隨機(jī)性,每組實(shí)驗(yàn)分別運(yùn)行50次,將各算法尋優(yōu)結(jié)果的最好值、最差值、均值、標(biāo)準(zhǔn)差的平均值進(jìn)行對(duì)比,見表5所示。

根據(jù)表5可知,相較于鳥群算法、混沌粒子群算法以及混合蟻獅算法,ISB-ALO算法最優(yōu)值、最差值、均值、標(biāo)準(zhǔn)差的平均值均低于對(duì)比算法,并且最優(yōu)值更接近測(cè)試函數(shù)的理論極值。綜上所述,ISB-ALO算法不論是尋優(yōu)曲線還是最終結(jié)果均優(yōu)于其它算法,證明了融合BBO機(jī)制的有效性。

表5 測(cè)試函數(shù)結(jié)果對(duì)比

3.2 BN結(jié)構(gòu)學(xué)習(xí)結(jié)果驗(yàn)證

為了證明ISB-ALO能夠有效提高BN結(jié)構(gòu)學(xué)習(xí)的準(zhǔn)確率,分別在采樣100、500、1 000、3 000組的數(shù)據(jù)下,以標(biāo)準(zhǔn)的animal網(wǎng)絡(luò)為背景,通過Matlab仿真,將該算法與混合蟻獅算法、鳥群算法、混沌粒子群算法的結(jié)構(gòu)學(xué)習(xí)效果進(jìn)行對(duì)比,為保證實(shí)驗(yàn)結(jié)果的準(zhǔn)確度,將每組數(shù)據(jù)獨(dú)立運(yùn)行50次取平均值記錄,各算法對(duì)比結(jié)果見表6,表中加粗字體為最優(yōu)值。

表6 BN結(jié)構(gòu)實(shí)驗(yàn)結(jié)果對(duì)比

根據(jù)表6的實(shí)驗(yàn)數(shù)據(jù),將各算法的BN結(jié)構(gòu)指標(biāo)——精確率、錯(cuò)誤邊以及BIC評(píng)分進(jìn)行詳細(xì)對(duì)比,結(jié)果見圖5～7。

由圖5可知,各數(shù)據(jù)量下,ISB-ALO算法的精確率均高于其他算法,且隨數(shù)據(jù)量的增加呈現(xiàn)平緩上升的趨勢(shì),與混合蟻獅算法、鳥群算法、混沌粒子群算法相比,精確率的平均值分別提高了7.20%、16.97%、6.21%,這是因?yàn)閷?duì)sigmoid函數(shù)的改進(jìn)充分利用了有限數(shù)據(jù),使結(jié)構(gòu)學(xué)習(xí)的精確率得到提升,彌補(bǔ)了數(shù)據(jù)量不足的缺點(diǎn)。

圖5 各算法精確率對(duì)比

由圖6可知,ISB-ALO算法的錯(cuò)誤邊都少于其他算法,且錯(cuò)誤邊數(shù)量隨數(shù)據(jù)量線性遞減,與混合蟻獅算法、鳥群算法以及混沌粒子群算法相比,錯(cuò)誤邊平均值分別減少了30.49%、49.34%、26.13%,這是由于算法迭代中互信息的約束,降低了錯(cuò)誤迭代的概率,使得BN結(jié)構(gòu)的錯(cuò)誤邊有所減少。

圖6 各算法錯(cuò)誤邊對(duì)比

由圖7可知,ISB-ALO算法的BIC評(píng)分相較其他算法均有所提高,且在數(shù)據(jù)量較小時(shí)就體現(xiàn)出明顯的優(yōu)勢(shì),與混合蟻獅算法、鳥群算法、混沌粒子群算法相比,BIC評(píng)分平均值分別提高了615.973,756.865,233.302。由此可見,ISB-ALO算法的學(xué)習(xí)結(jié)果在不同數(shù)據(jù)量,尤其是小數(shù)據(jù)集下均能保持較高的準(zhǔn)確性,BN結(jié)構(gòu)更接近標(biāo)準(zhǔn)的animal網(wǎng)絡(luò)。

圖7 各算法BIC評(píng)分對(duì)比

為驗(yàn)證算法的收斂性能,將ISB-ALO算法與混合蟻獅算法、鳥群算法以及混沌粒子群算法在小數(shù)據(jù)集下分別迭代50次的收斂曲線進(jìn)行對(duì)比,見圖8。

(a)數(shù)據(jù)量100

由圖8可知,在數(shù)據(jù)量為100、500、1 000時(shí),鳥群算法、混合蟻獅算法以及混沌粒子群算法的平均收斂代數(shù)分別為28、46、25,而ISB-ALO算法僅需16次迭代就能收斂到最優(yōu)值,說明該算法結(jié)合BBO機(jī)制后能快速跳出局部最優(yōu)。在最初迭代時(shí)ISB-ALO算法的BIC評(píng)分就高于其他算法,這是由于互信息對(duì)初始結(jié)構(gòu)的約束,且在整個(gè)收斂過程中BIC評(píng)分都高于其他算法,進(jìn)一步證明了改進(jìn)方法在小數(shù)據(jù)集下具有較高的學(xué)習(xí)效率。

4 結(jié)語

針對(duì)BN結(jié)構(gòu)學(xué)習(xí)算法易陷入局部最優(yōu)以及數(shù)據(jù)利用不充分的缺陷,本文提出了基于改進(jìn)蟻獅優(yōu)化的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)算法。一方面由于對(duì)sigmoid函數(shù)的改進(jìn),充分利用了有限數(shù)據(jù),提高了結(jié)構(gòu)學(xué)習(xí)的精確率;另一方面結(jié)合BBO機(jī)制提出的3個(gè)算子,使結(jié)構(gòu)學(xué)習(xí)算法易跳出局部最優(yōu),進(jìn)一步提升了搜索效率和BN結(jié)構(gòu)的準(zhǔn)確度。仿真結(jié)果證明本文算法在小數(shù)據(jù)集下BN結(jié)構(gòu)學(xué)習(xí)的可行性以及對(duì)蟻獅算法改進(jìn)的有效性。

此外,BN結(jié)構(gòu)學(xué)習(xí)在與智能算法結(jié)合時(shí)會(huì)增加總體的仿真時(shí)間,從而降低學(xué)習(xí)效率,因此,減少時(shí)間開銷,進(jìn)一步提高BN結(jié)構(gòu)學(xué)習(xí)的效率也是值得考慮的問題。