基于混合樽海鞘-差分進(jìn)化算法的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)算法

劉彬，范瑞星，劉浩然，張力悅，王海羽，張春蘭

（1. 燕山大學(xué)信息科學(xué)與工程學(xué)院，河北 秦皇島 066004；2. 河北省特種光纖與光纖傳感重點(diǎn)實(shí)驗(yàn)室，河北 秦皇島 066004）

1 引言

貝葉斯網(wǎng)絡(luò)（BN, Bayesian network）是結(jié)合圖論和概率論來(lái)表示因果知識(shí)的概率圖模型，是用于不確定領(lǐng)域中推理和預(yù)測(cè)的最佳方式之一[1]。貝葉斯網(wǎng)絡(luò)可以用圖論的語(yǔ)言直觀(guān)地揭示問(wèn)題的結(jié)構(gòu)，并利用該結(jié)構(gòu)降低概率推理的計(jì)算復(fù)雜度。由于貝葉斯網(wǎng)絡(luò)直觀(guān)易懂，在風(fēng)險(xiǎn)分析、機(jī)器學(xué)習(xí)、信息學(xué)等研究領(lǐng)域[2-3]都有應(yīng)用。

貝葉斯網(wǎng)絡(luò)的構(gòu)建包含結(jié)構(gòu)學(xué)習(xí)、參數(shù)學(xué)習(xí)和推理學(xué)習(xí)。結(jié)構(gòu)學(xué)習(xí)是基礎(chǔ)與核心，完備數(shù)據(jù)下的結(jié)構(gòu)學(xué)習(xí)方法主要有3種：基于依賴(lài)性測(cè)試的方法[4]、基于評(píng)分搜索的方法[5]和混合方法[6]，其中常見(jiàn)的結(jié)構(gòu)學(xué)習(xí)方法是基于評(píng)分搜索的方法，即在所有節(jié)點(diǎn)的結(jié)構(gòu)空間內(nèi)按照一定的搜索策略及評(píng)分準(zhǔn)則構(gòu)建貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)。

基于評(píng)分搜索的方法學(xué)習(xí)貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)是一種 NP問(wèn)題[7]，國(guó)內(nèi)外學(xué)者通常利用啟發(fā)式算法來(lái)解決此類(lèi)問(wèn)題。Tsamardinos等[8]提出了一種基于依賴(lài)性測(cè)試和爬山算法的最大最小爬山（MMHC,max-min hill-climbing）算法，該算法雖然改善了檢索策略，降低了搜索空間復(fù)雜度，但由于搜索空間的縮小易導(dǎo)致算法陷入局部最優(yōu)。劉浩然等[9]提出了基于最大支撐樹(shù)（MWST, most weight supported tree）和蟻群算法（ACO, ant colony optimization）的混合搜索節(jié)點(diǎn)序算法（MAK, MWST-ACO-K2），該算法在處理小型網(wǎng)絡(luò)時(shí)可取得較理想的結(jié)果，但是與其他基于節(jié)點(diǎn)序搜索算法類(lèi)似，需要對(duì)種群中所有個(gè)體運(yùn)行K2算法得到對(duì)應(yīng)的適應(yīng)度值，在大網(wǎng)絡(luò)中存在時(shí)間復(fù)雜度較高、結(jié)果較差等問(wèn)題。Wang等[1]提出了基于離散水循環(huán)算法的貝葉斯結(jié)構(gòu)學(xué)習(xí)算法（BEWCA-BN, binary encoding water cycle algorithm for BN structures learning），該算法根據(jù)邏輯算子提出了改進(jìn)的水循環(huán)算法更新個(gè)體，其中蒸發(fā)策略雖然提高了算法跳出局部最優(yōu)的能力，但在小網(wǎng)絡(luò)中通常需要花費(fèi)更多的時(shí)間尋找最優(yōu)解。Contaldi等[10]提出了基于精英遺傳算法的貝葉斯結(jié)構(gòu)學(xué)習(xí)算法（AESL-GA, adaptive elite-based structure learner using genetic algorithm），該算法采用自適應(yīng)的控制參數(shù)來(lái)避免參數(shù)設(shè)置對(duì)結(jié)果的影響，在小網(wǎng)絡(luò)中學(xué)習(xí)到了較優(yōu)的網(wǎng)絡(luò)結(jié)構(gòu)，但在大網(wǎng)絡(luò)中由于縮小搜索空間導(dǎo)致學(xué)習(xí)到的結(jié)果不太理想。

上述啟發(fā)式算法應(yīng)用于貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)時(shí)由于參數(shù)設(shè)置對(duì)搜索過(guò)程的影響，存在搜索效率較低、易陷入局部最優(yōu)等問(wèn)題，而Seyedall等[11]提出的樽海鞘算法（SSA, salp swarm algorithm）具有參數(shù)較少、操作簡(jiǎn)單、易于實(shí)現(xiàn)等優(yōu)點(diǎn)。SSA將種群劃分為引領(lǐng)者（leader）與跟隨者（follower），通過(guò)引領(lǐng)者領(lǐng)導(dǎo)跟隨者形成 slaps鏈進(jìn)行種群尋優(yōu)。在處理復(fù)雜問(wèn)題時(shí)由于引領(lǐng)者對(duì)跟隨者的引領(lǐng)作用，容易使整個(gè)種群過(guò)早地聚集于局部最優(yōu)解[12]。

本文將SSA應(yīng)用到貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)，同時(shí)為了避免SSA陷入局部最優(yōu)，將全局尋優(yōu)能力強(qiáng)的差分進(jìn)化（DE, differential evolution）算法[13]與SSA融合，構(gòu)建了一種混合樽海鞘-差分進(jìn)化（HBSS-DE,hybrid binary salp swarm-differential evolution）算法。該算法首先設(shè)置規(guī)模因子將種群劃分[14]為較好種群和較差種群。然后構(gòu)建樽海鞘搜索策略更新較好種群，提高算法的收斂速度；構(gòu)建差分搜索策略更新較差種群，避免陷入局部最優(yōu)，并在合并子種群時(shí)利用變異算子增大搜索范圍。最后通過(guò)種群的迭代搜索最佳結(jié)構(gòu)。

2 HBSS-DE算法的構(gòu)建

HBSS-DE算法利用最大支撐樹(shù)與爬山算法建立初始種群P0，然后將P0降序排列更新為種群P，并設(shè)置規(guī)模因子將種群P劃分為較好種群P1與較差種群P2。構(gòu)建樽海鞘搜索策略更新P1，建立差分搜索策略更新P2。合并為種群P時(shí)利用兩點(diǎn)變異算子增加種群的多樣性，并根據(jù)規(guī)模因子重新劃分P進(jìn)入下次迭代。迭代結(jié)束輸出種群P中評(píng)分最高的樽海鞘個(gè)體，即最佳的貝葉斯結(jié)構(gòu)。

2.1 初始種群的建立及劃分

根據(jù)數(shù)據(jù)樣本計(jì)算目標(biāo)網(wǎng)絡(luò)各節(jié)點(diǎn)間的互信息，利用2個(gè)節(jié)點(diǎn)間的互信息可以得出這2個(gè)節(jié)點(diǎn)是否相關(guān)[15]，不存在相關(guān)關(guān)系的節(jié)點(diǎn)必然不存在因果關(guān)系。以變量X、Y為例，互信息I(X,Y)為

其中，p(X,Y)為變量X和變量Y的聯(lián)合概率，p(X)為變量X的概率，p(Y)為變量Y的概率。

根據(jù)互信息計(jì)算各節(jié)點(diǎn)之間的權(quán)重，利用最大支撐樹(shù)原則生成一個(gè)候補(bǔ)結(jié)構(gòu)[16]，可以有效地縮小搜索的空間。該候補(bǔ)結(jié)構(gòu)中，除樹(shù)形結(jié)構(gòu)之外的節(jié)點(diǎn)利用爬山算法中的加邊、減邊、轉(zhuǎn)邊算子得到樽海鞘種群。其中每個(gè)樽海鞘代表的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)可用如圖1所示的鄰接矩陣表示。

圖1 樽海鞘個(gè)體

采用貝葉斯信息準(zhǔn)則（BIC, Bayesian information criterion）評(píng)分函數(shù)對(duì)樽海鞘個(gè)體評(píng)價(jià)。根據(jù)BIC評(píng)分函數(shù)的可分解性，當(dāng)BN中的局部結(jié)構(gòu)改變時(shí)，為了減少重復(fù)計(jì)算的次數(shù)，只需利用式(2)計(jì)算改變的局部結(jié)構(gòu)G1的評(píng)分fnew(G1,D)，然后代入式(3)即可得到樽海鞘個(gè)體的評(píng)分f(G,D)。

其中，Xi表示節(jié)點(diǎn)，π(Xi)表示Xi的父節(jié)點(diǎn)；mijk表示數(shù)據(jù)中滿(mǎn)足π(Xi)組合，即取值為j且Xi=k的樣本數(shù)；qi表示π(Xi)取值共有qi種組合；ri表示Xi共有ri種取值；D表示數(shù)據(jù)的樣本；G表示鄰接矩陣，G2表示G中未改變的局部結(jié)構(gòu)，fold(G2,D) 表示G2的評(píng)分。

選取樽海鞘種群中高于平均評(píng)分的個(gè)體作為初始種群P0。文獻(xiàn)[14]在種群劃分階段將初始種群隨機(jī)分成2個(gè)相等的子種群更新個(gè)體，由于個(gè)體分布隨著種群迭代動(dòng)態(tài)變化，導(dǎo)致迭代后期無(wú)法提高算法的局部搜索能力。為了保證種群全局搜索與局部搜索的平衡，本文根據(jù)種群的進(jìn)化情況建立自適應(yīng)劃分種群的規(guī)模因子q，具體的形式為

其中，NP為P0的種群規(guī)模，Tm為最大迭代次數(shù)，t為迭代次數(shù)，■*■為向下取整函數(shù)，K為自適應(yīng)調(diào)整規(guī)模因子q的參數(shù)，是根據(jù)個(gè)體評(píng)分與該種群平均評(píng)分的相對(duì)值建立的，具體的形式為

其中，fmax為P的最高評(píng)分值，f為P的平均評(píng)分值，fmin為P的最低評(píng)分值。

由于在迭代初期，種群的個(gè)體分布較分散，即K的值較小，因此q的值較小保證算法的全局搜索。隨著迭代的進(jìn)行，種群的個(gè)體分布趨于集中，即K的值也逐漸增大，因而q的值較大保證算法的局部搜索。

根據(jù)樽海鞘個(gè)體的評(píng)分將P0降序排列更新為種群P，利用規(guī)模因子q將種群劃分為較好種群P1與較差種群P2，具體形式為

其中，P1的種群規(guī)模NP1=q，P2的種群規(guī)模NP2= N P- N P1。

2.2 子種群更新

為了提高HBSS-DE算法的收斂速度，利用自適應(yīng)的變異算子與交叉算子改進(jìn) SSA的引領(lǐng)者與跟隨者，建立樽海鞘搜索策略更新較好種群P1。同時(shí)為了提高算法的收斂精度，改進(jìn)DE算法中的變異算子與交叉算子，建立差分搜索策略更新較差種群P2。

其中，rand為[0,1]之間的隨機(jī)數(shù)，“1”為加邊操作，“0”為減邊操作為變異位置的值。

其中，Crmax為交叉概率上限；Crmin為交叉概率下限；M為控制交叉方式的參數(shù)，它是根據(jù)個(gè)體的差異，即當(dāng)代種群中個(gè)體最佳評(píng)分與平均評(píng)分的相對(duì)值建立的，具體的形式如式(13)所示。

其中，fmax為P中最高評(píng)分值，為P的平均評(píng)分值，fmin為P中最小評(píng)分值。由式(13)可知，在算法的迭代初期，M的值較小，因而Cr的值較小，算法能以較大的概率選擇單點(diǎn)交叉法更新個(gè)體。隨著迭代的進(jìn)行，M的值逐漸增大，Cr的值也逐漸增大，樽海鞘個(gè)體以較大的概率選擇兩點(diǎn)交叉法更新個(gè)體。

將自適應(yīng)因子代入式(14)的交叉算子中更新P1中的跟隨者個(gè)體即

其中，F(xiàn)1是單點(diǎn)交叉，即隨機(jī)選擇一列的位置，然后交換 2個(gè)鄰接矩陣對(duì)應(yīng)列的位置；F2是兩點(diǎn)交叉，即交換2個(gè)鄰接矩陣對(duì)應(yīng)兩列的位置。以圖2所示的單點(diǎn)交叉為例，交換矩陣A和矩陣C的最后一列，得到矩陣E。

圖2 單點(diǎn)交叉

1) 差分搜索策略

改進(jìn)的變異算子先從P2中隨機(jī)選取3個(gè)樽海鞘個(gè)體（其中），然后將代入式(15)產(chǎn)生差分矩陣根據(jù)式(8)得到的變異位置集合R。利用式(16)將中的變異位置值轉(zhuǎn)化為變異概率并代入式(17)得到的變異位置值

其中，k2? [ 1,NP2]；r1、r2、r3為 [1 ,NP2]之間的隨機(jī)整數(shù)，并且r1≠r2≠r3；rand為 0～1的隨機(jī)數(shù)；c1(i,j)為變異概率；b=20為帶寬因子[17]；F=0.5為

改進(jìn)的交叉算子是通過(guò)式(12)得到P2的自適應(yīng)因子Cr，代入式(18)將變異個(gè)體與原個(gè)體交叉得到更新個(gè)體即

2) 選擇操作

2.3 合并子種群

為了能夠用更少的時(shí)間搜索到最佳網(wǎng)絡(luò)結(jié)構(gòu)，文獻(xiàn)[14]將更新之后的子種群P1、P2合并為種群P，使種群中的個(gè)體在搜索空間中彼此共享位置信息。但是種群個(gè)體的分布情況是動(dòng)態(tài)變化的，即在算法的迭代初期，個(gè)體分布比較分散，種群P1、P2中相同的個(gè)體較少；隨著迭代的進(jìn)行，個(gè)體趨于集中，種群P1、P2中相同的個(gè)體也逐漸增多，種群P的多樣性易喪失。

由于迭代后期種群的多樣性遭到破壞，算法易陷入局部最優(yōu)。為保證算法迭代后期有能力跳出局部最優(yōu)，本文將種群P1、P2中相同的個(gè)體通過(guò)兩點(diǎn)變異增加種群的多樣性。根據(jù)式(20)將P2中與P1評(píng)分相同的個(gè)體保存到種群P3，評(píng)分不同的個(gè)體保存到種群P4。

其中，k1? [ 1,NP1]，k2? [ 1,NP2]，f(xk

t1+1)、f(xk

t+21)分別是種群P1、P2中每個(gè)個(gè)體的評(píng)分。

將P3中的個(gè)體通過(guò)兩點(diǎn)變異增加種群多樣性，其中兩點(diǎn)變異是對(duì)鄰接矩陣中任意一列的2個(gè)元素進(jìn)行取反，如圖3所示對(duì)矩陣Q的右上角2個(gè)元素進(jìn)行取反，得到矩陣W。

圖3 兩點(diǎn)變異

將更新種群3P與1P、4P合并成新的種群0P，根據(jù)個(gè)體評(píng)分降序排列更新種群P，利用規(guī)模因子重新劃分種群進(jìn)入下一次迭代。迭代結(jié)束后保留種群P中的評(píng)分最佳的樽海鞘個(gè)體，即最優(yōu)的貝葉斯結(jié)構(gòu)。

2.4 HBSS-DE算法的整體流程

本文2.1節(jié)～2.3節(jié)介紹了算法的原理，接下來(lái)，對(duì)算法的具體步驟進(jìn)行簡(jiǎn)要描述。

步驟1 輸入數(shù)據(jù)樣本，通過(guò)互信息建立最大支撐樹(shù)，初始化參數(shù)Tm，t=1。

步驟2 利用爬山算法對(duì)最大支撐樹(shù)進(jìn)行初步搜索得到樽海鞘種群，并選擇高于平均值的樽海鞘個(gè)體建立初始種群0P。

步驟3 將0P通過(guò)評(píng)分降序排序更新為種群P，并通過(guò)自適應(yīng)因子劃分種群P為較好種群1P與較差種群2P。

步驟4 種群1P中采用樽海鞘搜索策略進(jìn)行更新，提高算法的收斂速度。

步驟5 種群P2中采用差分搜索策略進(jìn)行更新，提高算法的收斂精度。

步驟6 將2個(gè)子種群中相同個(gè)體利用兩點(diǎn)變異增加種群的多樣性，變異操作之后合并為種群P0。

步驟7 若滿(mǎn)足t＜Tm，則t=t+1，并轉(zhuǎn)至步驟3；否則，輸出最高評(píng)分值對(duì)應(yīng)的貝葉斯結(jié)構(gòu)。

2.5 HBSS-DE算法的收斂性分析

根據(jù) Solis等[18]提出的概率測(cè)度法分析隨機(jī)搜索算法HBSS-DE的收斂性。

引理1 隨機(jī)搜索算法 HBSS-DE滿(mǎn)足f(N(z,ξ) ) ≥f(z)，若ξ∈Sgbest，則f(N(z,ξ) ) ≥f(ξ)。其中，f為HBSS-DE算法解決最大化問(wèn)題的適應(yīng)度函數(shù)；N為產(chǎn)生較優(yōu)最新解的算子；z為搜索空間S的最優(yōu)解空間Sgbest中的樽海鞘個(gè)體，也是在Sgbest上產(chǎn)生可接受函數(shù)值的上確界；ξ為算法在S上隨機(jī)生成的樽海鞘個(gè)體。

證明根據(jù) 2.2節(jié)中選擇操作的描述，可將HBSS-DE算法中對(duì)當(dāng)前最優(yōu)解的選擇算子N定義為

引理2 HBSS-DE算法的最優(yōu)解空間Sgbest的概率測(cè)度大于0，即

證明假設(shè)HBSS-DE算法的貝葉斯結(jié)構(gòu)群為X={x1,x2,…,xn} ,x∈S，其中搜索空間S是可列集或有限集，顯然它的 Lebesgue[19]總是大于 0，即L[S] ＞0 ，HBSS-DE算法的最優(yōu)解空間Sgbest屬于S的一個(gè)Borel[19]子集，由HBSS-DE算法的最優(yōu)解空間Sgbest的定義可知，證畢。

引理3 HBSS-DE算法中，當(dāng)滿(mǎn)足L[Sgbest]＞0時(shí)，式(22)成立。

其中，μt(?)為第t次迭代結(jié)果的概率測(cè)度。

證明當(dāng)滿(mǎn)足L[Sgbest] ＞0時(shí)，有0＜μi,t(Sgbest)＜1，可知由μt產(chǎn)生的對(duì)Sgbest的概率測(cè)度為

將μt(Sgbest)代入式(22)，可得

至此，引理3得證。根據(jù)Solis等[18]提出的概率測(cè)度法可知，當(dāng)HBSS-DE算法滿(mǎn)足引理1～引理3時(shí)，式(25)成立。其中表示在第t次的結(jié)果xt落到Sgbest里的概率值為1，即算法經(jīng)過(guò)有限次迭代后，HBSS-DE算法中一定有存在于Sgbest的個(gè)體。尋找到最優(yōu)解空間Sgbest之后，根據(jù)HBSS-DE算法的迭代性原則，在以后的所有迭代中，種群中所有個(gè)體都向Sgbest靠攏，最終收斂于Sgbest。

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

為了驗(yàn)證HBSS-DE算法的性能，在操作系統(tǒng)為Windows7，處理器為Intel i3 3.40 GHz CPU，內(nèi)存為4 GB，軟件環(huán)境為Matlab 2010a，基于貝葉斯網(wǎng)絡(luò)工具箱 FullBNT-1.0.7中的 ASIA網(wǎng)絡(luò)、CAR網(wǎng)絡(luò)、ALARM網(wǎng)絡(luò)進(jìn)行仿真實(shí)驗(yàn)。其中，標(biāo)準(zhǔn)的ASIA網(wǎng)絡(luò)具有8個(gè)節(jié)點(diǎn)、8條邊，標(biāo)準(zhǔn)的CAR網(wǎng)絡(luò)具有12個(gè)節(jié)點(diǎn)、9條邊，標(biāo)準(zhǔn)的ALARM網(wǎng)絡(luò)具有37個(gè)節(jié)點(diǎn)、46條邊。3種標(biāo)準(zhǔn)網(wǎng)絡(luò)是通過(guò)訓(xùn)練實(shí)際數(shù)據(jù)建立的貝葉斯網(wǎng)絡(luò)，其中節(jié)點(diǎn)之間的邊表示因果關(guān)系。在3種網(wǎng)絡(luò)中隨機(jī)生成數(shù)據(jù)量為500、1 000、3 000、5 000個(gè)的數(shù)據(jù)樣本，因?yàn)閿?shù)據(jù)是隨機(jī)產(chǎn)生的，為降低數(shù)據(jù)的隨機(jī)性對(duì)實(shí)驗(yàn)結(jié)果準(zhǔn)確性的影響，每種樣本容量分別產(chǎn)生 10個(gè)，且每個(gè)數(shù)據(jù)單獨(dú)運(yùn)行10次，即每組數(shù)據(jù)運(yùn)行100次后取平均值作為實(shí)驗(yàn)結(jié)果。

隨著節(jié)點(diǎn)的增加，采用評(píng)分搜索的方法學(xué)習(xí)全局最優(yōu)解是一種 NP問(wèn)題[7]，而全局最優(yōu)解與較其稍差的局部最優(yōu)解的實(shí)際效益相差不大[18]，因而采用足夠好的解Sgbest來(lái)代替全局最優(yōu)解，將NP問(wèn)題轉(zhuǎn)化為N-問(wèn)題。HBSS-DE算法在3種網(wǎng)絡(luò)中的實(shí)驗(yàn)結(jié)果分別如表1～表3所示，其中fbest是100次實(shí)驗(yàn)中的最佳BIC評(píng)分，fav是100次實(shí)驗(yàn)的平均BIC評(píng)分，fsn是標(biāo)準(zhǔn)網(wǎng)絡(luò)的BIC評(píng)分。利用驗(yàn)證算法的局部最優(yōu)解Sgbest是否接近全局最優(yōu)解。

由表1～表3可知，在小網(wǎng)絡(luò)（如ASIA網(wǎng)絡(luò)、CAR網(wǎng)絡(luò)）中，當(dāng)數(shù)據(jù)量＞500個(gè)時(shí)HBSS-DE算法搜索到的最佳結(jié)構(gòu)評(píng)分fbest與標(biāo)準(zhǔn)網(wǎng)絡(luò)的評(píng)分fsn幾乎相同，即在小網(wǎng)絡(luò)中可以搜索標(biāo)準(zhǔn)網(wǎng)絡(luò)，這是因?yàn)樾【W(wǎng)絡(luò)中節(jié)點(diǎn)較少、搜索空間較小。而在大網(wǎng)絡(luò)中（如ALARM網(wǎng)絡(luò)），HBSS-DE算法的fbest比較接近fsn，這是因?yàn)殡S著節(jié)點(diǎn)的增多，搜索空間變大，算法收斂于接近全局最優(yōu)解的局部最優(yōu)解。在A(yíng)SIA網(wǎng)絡(luò)中σ的平均值為0.004 91，在CAR網(wǎng)絡(luò)中σ的平均值為0.010 4，在A(yíng)LARM網(wǎng)絡(luò)中σ的平均值為0.023 9，總體而言HBSS-DE算法的局部最優(yōu)解Sgbest接近全局最優(yōu)解。

表1 ASIA網(wǎng)絡(luò)HBSS-DE算法的BIC評(píng)分

表2 CAR網(wǎng)絡(luò)HBSS-DE算法的BIC評(píng)分

表3 ALARM網(wǎng)絡(luò)HBSS-DE算法的BIC評(píng)分

根據(jù)文獻(xiàn)[21]，列出分析算法性能的評(píng)價(jià)指標(biāo)。

Ext（execution time）：找到最佳網(wǎng)絡(luò)所需要的時(shí)間（單位為s）。

TP（true positive）：真正例，即預(yù)測(cè)結(jié)構(gòu)與標(biāo)準(zhǔn)結(jié)構(gòu)中相同且方向?yàn)檎倪叀?/p>

FP（false positive）：假正例，即預(yù)測(cè)結(jié)構(gòu)中邊的方向?yàn)檎瑯?biāo)準(zhǔn)結(jié)構(gòu)中為負(fù)。

FN（false negative）：假負(fù)例，即預(yù)測(cè)結(jié)構(gòu)中邊的方向?yàn)樨?fù)，標(biāo)準(zhǔn)結(jié)構(gòu)中為正。

TPR（true positive rate）：正確率，即預(yù)測(cè)結(jié)構(gòu)中TP與標(biāo)準(zhǔn)結(jié)構(gòu)中邊的比值，

FPR（false positive rate）：精確率，即預(yù)測(cè)結(jié)構(gòu)中TP與預(yù)測(cè)結(jié)構(gòu)全部邊的比值，

F（F-measure）：綜合評(píng)價(jià)指標(biāo)，即正確率和召回率的調(diào)和平均值，

W：100次實(shí)驗(yàn)中HBSS-DE算法的實(shí)驗(yàn)值ψ與其他算法的實(shí)驗(yàn)值ε相比提升的百分比，即

將 HBSS-DE算法與 AESL-GA、MAK、BEWCA-BN、MMHC算法進(jìn)行對(duì)比實(shí)驗(yàn)。其中本文算法自適應(yīng)因子的上下限分別為0.85、0.2。根據(jù)文獻(xiàn)[1]設(shè)BEWCA-BN尺度因子c的上下限分別為0.9、0.7，搜索強(qiáng)度參數(shù)d的上下限分別為0.2、0.01。根據(jù)文獻(xiàn)[7]設(shè) MMHC獨(dú)立性測(cè)試的置信度α為0.01，統(tǒng)計(jì)閾值設(shè)置為0.05。根據(jù)文獻(xiàn)[8]設(shè)MAK信息素強(qiáng)度系數(shù)為 1，信息素蒸發(fā)系數(shù)為 0.7，啟發(fā)式因子權(quán)重為2。根據(jù)文獻(xiàn)[9]設(shè)AESL-GA獨(dú)立性測(cè)試的置信度為0.01，精英個(gè)體閾值α為0.09。實(shí)驗(yàn)結(jié)果如下：表4～表6是不同算法在不同網(wǎng)絡(luò)的平均BIC評(píng)分，圖4～圖6是不同算法在不同網(wǎng)絡(luò)的結(jié)構(gòu)對(duì)比，表7～表9是不同算法在不同網(wǎng)絡(luò)的執(zhí)行時(shí)間對(duì)比。

由表4～表6可知，當(dāng)數(shù)據(jù)量為500時(shí)，在A(yíng)SIA網(wǎng)絡(luò)與CAR網(wǎng)絡(luò)中，本文算法和BEWCA-BN算法均能找到相對(duì)較優(yōu)的評(píng)分，但隨著數(shù)據(jù)量的增大，本文算法相比于其他算法能學(xué)習(xí)到更優(yōu)的評(píng)分。根據(jù)W計(jì)算，當(dāng)數(shù)據(jù)量為500、1 000、3 000、5 000時(shí)，本文算法與其他算法相比，BIC評(píng)分的平均提高值分別為然后利用得到整體 BIC提升百分比。本文算法在 ASIA網(wǎng)絡(luò)中的 BIC評(píng)分比MAK、MMHC、AESL-G、BEWCA-BN 算法平均提升了 3.71%、4.34%、3.85%、1.86%，在 CAR網(wǎng)絡(luò)中平均提升了4.41%、3.64%、2.49%、1.47%，在 ALARM 網(wǎng)絡(luò)中平均提升了 6.96%、9.08%、10.02%、3.84%?？傮w而言，HBSS-DE算法能夠找到評(píng)分更優(yōu)的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)，在大型網(wǎng)絡(luò)中比其他算法的提升效果更佳。這是由于本文算法可以在較好個(gè)體周?chē)植克阉?，在較差個(gè)體周?chē)炙阉鳎⑼ㄟ^(guò)規(guī)模因子保證了算法的局部搜索與全局搜索的平衡，即在迭代前期全局搜索，迭代后期局部搜索。同時(shí)對(duì)于2個(gè)子種群中相同個(gè)體利用兩點(diǎn)變異策略增加了種群的多樣性，避免陷入局部最優(yōu)。

表4 不同算法在A(yíng)SIA網(wǎng)絡(luò)中不同數(shù)據(jù)量下的平均BIC評(píng)分

表5 不同算法在CAR網(wǎng)絡(luò)中不同數(shù)據(jù)量下的平均BIC評(píng)分

表6 不同算法在A(yíng)LARM網(wǎng)絡(luò)中不同數(shù)據(jù)量下的平均BIC評(píng)分

圖4 ASIA網(wǎng)絡(luò)不同數(shù)據(jù)下的結(jié)構(gòu)對(duì)比

圖5 CAR網(wǎng)絡(luò)不同數(shù)據(jù)下的結(jié)構(gòu)對(duì)比

圖6 ALARM網(wǎng)絡(luò)不同數(shù)據(jù)下的結(jié)構(gòu)對(duì)比

表7 不同算法在A(yíng)SIA網(wǎng)絡(luò)中不同數(shù)據(jù)量下的執(zhí)行時(shí)間

表8 不同算法在CAR網(wǎng)絡(luò)中不同數(shù)據(jù)量下的執(zhí)行時(shí)間

表9 不同算法在A(yíng)LARM網(wǎng)絡(luò)中不同數(shù)據(jù)量下的執(zhí)行時(shí)間

由圖4～圖6可知，本文算法的TP值在A(yíng)SIA網(wǎng)絡(luò)中比MAK、MMHC、AESL-GA、BEWCA-BN算法平均多了1.49、1.34、1.02、0.79，在CAR網(wǎng)絡(luò)中比其他算法平均多了2.21、1.71、1.23、0.56，在A(yíng)LARM網(wǎng)絡(luò)中比其他算法平均多了7.41、4.11、4.81、3.65。本文算法在A(yíng)SIA網(wǎng)絡(luò)、CAR網(wǎng)絡(luò)、ALARM 網(wǎng)絡(luò)中 FP的值均小于其他算法，且在 3個(gè)網(wǎng)絡(luò)中的TPR值均大于其他算法。根據(jù)W計(jì)算，當(dāng)數(shù)據(jù)量為500、1 000、3 000、5 000時(shí)，本文算法與其他算法相比，F(xiàn)值平均提高的百分比分別為然后利用計(jì)算整體提高百分比。本文算法的F值在A(yíng)SIA網(wǎng)絡(luò)中比MAK、MMHC、AESL-GA、BEWCA-BN算法平均提高了22.54%、17.89%、15.17%、8.57%，在CAR網(wǎng)絡(luò)中比其他算法平均提高了25.74%、19.29%、13.32%、9.64%，在 ALARM 網(wǎng)絡(luò)中比其他算法平均提高了24.71%、15.19%、10.91%、6.36%?？傮w而言，HBSS-DE算法能夠找到更準(zhǔn)確的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)，這是由于在較差種群中采用差分搜索策略，即在較差個(gè)體周?chē)M(jìn)行全局搜索增加了種群的多樣性；通過(guò)自適應(yīng)因子保證種群在迭代前期的全局搜索能力強(qiáng)；同時(shí)合并子種群時(shí)的兩點(diǎn)變異增大種群的搜索范圍，增加了種群跳出局部最優(yōu)的能力。

由表7～表9可知，當(dāng)ASIA網(wǎng)絡(luò)的數(shù)據(jù)量為500和1 000時(shí)，AESL-GA運(yùn)行時(shí)間最短，HBSS-DE算法運(yùn)行時(shí)間比AESL-GA略長(zhǎng)一些，這是由于在小數(shù)據(jù)量下HBSS-DE算法為了提高算法的全局搜索，通過(guò)規(guī)模因子將種群劃分為2個(gè)子種群更新個(gè)體，并將子種群中相同的個(gè)體利用兩點(diǎn)交叉變異擴(kuò)大搜索的范圍。雖然避免了陷入局部最優(yōu)，但同時(shí)增加了運(yùn)行時(shí)間。根據(jù)W計(jì)算，當(dāng)數(shù)據(jù)量為500、1 000、3 000、5 000時(shí)，HBSS-DE算法與其他算法相比，執(zhí)行時(shí)間平均縮短的百分比分別為其整體縮短的百分比根據(jù)得到。與MAK算法、MMHC算法、BEWCA-BN算法相比，HBSS-DE算法在 ASIA網(wǎng)絡(luò)中的運(yùn)行時(shí)間平均縮短了15.25%、21.77%、5.32%。在CAR網(wǎng)絡(luò)中，HBSS-DE算法比 MAK、MMHC、AESL-GA、BEWCA-BN算法平均縮短了18.57%、13.26%、15.18%、5.12%。當(dāng)ALARM網(wǎng)絡(luò)數(shù)據(jù)量為5 000時(shí)，HBSS-DE算法比BEWCA-BN算法耗時(shí)略長(zhǎng)，這是由于節(jié)點(diǎn)較多的網(wǎng)絡(luò)搜索的范圍較大，在迭代的過(guò)程中差分搜索策略雖然增大了搜索的空間，提高了算法的全局搜索能力；合并子種群時(shí)的兩點(diǎn)交叉變異雖然增加了種群的多樣性，避免了算法陷入局部最優(yōu)，但是差分搜索策略與兩點(diǎn)交叉變異也增加了算法的搜索時(shí)間。HBSS-DE算法在A(yíng)LARM網(wǎng)絡(luò)中比MAK、MMHC、AESL-GA、BEWCA-BN算法平均縮短了28.23%、92.63%、19.04%、1.42%?？傮w而言，HBSS-DE算法在大型網(wǎng)絡(luò)中比其他算法的搜索效率的優(yōu)勢(shì)更明顯。這是因?yàn)殚缀Ｇ仕阉鞑呗缘木植克阉髂芰?qiáng)，能夠快速地收斂到最優(yōu)解。而自適應(yīng)因子保證了迭代后期的局部搜索，提高了搜索效率；同時(shí)在評(píng)價(jià)個(gè)體時(shí)僅計(jì)算個(gè)體改變的部分結(jié)構(gòu)，減少在評(píng)價(jià)個(gè)體時(shí)消耗的無(wú)用時(shí)間。

4 結(jié)束語(yǔ)

本文提出了基于混合樽海鞘-差分算法的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)算法HBSS-DE。該算法通過(guò)設(shè)置規(guī)模因子，將種群劃分為2個(gè)子種群，利用構(gòu)建的樽海鞘搜索策略與差分搜索策略分別更新不同的子種群，在合并子種群時(shí)利用兩點(diǎn)交叉變異增加種群的多樣性。仿真實(shí)驗(yàn)證明，HBSS-DE算法能夠找到最佳的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)，其中規(guī)模因子平衡了局部搜索與全局搜索，樽海鞘搜索策略提高了算法的尋優(yōu)效率，差分搜索策略提高了算法的收斂精度。與其他算法相比，HBSS-DE算法的收斂精度與尋優(yōu)效率均有提升。