基于改進(jìn)混合遺傳細(xì)菌覓食算法的貝葉斯結(jié)構(gòu)學(xué)習(xí)算法

劉浩然, 常金鳳, 龐娜娜, 李晨冉, 盧澤丹

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

1 引 言

貝葉斯網(wǎng)絡(luò)(Bayesian network,BN)是基于圖論和概率論表示因果知識的概率圖模型,是一種有效的不確定性知識表達(dá)和推理工具[1]。貝葉斯網(wǎng)絡(luò)在數(shù)據(jù)挖掘、風(fēng)險(xiǎn)分析、機(jī)器學(xué)習(xí)、設(shè)備故障診斷和信息學(xué)等研究領(lǐng)域都有廣泛應(yīng)用[2,3]。

貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)是一個(gè)有向無環(huán)圖[4](directed acyclic graph,DAG)。貝葉斯網(wǎng)絡(luò)的學(xué)習(xí)主要由結(jié)構(gòu)學(xué)習(xí)和參數(shù)學(xué)習(xí)兩部分構(gòu)成,結(jié)構(gòu)學(xué)習(xí)是貝葉斯網(wǎng)絡(luò)的基礎(chǔ)。一般的DAG空間里的網(wǎng)絡(luò)結(jié)構(gòu)數(shù)量很大,為了降低搜索的復(fù)雜性找到最優(yōu)的網(wǎng)絡(luò)結(jié)構(gòu),通常使用啟發(fā)式算法[5]來解決此問題。

冀俊忠等提出一種基于蟻群優(yōu)化的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)算法[6];汪春峰等提出一種學(xué)習(xí)貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)的限制型遺傳算法[7];張平等將人工蜂群算法應(yīng)用到貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)中,提高了算法的學(xué)習(xí)速率和學(xué)習(xí)質(zhì)量[8];Gheisari提出將粒子群算法引入到貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)中,增強(qiáng)了算法的搜索能力[9];劉浩然等提出一種基于師生交流機(jī)制和變異機(jī)制的分類優(yōu)化貝葉斯網(wǎng)絡(luò)算法[10]。上述算法都在一定程度上解決了BN結(jié)構(gòu)學(xué)習(xí)時(shí)易陷入局部最優(yōu)和尋優(yōu)效率低的問題,但這些算法受其參數(shù)設(shè)置影響,貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)效果也受到限制。

在本文中,將細(xì)菌覓食優(yōu)化算法[11](bacterial foraging optimization algorithm,BFO)和遺傳算法[12](genetic algorithm,GA)結(jié)合起來,提出改進(jìn)的混合遺傳細(xì)菌覓食算法的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)算法(GBFO-B)。該算法首先通過GA算法獲取較優(yōu)貝葉斯網(wǎng)絡(luò)結(jié)構(gòu),以彌補(bǔ)BFO算法依賴初始解的不足；然后利用BFO算法的趨向行為、復(fù)制行為和遷移行為進(jìn)行求解,通過引入交叉策略,加強(qiáng)菌群的內(nèi)部信息交流,增強(qiáng)種群多樣性；引入變異策略,有利于跳出局部最優(yōu),降低BFO算法陷入局部最優(yōu)解的概率；通過改進(jìn)遷移行為,在一定程度上保護(hù)精英個(gè)體,加強(qiáng)算法之間的融合,提高全局收斂性。

2 GBFO-B算法構(gòu)建

2.1 復(fù)制行為及其改進(jìn)

復(fù)制行為中細(xì)菌的得分為單次趨向操作中經(jīng)過所有位置的適應(yīng)值的累積和,對應(yīng)的操作公式如式(1)所示。這種操作可能會造成適應(yīng)度值較高的細(xì)菌被淘汰掉,減慢算法的收斂速度。因此,本文將適應(yīng)度值直接作為細(xì)菌的得分克服此問題,保證較優(yōu)的細(xì)菌在下一代被保留。

(1)

式中：J表示細(xì)菌的適應(yīng)值；Nc表示細(xì)菌趨向性活動(dòng)的最大次數(shù)；i表示細(xì)菌；j表示趨向行為次數(shù)；k表示復(fù)制行為次數(shù)；l表示遷移行為次數(shù)。

X=X1+X2

(2)

(3)

(4)

(5)

2.2 遷移行為及其改進(jìn)

菌群中的每個(gè)個(gè)體都根據(jù)式(6)完成遷徙行為：

(6)

式中：q為(0,1 )區(qū)間內(nèi)采樣的一個(gè)均勻分布的隨機(jī)數(shù)；G是細(xì)菌表示的當(dāng)前網(wǎng)絡(luò)結(jié)構(gòu)；G′是初始化產(chǎn)生的隨機(jī)新網(wǎng)絡(luò)結(jié)構(gòu)；Ped是遷徙概率。由于每個(gè)細(xì)菌被賦予的遷徙概率是相同的,如果在全局最優(yōu)點(diǎn)附近的精英細(xì)菌個(gè)體被遷徙而初始化,將造成精英個(gè)體的丟失,算法的收斂速度變慢。

2.3 本文算法步驟

步驟1：種群初始化。計(jì)算互信息確定最大權(quán)生成樹,結(jié)合評分函數(shù)學(xué)習(xí)最大權(quán)生成樹得到初始網(wǎng)絡(luò)結(jié)構(gòu)。

步驟2：遺傳操作。根據(jù)BIC評分,按照輪盤賭的方式對種群進(jìn)行選擇。以列向量為單位對結(jié)構(gòu)進(jìn)行交叉操作,根據(jù)互信息對結(jié)構(gòu)進(jìn)行變異操作。

步驟3：判斷是否滿足GA算法的終止條件,直到產(chǎn)生最優(yōu)的一代個(gè)體,并將得到的個(gè)體作為BFO算法的初始種群。

步驟4：趨向行為。細(xì)菌進(jìn)行翻轉(zhuǎn),計(jì)算翻轉(zhuǎn)后的適應(yīng)度值,若適應(yīng)度值增大,則按照原來的方向繼續(xù)移動(dòng),直到適應(yīng)度值不再改善或達(dá)到最大移動(dòng)步數(shù)；若適應(yīng)度值減小,則結(jié)束此次趨化,進(jìn)入下一個(gè)細(xì)菌的趨化。待全部細(xì)菌一次趨化完成后,進(jìn)入第二次趨化,不斷重復(fù)上述操作,直到達(dá)到最大趨化次數(shù)。

步驟5：復(fù)制行為。

步驟6：判斷是否達(dá)到最大復(fù)制次數(shù),若未達(dá)到,轉(zhuǎn)向步驟4。

步驟7：遷移行為。

步驟8：判斷是否達(dá)到最大遷移次數(shù),若未達(dá)到,轉(zhuǎn)向步驟4,否則結(jié)束。

3 實(shí)驗(yàn)結(jié)果與分析

根據(jù)標(biāo)準(zhǔn)的Car網(wǎng)絡(luò)和Alarm網(wǎng)絡(luò)對GBFO算法進(jìn)行仿真驗(yàn)證。并與GA算法、人工蜂群算法(ABC)、蟻群算法(ACO)、BFO算法在準(zhǔn)確度、BIC評分值[15]和運(yùn)行時(shí)間方面進(jìn)行對比,測試本文算法的性能。

(1)基于Car網(wǎng)絡(luò)的仿真實(shí)驗(yàn),Car網(wǎng)絡(luò)的準(zhǔn)確度結(jié)果如圖1所示。

圖1 Car網(wǎng)絡(luò)準(zhǔn)確邊數(shù)和漢明距離Fig.1 Car network accurate edge number and Hamming distance

在數(shù)據(jù)量為500時(shí),GBFO算法學(xué)習(xí)到的BN結(jié)構(gòu)的準(zhǔn)確邊的數(shù)目有6條以上,這說明GBFO算法學(xué)習(xí)Car網(wǎng)絡(luò)可以得到較為準(zhǔn)確的結(jié)果。隨著數(shù)據(jù)樣本規(guī)模的增大,學(xué)習(xí)到的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)的正確邊數(shù)逐漸增加,漢明距離也呈現(xiàn)明顯下降的趨勢,效果明顯變好。GBFO和BFO學(xué)習(xí)到的BN結(jié)構(gòu)的正確邊數(shù)明顯大于GA,ABC和ACO,漢明距離明顯小于GA,ABC和ACO。這說明,BFO算法有更好的收斂性和尋優(yōu)能力,算法的性能更好一些。GBFO算法因?yàn)橥ㄟ^遺傳算法產(chǎn)生初始種群,保證了群體的優(yōu)良性,學(xué)習(xí)到的正確邊條數(shù)高于BFO,漢明距離小于BFO,其效果優(yōu)于BFO算法。

表1 Car網(wǎng)絡(luò)BIC得分統(tǒng)計(jì)結(jié)果Tab.1 Car network BIC score statistics

表2 Car網(wǎng)絡(luò)平均運(yùn)行時(shí)間統(tǒng)計(jì)結(jié)果Tab.2 Car network average running time statistics

由表1可知,對于Car網(wǎng)絡(luò),GBFO算法的平均最佳得分值最高,說明GBFO算法的性能更好,這是因?yàn)榧?xì)菌覓食算法的全局搜索能力較強(qiáng)。

由表2可知,GBFO算法學(xué)習(xí)貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)時(shí)的運(yùn)行時(shí)間僅低于遺傳算法,與其他種群算法相比,GBFO算法的運(yùn)行時(shí)間要更長,這是由于GBFO算法在細(xì)菌覓食行為部分要經(jīng)過大量的循環(huán)和迭代操作,犧牲了大量時(shí)間。然而,隨著樣本容量的增加,算法運(yùn)行時(shí)間增長相對緩慢,說明GBFO算法處理相對較大的數(shù)據(jù)集時(shí)有更明顯的優(yōu)勢。ABC算法由于人工蜜蜂之間有兩種信息交換機(jī)制,因此它可以快速地進(jìn)行求解優(yōu)化,在不同大小數(shù)據(jù)集下運(yùn)行時(shí)間均最短,獲得了最佳的時(shí)間性能。

表3 Alarm網(wǎng)絡(luò)BIC得分統(tǒng)計(jì)結(jié)果Tab.3 Alarm network BIC score statistics

表4 Alarm網(wǎng)絡(luò)平均運(yùn)行時(shí)間統(tǒng)計(jì)結(jié)果Tab.4 Alarm network average running time statistics

(2)基于Alarm網(wǎng)絡(luò)的仿真實(shí)驗(yàn),Alarm網(wǎng)絡(luò)的準(zhǔn)確度統(tǒng)計(jì)結(jié)果如圖2所示。

從圖2中可以看出,數(shù)據(jù)樣本量越大,算法學(xué)習(xí)到的正確邊數(shù)越多,錯(cuò)誤邊數(shù)越少,算法準(zhǔn)確率越高。在樣本數(shù)據(jù)為500時(shí),GBFO算法學(xué)習(xí)到的正確邊數(shù)比GA算法要多5條邊,比ABC和ACO 要多4條邊左右,GBFO算法比GA算法學(xué)習(xí)到的錯(cuò)誤邊數(shù)要少6條左右,比BFO 要少2條邊左右。這說明在數(shù)據(jù)量較少時(shí),GBFO算法也有較高的準(zhǔn)確度。在樣本數(shù)據(jù)為5 000時(shí),GBFO算法學(xué)習(xí)到的貝葉斯網(wǎng)絡(luò)的正確邊數(shù)為42.5條左右,接近標(biāo)準(zhǔn)的Alarm網(wǎng)絡(luò)的邊數(shù),尋優(yōu)能力較好。

由表3和表4可以看出,在Alarm中型網(wǎng)絡(luò)下, GBFO算法與其他算法相比, BIC得分更高,BN結(jié)構(gòu)學(xué)習(xí)精度較高,但運(yùn)行時(shí)間相對較慢。GBFO算法學(xué)習(xí)得到的網(wǎng)絡(luò)結(jié)構(gòu)與標(biāo)準(zhǔn)網(wǎng)絡(luò)差異很小,說明在學(xué)習(xí)諸如Alarm網(wǎng)絡(luò)這樣的中等規(guī)模的貝葉斯網(wǎng)絡(luò)時(shí),GBFO算法是一種有效準(zhǔn)確的算法。

4 結(jié) 論

貝葉斯網(wǎng)絡(luò)是目前不確定知識表達(dá)和推理領(lǐng)域最有效的工具之一,本文提出了一種改進(jìn)的混合遺傳細(xì)菌覓食算法的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)算法。

將遺傳算法和細(xì)菌覓食優(yōu)化算法的優(yōu)點(diǎn)進(jìn)行有效的結(jié)合,同時(shí)將這種算法應(yīng)用到貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)中。通過對種群的交叉變異操作,提高了全局搜索能力,避免陷入局部最優(yōu)解,增強(qiáng)了種群的多樣性。通過實(shí)驗(yàn)結(jié)果可以看出,在樣本容量相同的情況下,GBFO算法學(xué)習(xí)的網(wǎng)絡(luò)結(jié)構(gòu)更接近真實(shí)網(wǎng)絡(luò)。GBFO算法可以學(xué)習(xí)到分值較高的網(wǎng)絡(luò)結(jié)構(gòu),收斂效果好。但是,在實(shí)驗(yàn)中發(fā)現(xiàn),多次的迭代與評分操作,消耗了大量的時(shí)間,造成了GBFO算法的效率不是特別高。GBFO算法仍需對其效率這一不足之處進(jìn)行優(yōu)化,這將是下一步的重點(diǎn)。