基于動(dòng)態(tài)約束模型的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)優(yōu)化算法

李沛然，劉 琨，張 育，任 佳，崔亞妮

（海南大學(xué)信息與通信工程學(xué)院，海南海口，570228）

作為概率圖模型的典型代表，貝葉斯網(wǎng)絡(luò)（Bayesian Network，BN）是不確定知識(shí)表示和推理的重要理論工具.從樣本數(shù)據(jù)中學(xué)習(xí)獲得高質(zhì)量的BN模型決定了對(duì)復(fù)雜系統(tǒng)認(rèn)知的準(zhǔn)確性.傳統(tǒng)BN結(jié)構(gòu)學(xué)習(xí)方法主要有基于約束（Constraint?Based，CB）的學(xué)習(xí)方法［1］和基于搜索（Score?and?Search，SS）的學(xué)習(xí)方法［2］2類(lèi).基于CB的學(xué)習(xí)方法主要有PC算法［3］、最大最小父子節(jié)點(diǎn)（Max-Min Parent Children，MMPC）算法［4］、最大權(quán)重生成樹(shù)（Maximum Weight Spanning Tree MWST）算法［5］以及構(gòu)建馬爾科夫覆蓋［6-8］等.基于SS的學(xué)習(xí)方法主要包括爬山算法［9-10］、遺傳算法［11］和蟻群算法［12-13］等.上述2種學(xué)習(xí)方法雖然適合貝葉斯網(wǎng)絡(luò)的結(jié)構(gòu)學(xué)習(xí)過(guò)程，但是各自存在局限性.文獻(xiàn)［14］研究結(jié)果表明，將2種方法結(jié)合得到的混合學(xué)習(xí)方法能夠有效平衡搜索范圍和搜索效果，提高BN結(jié)構(gòu)學(xué)習(xí)的速度.在混合算法中，將約束方法與一些智能優(yōu)化方法相結(jié)合進(jìn)行結(jié)構(gòu)的尋優(yōu)是當(dāng)前的研究熱點(diǎn).劉彬［12］等通過(guò)MWST初始化網(wǎng)絡(luò)結(jié)構(gòu)，然后運(yùn)用蟻群結(jié)合K2進(jìn)行節(jié)點(diǎn)序列尋優(yōu)，提出一種MWST-ACO-K2算法用于BN結(jié)構(gòu)學(xué)習(xí)；劉浩然［15］等提出一種IWOA算法，該算法利用MMPC結(jié)合爬山算法生成初始種群，進(jìn)而運(yùn)用改進(jìn)的鯨魚(yú)優(yōu)化策略進(jìn)行種群搜索.

在研究過(guò)程中，粒子群（Particle Swarm Optimization，PSO）算法［16］因?yàn)楦路绞胶?jiǎn)單、采用并行運(yùn)算求解方式、算法收斂速度更快的特點(diǎn)，所以逐漸被應(yīng)用于BN結(jié)構(gòu)的優(yōu)化過(guò)程.但是BN采用二進(jìn)制編碼方式，傳統(tǒng)粒子群算法無(wú)法與BN結(jié)構(gòu)學(xué)習(xí)兼容，因而需要對(duì)粒子群的更新公式進(jìn)行適應(yīng)性?xún)?yōu)化.有學(xué)者提出將離散PSO算法或二進(jìn)制PSO算法應(yīng)用到BN結(jié)構(gòu)學(xué)習(xí)中，例如Wang［17］等利用二進(jìn)制粒子群優(yōu)化方法對(duì)網(wǎng)絡(luò)結(jié)構(gòu)矩陣進(jìn)行了扁平化，重新定義了粒子的速度和位置；李曉林［18］等提出了一種運(yùn)用極大似然樹(shù)初始化粒子群并基于免疫理論改進(jìn)的二元粒子群優(yōu)化方法，將粒子群優(yōu)化算法與BN結(jié)構(gòu)學(xué)習(xí)融合；李國(guó)梁［19］等提出了一種基于最大信息量的PSO算法，利用混沌映射的方法使鄰接矩陣表示BN網(wǎng)絡(luò)結(jié)構(gòu)，通過(guò)近似的方式將所有的計(jì)算結(jié)果映射到0～1值中；范瑞星［20］等通過(guò)將差分變異算法與離散粒子群相結(jié)合，并通過(guò)自適應(yīng)反向?qū)W習(xí)策略對(duì)初始種群進(jìn)行有目的地?cái)U(kuò)充，達(dá)到提升尋優(yōu)效率和收斂精度的效果；Liu［16］等將粒子的位置視為相關(guān)邊緣存在的概率，將速度視為對(duì)相關(guān)邊存在概率的增減，從而找到一種從連續(xù)搜索空間中更新粒子的方法，但是其本質(zhì)依賴(lài)于對(duì)粒子群結(jié)果的合理映射.雖然上述文獻(xiàn)基于改進(jìn)粒子群方法獲得了合理結(jié)構(gòu)，但CB階段對(duì)搜索空間約束固化，導(dǎo)致學(xué)習(xí)速度較慢，并采用映射的方式使得多種更新對(duì)應(yīng)一個(gè)解結(jié)構(gòu)，降低了結(jié)果對(duì)更新過(guò)程的敏感度，導(dǎo)致學(xué)習(xí)精度難以保證.還有研究者將PSO與其他優(yōu)化算法相結(jié)合產(chǎn)生新的更新方法.Gheisari［21］等提出了一種改進(jìn)PSO參數(shù)的結(jié)構(gòu)學(xué)習(xí)方法，將PSO與遺傳算法的更新方法相結(jié)合，使PSO應(yīng)用于BN結(jié)構(gòu)學(xué)習(xí)，但由于其初始粒子是隨機(jī)生成的，忽略了對(duì)初始粒子的合理約束，使得BN結(jié)構(gòu)學(xué)習(xí)精度不高；Li［22］等以MMPC建立無(wú)向圖構(gòu)建初始粒子群，同樣采用GA與PSO相結(jié)合的方式進(jìn)行結(jié)構(gòu)更新；李俊武［23］等以MWST生成初始網(wǎng)絡(luò)，通過(guò)布谷鳥(niǎo)與粒子群相結(jié)合的CS-PSO混合算法進(jìn)行BN結(jié)構(gòu)學(xué)習(xí)；Aydilek［24］運(yùn)用元啟發(fā)式算法，得到一種螢火蟲(chóng)-粒子群（HEPSO）優(yōu)化算法.綜上所述，許多學(xué)者都希望借助粒子群算法的全局尋優(yōu)能力，但是面對(duì)PSO算法容易陷入局部最優(yōu)的問(wèn)題，都沒(méi)能給出一個(gè)合理的解決方案.

基于粒子群的BN結(jié)構(gòu)學(xué)習(xí)雖然具有算法復(fù)雜度相對(duì)較低、收斂速度快、并行效率高的特點(diǎn)，但是也普遍存在難以控制學(xué)習(xí)精度以及容易早熟陷入局部最優(yōu)的缺陷.因此，建立前期的合理約束和早熟識(shí)別工作就顯得尤為重要.針對(duì)上述問(wèn)題與需求，筆者提出了一種基于動(dòng)態(tài)約束模型的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)優(yōu)化算法.該方法將馬爾科夫覆蓋（Markov blanket MB）與PSO相結(jié)合，首先設(shè)立動(dòng)態(tài)閾值通過(guò)互信息（Mutual Information，MI）約束搜索范圍，運(yùn)用條件獨(dú)立性檢驗(yàn)（Conditional Independence，CI）構(gòu)建馬爾科夫覆蓋，初始化粒子群縮小解結(jié)構(gòu)搜索空間規(guī)模，然后通過(guò)重新定義粒子群的更新機(jī)制搜索最優(yōu)結(jié)構(gòu)空間，解決了粒子群在貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)更新上的難題，同時(shí)提升搜索精度，最后采用計(jì)數(shù)器配合更替機(jī)制由新粒子替代部分質(zhì)量較低的原始粒子，對(duì)算法進(jìn)行早熟干擾，防止過(guò)早收斂導(dǎo)致結(jié)果陷入局部最優(yōu).

1 基本方法簡(jiǎn)述

提出了基于動(dòng)態(tài)約束的馬爾科夫覆蓋與粒子群相結(jié)合的MB-PSO方法，全文算法過(guò)程如圖1所示.

圖1 基于動(dòng)態(tài)約束模型的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)優(yōu)化算法流程圖

如圖1所示，首先設(shè)立動(dòng)態(tài)閾值，通過(guò)計(jì)算不同閾值下各節(jié)點(diǎn)的馬爾科夫覆蓋得到多個(gè)無(wú)向圖結(jié)構(gòu)，然后根據(jù)Jiang［6］等提出的CRAE算法進(jìn)行定向，可以構(gòu)造出復(fù)雜度不同的初始粒子，為粒子群搜索過(guò)程提供種類(lèi)豐富的初始網(wǎng)絡(luò)，最后以BIC評(píng)分作為適應(yīng)度值，通過(guò)改進(jìn)的粒子群算法進(jìn)行迭代尋優(yōu).另外，在迭代尋優(yōu)階段，以計(jì)數(shù)器設(shè)置對(duì)搜尋結(jié)果進(jìn)行監(jiān)測(cè)，當(dāng)過(guò)程陷入早熟時(shí)可以通過(guò)強(qiáng)制更換粒子，達(dá)到跳出局部最優(yōu)的效果.

2.1基于動(dòng)態(tài)馬爾科夫覆蓋簡(jiǎn)易發(fā)現(xiàn)方法的粒子群初始化過(guò)程基于CI測(cè)試與MI的動(dòng)態(tài)馬爾科夫覆蓋簡(jiǎn)易發(fā)現(xiàn)方法分為2步.第一步從空?qǐng)D出發(fā)，進(jìn)行連接邊擴(kuò)充：通過(guò)MI和MMI進(jìn)行互信息排序，加入動(dòng)態(tài)閾值α調(diào)節(jié)約束范圍的大小，由于粒子數(shù)量通常較多，因此將動(dòng)態(tài)閾值的運(yùn)動(dòng)步長(zhǎng)設(shè)為0.01，則動(dòng)態(tài)閾值為α=0.15i，i為粒子數(shù)，當(dāng)節(jié)點(diǎn)間的互信息滿(mǎn)足MI≥αMMI時(shí)，默認(rèn)2個(gè)節(jié)點(diǎn)存在連接關(guān)系，添加無(wú)向邊，直至完成對(duì)馬爾科夫覆蓋的候選節(jié)點(diǎn)進(jìn)行初步限制.第二步對(duì)當(dāng)前的約束環(huán)境進(jìn)行收縮：在排除多余信息之后進(jìn)行CI測(cè)試，在條件獨(dú)立性斷言成立時(shí)在馬爾科夫覆蓋中刪除該節(jié)點(diǎn)，可以達(dá)到減少冗余計(jì)算，提高運(yùn)算效率的效果.由于動(dòng)態(tài)閾值的設(shè)定，將在不同閾值下得到不同的無(wú)向圖結(jié)構(gòu)，形成初始的無(wú)向圖集群，之后再進(jìn)行進(jìn)一步的定向工作，使得無(wú)向圖變?yōu)橛邢驁D.

基于動(dòng)態(tài)約束模型的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)優(yōu)化算法中構(gòu)建馬爾科夫覆蓋約束部分的偽代碼如下：

返回?zé)o向圖集合G

將得到的無(wú)向圖通過(guò)CRAE確定連接邊的方向，假設(shè)Xi和Xj無(wú)向圖中存在連接邊的2個(gè)節(jié)點(diǎn)，則邊的定向計(jì)算公式為

當(dāng)CRAE(Xi→Xj)≥CRAE(Xj→Xi)時(shí)，連接邊的方向應(yīng)該為從節(jié)點(diǎn)i指向節(jié)點(diǎn)j.

由此，得到了初始粒子群，通過(guò)此方式不僅可以提高粒子的質(zhì)量，同時(shí)也可以豐富粒子的多樣性，得到復(fù)雜度各異的初始粒子，為后續(xù)的粒子群搜索過(guò)程提供幫助.

2.2適用于BN的小規(guī)模粒子群優(yōu)化算法粒子群算法由鳥(niǎo)類(lèi)覓食行為衍變而來(lái)，胡旺［25］等曾提出一種簡(jiǎn)化而得到的粒子群更新方式

其中，ωXt表示過(guò)去對(duì)現(xiàn)在的影響，其程度大小由ω調(diào)節(jié)，c1r1(Pbest-Xt)表示粒子的自我更新，c2r2(Gbest-Xt)表示粒子與群體之間的資源共享.在粒子群算法中最重要的是更新環(huán)節(jié)，即粒子速度和位置的更新.將每一個(gè)鄰接矩陣所表示的有向無(wú)環(huán)圖作為粒子位置，由于其二進(jìn)制的特性，在粒子群更新公式中無(wú)法通過(guò)常規(guī)的調(diào)節(jié)系數(shù)對(duì)其進(jìn)行操作，為保持粒子更新過(guò)程中有向無(wú)環(huán)圖的原始意義，將通過(guò)對(duì)其進(jìn)行加減邊或反轉(zhuǎn)邊的操作形式?jīng)Q定粒子的變更程度，Pk表示在優(yōu)化算法中每一個(gè)代表當(dāng)前粒子的DAG結(jié)構(gòu).將更新過(guò)程改進(jìn)后的粒子群算法應(yīng)用于BN結(jié)構(gòu)學(xué)習(xí)中，故而粒子群更新公式可以改寫(xiě)為

此處需要定義2個(gè)新的算子：

⊕定義為執(zhí)行粒子加減邊的更新操作；

??MI定義為通過(guò)互信息對(duì)需要執(zhí)行加減操作的邊進(jìn)行篩選.

對(duì)于每個(gè)操作的具體執(zhí)行方法，將擴(kuò)充為式（5）和（6）進(jìn)行具體闡述.

首先運(yùn)用BIC評(píng)分作為該更新算法的評(píng)分函數(shù)，計(jì)算當(dāng)前結(jié)構(gòu)的適應(yīng)度優(yōu)劣，該評(píng)分函數(shù)如下所示

BIC評(píng)分函數(shù)由2個(gè)部分組成，分別是度量候選結(jié)構(gòu)與樣本數(shù)據(jù)匹配程度的對(duì)數(shù)似然函數(shù)和與模型本身維數(shù)和數(shù)據(jù)集規(guī)模的相關(guān)罰項(xiàng)，這使得該評(píng)分可以有效平衡所得貝葉網(wǎng)絡(luò)結(jié)構(gòu)的匹配性與復(fù)雜性，有助于最終結(jié)構(gòu)的搜尋.

因此，當(dāng)BIC(P best)>BIC(P g)時(shí)，

當(dāng)BIC(P best)≤BIC(P g)

其中，C是對(duì)矩陣的復(fù)雜度計(jì)算，文中復(fù)雜度僅指網(wǎng)絡(luò)結(jié)構(gòu)中有向邊的數(shù)量；()MImax和()MImin分別是將當(dāng)代最優(yōu)結(jié)構(gòu)與當(dāng)前結(jié)構(gòu)相比，選擇差異邊中互信息最大（最?。┑倪?，該操作也即當(dāng)前結(jié)構(gòu)評(píng)分較低時(shí)，根據(jù)與最優(yōu)結(jié)構(gòu)比較的復(fù)雜度高低分別適當(dāng)增加（減少）當(dāng)代最優(yōu)結(jié)構(gòu)中與當(dāng)前結(jié)構(gòu)相比不同的邊中互信息最大（最?。┑倪?，使得當(dāng)前結(jié)構(gòu)可以學(xué)習(xí)部分最優(yōu)結(jié)構(gòu)的節(jié)點(diǎn)關(guān)系，使其復(fù)雜度向當(dāng)前較優(yōu)結(jié)構(gòu)靠攏.

特別的，當(dāng)BIC(G best)

其中，turn代表對(duì)原有結(jié)構(gòu)執(zhí)行邊的反轉(zhuǎn)操作，Pg±rand(0，1)為在當(dāng)前結(jié)構(gòu)中做隨機(jī)的加減邊操作.

當(dāng)前結(jié)構(gòu)評(píng)分達(dá)到最佳時(shí)，在保存該結(jié)構(gòu)數(shù)據(jù)的同時(shí)將通過(guò)隨機(jī)的形式在結(jié)構(gòu)中進(jìn)行邊的變換，增加粒子的多樣性.

通過(guò)如圖2所示的例子進(jìn)行說(shuō)明.

圖2中MI（i，j）為節(jié)點(diǎn)i到j(luò)之間的互信息值.在該示例中，設(shè)BIC(P k)

圖2 改進(jìn)的粒子群優(yōu)化算法更新示例

本文提出的更新方式不僅可以調(diào)節(jié)當(dāng)前粒子不斷向全局最優(yōu)和當(dāng)代最優(yōu)靠近，還可以在一定程度上幫助搜索過(guò)程跳出局部最優(yōu).

2.3跳出局部最優(yōu)的搜尋計(jì)數(shù)器和重啟機(jī)制由于目前的搜索算法大多面對(duì)易陷入局部最優(yōu)的特點(diǎn)，因此通過(guò)插入計(jì)數(shù)器，計(jì)算當(dāng)前最優(yōu)粒子的重復(fù)迭代次數(shù).當(dāng)最優(yōu)值連續(xù)迭代3次及以上時(shí)默認(rèn)陷入局部最優(yōu)，進(jìn)行粒子的強(qiáng)制更換，即刪除當(dāng)前評(píng)分值最低的粒子.在最優(yōu)粒子的基礎(chǔ)上進(jìn)行反轉(zhuǎn)邊或者加減邊的操作，并將該粒子替換當(dāng)前評(píng)分值最低的粒子進(jìn)入下一次迭代循環(huán)，其過(guò)程如圖3所示.

圖3中k是當(dāng)前迭代次數(shù)，t是計(jì)數(shù)器的記次數(shù)，代表最優(yōu)結(jié)果的重復(fù)次數(shù).當(dāng)最優(yōu)結(jié)果經(jīng)歷3次更新不發(fā)生變化時(shí)，默認(rèn)尋優(yōu)更替發(fā)生了停滯，即在當(dāng)前環(huán)境下難以找到更優(yōu)解，故而為了尋找更優(yōu)解，需要替換原有效果不佳的粒子，通過(guò)引入新粒子的方式增加更優(yōu)結(jié)構(gòu)出現(xiàn)的可能性.新粒子由當(dāng)前的最優(yōu)粒子通過(guò)隨機(jī)加減邊的方式產(chǎn)生.與此同時(shí)，還會(huì)通過(guò)檢測(cè)各粒子結(jié)構(gòu)中是否產(chǎn)生閉環(huán)，并加以排除.

圖3 基于計(jì)數(shù)器的粒子替換機(jī)制

2.4算法實(shí)現(xiàn)具體步驟

步驟1設(shè)置空?qǐng)D，添加動(dòng)態(tài)閾值α，當(dāng)MI≥αMMI時(shí)添加無(wú)向邊；

步驟2CI測(cè)試確定每個(gè)節(jié)點(diǎn)的馬爾科夫覆蓋，生成無(wú)向圖組；

步驟3CRAE函數(shù)對(duì)無(wú)向圖定向，生成初始粒子群；

步驟4計(jì)算當(dāng)代粒子的BIC評(píng)分值與復(fù)雜度，記錄當(dāng)代粒子評(píng)分值，更新全局最優(yōu)與個(gè)體最優(yōu)；

步驟5選擇相應(yīng)的更新機(jī)制，進(jìn)行邊的加減反轉(zhuǎn)操作；

步驟6計(jì)數(shù)器在迭代循環(huán)內(nèi)判斷收斂狀態(tài)，替換質(zhì)量較差的粒子；

步驟7重復(fù)步驟4、步驟5、步驟6，直至達(dá)到設(shè)定循環(huán)次數(shù)，跳出循環(huán)，得到最終解結(jié)構(gòu).

3 實(shí)驗(yàn)結(jié)果及數(shù)據(jù)分析

為了證實(shí)該算法的性能，選擇了2個(gè)公信力比較強(qiáng)的網(wǎng)絡(luò)生成4個(gè)數(shù)據(jù)集進(jìn)行測(cè)試，分別是：AISA網(wǎng)絡(luò)和ALARM網(wǎng)絡(luò).AISA網(wǎng)絡(luò)是一個(gè)反應(yīng)呼吸道疾病的醫(yī)學(xué)例子，說(shuō)明病人是否患有與胸部診所有關(guān)的肺結(jié)核、肺癌或支氣管炎，每個(gè)變量可以采取2個(gè)離散狀態(tài).分別利用1 000個(gè)案例的數(shù)據(jù)庫(kù)和5 000個(gè)案例的數(shù)據(jù)庫(kù)訓(xùn)練網(wǎng)絡(luò)結(jié)構(gòu).ALARM網(wǎng)絡(luò)是告警相關(guān)性和故障診斷模型，具有37個(gè)節(jié)點(diǎn)，同樣通過(guò)1 000組數(shù)據(jù)和5 000組數(shù)據(jù)進(jìn)行結(jié)構(gòu)訓(xùn)練.與此同時(shí)與BNC-PSO［21］，MMHC［9］和IK2vMB［6］3種方法在4個(gè)方面進(jìn)行對(duì)比，分別是：最終BIC評(píng)分（ABB），以s為單位的平均運(yùn)行時(shí)間（ART），得到最佳個(gè)體的平均迭代次數(shù)（AGB）和最佳個(gè)體與正確BN結(jié)構(gòu)的平均漢明距離（AHD），并且在結(jié)果收斂的條件下使用相同的種群大小和迭代次數(shù)，分別是60和500.

實(shí)驗(yàn)平臺(tái)：Intel Corei7?5300U，2.30 GHz，64位Windows10、8 GiBRAM內(nèi)存.程序均用Matlab軟件在R2014a版本下編譯，并且均以BIC評(píng)分作為最終判定結(jié)構(gòu)適應(yīng)度的標(biāo)準(zhǔn)評(píng)分，每個(gè)實(shí)驗(yàn)重復(fù)50次并計(jì)算其平均值.

表1是實(shí)驗(yàn)網(wǎng)絡(luò)的各項(xiàng)信息，包括實(shí)驗(yàn)網(wǎng)絡(luò)名稱(chēng)、數(shù)據(jù)集、實(shí)驗(yàn)數(shù)據(jù)組數(shù)量、網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)、網(wǎng)絡(luò)連接邊數(shù)和正確網(wǎng)絡(luò)結(jié)構(gòu)在不同數(shù)據(jù)集下的BIC評(píng)分.

表1 數(shù)據(jù)集標(biāo)準(zhǔn)信息

4種算法中，BNC-PSO算法首先隨機(jī)產(chǎn)生初始種群，運(yùn)用BIC評(píng)分計(jì)算粒子的適應(yīng)度值獲得初始最優(yōu)解，然后通過(guò)遺傳算子更新粒子，并計(jì)算BIC評(píng)分，并對(duì)最優(yōu)值進(jìn)行更新，直至滿(mǎn)足終止條件.MMHC則是在獲得候選父節(jié)點(diǎn)集合之后運(yùn)用貪婪爬山搜索算法，基于BDeu評(píng)分函數(shù)通過(guò)對(duì)結(jié)構(gòu)邊的加減的評(píng)分判定獲得最終的最優(yōu)解.IK2vMB算法是一種基于馬爾科夫毯的改進(jìn)K2算法，該方法分為2個(gè)部分：1）首先利用MI建立最大權(quán)重生成樹(shù)，構(gòu)建無(wú)向圖，運(yùn)用條件相對(duì)平均熵對(duì)該無(wú)向圖的連接邊進(jìn)行定向，然后將該有向圖分成節(jié)點(diǎn)塊進(jìn)行排序并修正，最后通過(guò)將所有節(jié)點(diǎn)塊拼接獲得初始結(jié)構(gòu)；2）首先尋找根節(jié)點(diǎn)的馬爾科夫毯，然后根據(jù)Koller-Sahami算法得到馬爾科夫毯中的節(jié)點(diǎn)排序，最后運(yùn)用修正得到節(jié)點(diǎn)序列代入K2算法學(xué)習(xí)到最終的BN結(jié)構(gòu).

在表2中可以看出，在通過(guò)馬爾科夫覆蓋對(duì)初始粒子群進(jìn)行有目的的初始化之后，可以在更少的迭代次數(shù)下得到當(dāng)前算法的最終結(jié)果，這一點(diǎn)反映了算法的運(yùn)算效率相對(duì)更高.當(dāng)網(wǎng)絡(luò)結(jié)構(gòu)規(guī)模較小的時(shí)候，該初始化方式并不會(huì)對(duì)運(yùn)算速度造成嚴(yán)重的負(fù)擔(dān)，但是卻能對(duì)結(jié)構(gòu)學(xué)習(xí)產(chǎn)生非常積極的作用.與BNCPSO相比，加入了計(jì)數(shù)器和粒子替換機(jī)制后的MB-PSO還可以在結(jié)果暫時(shí)收斂之后跳出局部最優(yōu)，得到結(jié)果更佳的BN結(jié)構(gòu).

表2 不同算法在各數(shù)據(jù)集中的比較

從圖4可以看出，算法在第五代左右經(jīng)歷了第一次收斂，但是在第十代再次獲得新的結(jié)構(gòu)，這也表明了計(jì)數(shù)器設(shè)置的必要性與其產(chǎn)生的跳出局部最優(yōu)的效果.BNC-PSO和IK2vMB均面臨學(xué)習(xí)結(jié)果的精度較低的問(wèn)題，這與其更新方式和學(xué)習(xí)機(jī)制的設(shè)定有密不可分的關(guān)系，MMHC雖然能夠保證相對(duì)較穩(wěn)定的學(xué)習(xí)質(zhì)量，但是依然會(huì)面臨隨著網(wǎng)絡(luò)結(jié)構(gòu)復(fù)雜度提高后貪婪算法迭代次數(shù)過(guò)多，不再適用的問(wèn)題.

圖4 MB-PSO算在AISA網(wǎng)絡(luò)1 000組數(shù)據(jù)集下某次BIC評(píng)分前50代數(shù)據(jù)截取圖

從表3和圖5可以看出，雖然本文算法運(yùn)行時(shí)間在網(wǎng)絡(luò)規(guī)模擴(kuò)大后失去了優(yōu)勢(shì)，但是依然能夠確保其收斂速度和學(xué)習(xí)精度保持較高的水平，體現(xiàn)在本文算法的初始粒子群BIC評(píng)分較高以及最終結(jié)果的漢明距離標(biāo)準(zhǔn)差較小這一結(jié)果上，表明本文算法具有較高的穩(wěn)定性.在保證穩(wěn)定性與最終漢明距離結(jié)果均比較理想的情況下，無(wú)論是小規(guī)模的8節(jié)點(diǎn)網(wǎng)絡(luò)，還是具備一定規(guī)模的37節(jié)點(diǎn)中型網(wǎng)絡(luò)，通過(guò)本文算法得到的最終網(wǎng)絡(luò)結(jié)構(gòu)的精度都是可以保證的.因此，本文算法在中小規(guī)模的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)中可以得到較好的效果.

表3 ASIA網(wǎng)絡(luò)和ALARM網(wǎng)絡(luò)在1 000和5 000組數(shù)據(jù)集下的初始粒子平均BIC評(píng)分

圖5 ASIA網(wǎng)絡(luò)和ALARM網(wǎng)絡(luò)在1 000和5 000組數(shù)據(jù)集下的平均漢明距離與標(biāo)準(zhǔn)差

綜上所述，在中小規(guī)模節(jié)點(diǎn)的情況下，本文算法在運(yùn)算時(shí)間和學(xué)習(xí)精度2個(gè)方面的優(yōu)勢(shì)比較明顯，計(jì)數(shù)器和粒子重置機(jī)制也有效保證了結(jié)果的收斂效率，降低了陷入局部最優(yōu)的可能，使得算法在保證結(jié)果質(zhì)量的同時(shí)能夠較快的實(shí)現(xiàn)收斂，這一結(jié)果為后續(xù)進(jìn)行大規(guī)模網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)提供了可能.

4 小 結(jié)

基于啟發(fā)式群智能算法PSO和動(dòng)態(tài)馬爾科夫覆蓋構(gòu)造了一種混合結(jié)構(gòu)學(xué)習(xí)算法，首先通過(guò)動(dòng)態(tài)約束閾值構(gòu)建基于馬爾科夫覆蓋的無(wú)向圖集合，通過(guò)CRAE定向和MI約束邊的生成條件添加新的有向邊增加初始化粒子的多樣性，構(gòu)成多個(gè)聯(lián)通的有向無(wú)環(huán)圖作為PSO的初始粒子，然后運(yùn)用PSO的思想重構(gòu)粒子更新過(guò)程，以適應(yīng)度和復(fù)雜度作為判斷粒子優(yōu)劣的條件，通過(guò)加邊、減邊、反轉(zhuǎn)邊的方式進(jìn)行粒子更新，最后在PSO尋優(yōu)過(guò)程中加入計(jì)數(shù)器和粒子更替機(jī)制，時(shí)刻監(jiān)視粒子最優(yōu)解的更新動(dòng)態(tài)，做到優(yōu)勝劣汰，及時(shí)以新粒子替代“劣質(zhì)”的粒子，避免過(guò)早收斂陷入局部最優(yōu).實(shí)驗(yàn)結(jié)果表明，粒子的初始化過(guò)程使得初始粒子品質(zhì)更佳，加快了粒子的尋優(yōu)速度；PSO優(yōu)化方法的重構(gòu)使得BN結(jié)構(gòu)學(xué)習(xí)合理的與粒子更新相結(jié)合，從而使學(xué)習(xí)得到的結(jié)果準(zhǔn)確度更高；計(jì)數(shù)器作用下的粒子更替可以有效規(guī)避算法過(guò)早收斂陷入局部最優(yōu).在與其他算法的實(shí)驗(yàn)比較中，本文算法可以做到學(xué)習(xí)精度更高，效率更佳，可以進(jìn)一步應(yīng)用于復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)和解決實(shí)際問(wèn)題中.