基于改進蟻獅優化的貝葉斯網絡結構學習算法

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

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

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

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

針對蟻獅算法易陷入局部最優的缺點,同時為了有效利用小數據集,本文對蟻獅算法進行改進并應用于BN結構學習過程,提出基于改進蟻獅優化的貝葉斯網絡結構學習算法(improved sigmoid function and fusion of the BBO mechanism and the ant lion algorithm,ISB-ALO)。

1 相關概念

1.1 互信息

互信息(mutual information,MI)可以衡量節點間的關聯程度。互信息值越大,關聯性越強,互信息值為零時,節點相互獨立。變量X和Y之間的互信息用I(X,Y)表示,且對任意兩個離散隨機變量X和Y,有I(X,Y)>0,表達式如式(1)所示:

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

(1)

(2)

(3)

(4)

1.2 BN結構表達以及sigmoid函數

貝葉斯網是一個有向無環圖,其中,將節點視為隨機變量,節點的連接邊表示變量之間的因果關系,高曉光等在文獻[21]中提出有向無環圖及其位置表示的方法如圖1所示。

圖1 有向無環圖及其位置表示

圖1對應的矩陣G(n,n)中,元素gij的取值與各節點連接關系用式(5)表示:

(5)

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

由式(5)可知,矩陣元素只能用0和1表示,但算法迭代時數值復雜多變,因此有學者用sigmoid函數對其進行轉換,式(6)為sigmoid函數表達式:

(6)

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

1.3 基本蟻獅算法

ALO模擬蟻獅對螞蟻的狩獵機制來實現尋優,精英蟻獅的位置相當于優化問題的解,蟻獅通過捕獵高適應度的螞蟻實現對近似最優解的更新和保存,該過程被模擬為以下5個部分:

1)螞蟻隨機游走機制

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

(7)

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

2)蟻獅構建陷阱

螞蟻的隨機游走受蟻獅陷阱的影響為:

(8)

(9)

3)蟻獅捕捉螞蟻

一只螞蟻只會被困在一只選定的蟻獅陷阱中,優化過程中利用輪盤賭策略根據適應度來選擇螞蟻。蟻獅建立與其適應度成比例的陷阱,對適應度高于自己的螞蟻進行捕獵。

4)蟻獅重駐陷阱

狩獵完成后,為增加捕獵的機會,蟻獅會將位置更新到適應度高于自己的螞蟻的位置:

(10)

5)精英機制

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

(11)

2 ISB-ALO算法構建

2.1 互信息約束算法的初始結構

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

2.2 小數據集下sigmoid函數的改進

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

(12)

(13)

2.3 融合BBO機制的蟻獅算法

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

2.3.1 遷移算子

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

表1 遷移算子流程

圖2 物種遷移模型

(14)

λ=1-μ

(15)

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

2.3.2 變異算子

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

表2 變異算子流程

(16)

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

2.3.3 清除算子

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

表3 清除算子流程

2.4 ISB-ALO算法

ISB-ALO算法流程見圖3。

圖3 算法流程圖

3 仿真結果及分析

3.1 算法驗證

為了驗證本文ISB-ALO算法的尋優性能,用4個具有單峰、多模態、高維和低維等特點且理論極值均為0的測試函數驗證,將該算法的尋優曲線與混沌粒子群算法、鳥群算法、混合蟻獅算法進行對比,各算法參數設置見表4,迭代次數均為2 000次,實驗結果見圖4。

(a)Ackley函數

表4 實驗參數設置

測試函數如下:

1)Ackley函數

(17)

2)booth函數

xi∈[-5.12,5.12]

(18)

3)Sphere函數

(19)

4)Zakharov函數

xi∈[-5,10]

(20)

根據圖4可知:混沌粒子群算法以及混合蟻獅算法在迭代未結束時就停止更新,而鳥群算法以及ISB-ALO算法可以不斷迭代直至最優值。由于引入了BBO機制,ISB-ALO算法搜索能力較鳥群算法更強,不同測試函數下該算法的尋優結果均優于對比算法,且不會陷入局部最優解。

為了避免實驗的隨機性,每組實驗分別運行50次,將各算法尋優結果的最好值、最差值、均值、標準差的平均值進行對比,見表5所示。

根據表5可知,相較于鳥群算法、混沌粒子群算法以及混合蟻獅算法,ISB-ALO算法最優值、最差值、均值、標準差的平均值均低于對比算法,并且最優值更接近測試函數的理論極值。綜上所述,ISB-ALO算法不論是尋優曲線還是最終結果均優于其它算法,證明了融合BBO機制的有效性。

表5 測試函數結果對比

3.2 BN結構學習結果驗證

為了證明ISB-ALO能夠有效提高BN結構學習的準確率,分別在采樣100、500、1 000、3 000組的數據下,以標準的animal網絡為背景,通過Matlab仿真,將該算法與混合蟻獅算法、鳥群算法、混沌粒子群算法的結構學習效果進行對比,為保證實驗結果的準確度,將每組數據獨立運行50次取平均值記錄,各算法對比結果見表6,表中加粗字體為最優值。

表6 BN結構實驗結果對比

根據表6的實驗數據,將各算法的BN結構指標——精確率、錯誤邊以及BIC評分進行詳細對比,結果見圖5～7。

由圖5可知,各數據量下,ISB-ALO算法的精確率均高于其他算法,且隨數據量的增加呈現平緩上升的趨勢,與混合蟻獅算法、鳥群算法、混沌粒子群算法相比,精確率的平均值分別提高了7.20%、16.97%、6.21%,這是因為對sigmoid函數的改進充分利用了有限數據,使結構學習的精確率得到提升,彌補了數據量不足的缺點。

圖5 各算法精確率對比

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

圖6 各算法錯誤邊對比

由圖7可知,ISB-ALO算法的BIC評分相較其他算法均有所提高,且在數據量較小時就體現出明顯的優勢,與混合蟻獅算法、鳥群算法、混沌粒子群算法相比,BIC評分平均值分別提高了615.973,756.865,233.302。由此可見,ISB-ALO算法的學習結果在不同數據量,尤其是小數據集下均能保持較高的準確性,BN結構更接近標準的animal網絡。

圖7 各算法BIC評分對比

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

(a)數據量100

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

4 結語

針對BN結構學習算法易陷入局部最優以及數據利用不充分的缺陷,本文提出了基于改進蟻獅優化的貝葉斯網絡結構學習算法。一方面由于對sigmoid函數的改進,充分利用了有限數據,提高了結構學習的精確率;另一方面結合BBO機制提出的3個算子,使結構學習算法易跳出局部最優,進一步提升了搜索效率和BN結構的準確度。仿真結果證明本文算法在小數據集下BN結構學習的可行性以及對蟻獅算法改進的有效性。

此外,BN結構學習在與智能算法結合時會增加總體的仿真時間,從而降低學習效率,因此,減少時間開銷,進一步提高BN結構學習的效率也是值得考慮的問題。