貝葉斯網(wǎng)絡(luò)推理學(xué)習(xí)的混合粒子群-差分算法

范瑞星，劉浩然，張力悅，蘇昭玉，劉 彬

1(燕山大學(xué)信息科學(xué)與工程學(xué)院，河北秦皇島066004)

2(燕山大學(xué)電氣工程學(xué)院，河北秦皇島066004)

1 引 言

貝葉斯網(wǎng)絡(luò)(Bayesian Networks，BNs)由一個(gè)有向無環(huán)圖(Directed Acyclic Graph，DAG)和條件概率表(Condition Probability Table，CPT)組成，被廣泛應(yīng)用于不確定性推理問題［1］.BNs 可根據(jù)網(wǎng)絡(luò)節(jié)點(diǎn)的聯(lián)合概率分布進(jìn)行概率推理，在人工智能、決策支持系統(tǒng)、故障診斷、信息學(xué)研究等研究領(lǐng)域都有應(yīng)用［2，3］.

貝葉斯網(wǎng)絡(luò)的構(gòu)建包含結(jié)構(gòu)學(xué)習(xí)、參數(shù)學(xué)習(xí)以及推理學(xué)習(xí)，其中推理學(xué)習(xí)是貝葉斯網(wǎng)絡(luò)目的與應(yīng)用.推理學(xué)習(xí)根據(jù)問題的不同可分為:后驗(yàn)概率問題、最大后驗(yàn)假設(shè)(Maximum a Posteriori Hypothesis，MAP)問題和最大可能解釋(Most Probable Explanation，MPE)問題.其中MPE 問題是從全部變量與證據(jù)變量相一致的狀態(tài)組合中找到概率最大的解釋.由于實(shí)際生活中存在較多的MPE 問題，目前許多學(xué)者對MPE 問題進(jìn)行了大量的研究［4］.

解決MPE 問題的算法可分為精確算法與近似算法這兩大類，根據(jù)變量消元法、團(tuán)樹傳播法等精確算法［5］可以搜索到MPE 問題的精確解，然而精確算法對于實(shí)際網(wǎng)絡(luò)已被證明是不可行的或不切實(shí)際的［6］，由于精確算法的局限性，以及MPE 問題在實(shí)際應(yīng)用中的重要性，許多國內(nèi)外的專家學(xué)者將啟發(fā)式算法應(yīng)用于貝葉斯網(wǎng)絡(luò)的MPE 問題.文獻(xiàn)［7］利用貝葉斯網(wǎng)絡(luò)的多重分形特征和聚類特性構(gòu)建了一種小生境遺傳(Nitching Genetic Algorithm，NGA)算法.該算法利用貝葉斯網(wǎng)絡(luò)聯(lián)合概率分布中的高度自相似性，選擇一種概率擁擠方法構(gòu)建改進(jìn)的遺傳算法.雖然提高了算法迭代初期的搜索效率，但是由于這種自相似性使得算法迭代后期易陷入局部最優(yōu).文獻(xiàn)［8］將MPE 問題作為約束優(yōu)化問題重新定義了適應(yīng)度函數(shù)，對于每種解釋都要考慮導(dǎo)致適應(yīng)度為零的節(jié)點(diǎn)數(shù)量，當(dāng)BNs 的CPT 中包含大量的零時(shí)通過競賽選擇處理BNs 中的約束.在小網(wǎng)絡(luò)中雖然提高了算法的收斂精度，但在大網(wǎng)絡(luò)中收斂速度較慢.文獻(xiàn)［9］根據(jù)馬爾可夫鏈模型處理CPT 中節(jié)點(diǎn)狀態(tài)為零情況，提出基于隨機(jī)貪婪搜索(Stochastic Greedy Search，SGS)算法的 SimpleSGS 算法，根據(jù)貪婪搜索策略處理BNs 中條件概率表中的零項(xiàng)，貪婪搜索策略雖然提高了SimpleSGS 算法的收斂精度，但其搜索效率有所下降.文獻(xiàn)［10］構(gòu)建DMVPSO 算法來解決貝葉斯網(wǎng)絡(luò)的MPE 問題，其中粒子對應(yīng)BNs 中每個(gè)節(jié)點(diǎn)可能的狀態(tài)值，并利用鏈?zhǔn)椒▌t確定其粒子的評價(jià)函數(shù)，通過離散PSO 迭代搜索MPE.雖然在小網(wǎng)絡(luò)中收斂精度較高，但是隨著節(jié)點(diǎn)數(shù)量的增加，搜索的結(jié)果逐漸變差.文獻(xiàn)［11］將離散的PSO 與OSI 框架結(jié)合構(gòu)建了DOSI 算法，根據(jù)馬爾科夫毯的性質(zhì)將BNs 劃分為多個(gè)子網(wǎng)絡(luò).利用離散PSO 更新每個(gè)子網(wǎng)絡(luò)，并采用OSI 框架中的競爭機(jī)制處理子網(wǎng)絡(luò)中的重疊節(jié)點(diǎn).但是隨著節(jié)點(diǎn)的增多搜索范圍變廣，DOSI 算法迭代后期易陷入局部最優(yōu).

PSO 算法由于全局極值gbest 以及運(yùn)動慣性ω 的影響，迭代后期易喪失種群多樣性而陷入局部最優(yōu).而差分進(jìn)化(Differential Evolution，DE)算法具有較強(qiáng)的全局搜索能力、能夠并行化等優(yōu)點(diǎn)［12］，將DE 引入PSO 建立混合離散粒子群-差分(Hybrid Discrete Particle Swarm Optimization-Differential Evolution，HDPSO-DE)算法.該算法利用自適應(yīng)的反向?qū)W習(xí)策略增加初始種群的多樣性，在PSO 更新過程中為避免gbest、ω 的不合理取值對算法性能的影響，將DE 的變異算子引入PSO 構(gòu)建了自適應(yīng)概率分層搜索策略(Adaptive Probability Hierarchical Strategy，APHS)更新粒子.同時(shí)根據(jù)levy 飛行機(jī)制構(gòu)建自適應(yīng)變異策略避免PSO 算法迭代后期陷入局部最優(yōu)，并利用概率測度法分析了算法的收斂性.仿真結(jié)果表明，與其它的幾種算法進(jìn)行比較，HDPSO-DE 算法的收斂精度與收斂速度均有提升.

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

2.1 構(gòu)建初始種群

HDPSO-DE 算法中的粒子表示MPE 問題的一種解釋，即貝葉斯網(wǎng)絡(luò)所有節(jié)點(diǎn)的狀態(tài)取值.設(shè)算法的初始種群為其中 N 為種群的規(guī)模.隨機(jī)初始化第i 個(gè)粒子其中n 為貝葉斯網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)量.對于粒子的第k 個(gè)節(jié)點(diǎn)若 k∈E 為證據(jù)節(jié)點(diǎn)直接賦值，否則為非證據(jù)節(jié)點(diǎn)，根據(jù)節(jié)點(diǎn)上下限隨機(jī)賦值.

式中xik表示網(wǎng)絡(luò)中第i 個(gè)粒子的第k 節(jié)點(diǎn)，π(xik)表示節(jié)點(diǎn)xik的父節(jié)點(diǎn).P(xi1，xi2，…，xin)表示的是貝葉斯網(wǎng)絡(luò)的聯(lián)合概率分布，P(xik|π(xik)為第k 節(jié)點(diǎn)的條件概率分布.

文獻(xiàn)［13］利用反向?qū)W習(xí)策略(Opposition Based Learning，OBL)更新PSO，增加了種群的多樣性，本文將聚類思想［14］引入到反向?qū)W習(xí)策略中構(gòu)建了自適應(yīng)的反向?qū)W習(xí) (A-daptive Opposition Based Learning，AOBL)策略.根據(jù)聚類思想即種群G(0)每個(gè)粒子與最佳粒子之間的距離構(gòu)建了如式(3)所示的每個(gè)粒子的自適應(yīng)反向?qū)W習(xí)參數(shù)ωi，將ωi代入式(4)建立了自適應(yīng)的反向?qū)W習(xí)策略.

2.2 HDPSO-DE 算法的迭代過程

為了平衡粒子群算法的局部搜索與全局搜索，文獻(xiàn)［15］建立了依概率分層的簡單粒子群(Probability Hierarchical Simple PSO，PHSPSO)算法，但由于其概率值是固定的，迭代后期算法的收斂速度下降.為提高迭代后期算法的收斂速度，將DE 變異算子引入到PSO，根據(jù)概率分層思想建立如式(5)的APHS 搜索策略.利用自適應(yīng)的學(xué)習(xí)因子 μ1、μ2指導(dǎo)當(dāng)前粒子向不同的導(dǎo)引粒子學(xué)習(xí)，根據(jù)導(dǎo)引粒子的不同共有三種APHS 搜索策略:APHS-G、APHS-R 與 APHS-P.

式中APHS-G 表示向全局最優(yōu)解粒子Gt學(xué)習(xí)，APHS-R 表示向隨機(jī)粒子xrand學(xué)習(xí)，APHS-P 向當(dāng)前極值粒子Pt學(xué)習(xí)，μ1、μ2是根據(jù)聚類思想［14］與迭代過程構(gòu)建的.

APHS-G搜索策略:為了提高粒子群算法的搜索效率，當(dāng)rand≥μ1時(shí)粒子向?qū)бＷ?Gt學(xué)習(xí).為避免 gbest、ω 的不合理取值對算法性能的影響，以多交叉操作［16］為理論依據(jù)，將DEcurrent-to-best1 變異算子引入到PSO，省略PSO 的速度項(xiàng)構(gòu)建了如式(8)所示的APHS-G 搜索策略，即從種群G'(0)隨機(jī)選擇的個(gè)體利用之間的差異性指導(dǎo)粒子xtik更新.

APHS-R搜索策略:粒子群算法迭代后期，由于全部粒子向全局最優(yōu)解粒子靠攏，易造成種群多樣性喪失而陷入局部最優(yōu).為避免算法出現(xiàn)早熟收斂現(xiàn)象，當(dāng)rand≤μ2時(shí)粒子向?qū)бＷ觴rand學(xué)習(xí).將DE and1 變異算子引入粒子更新過程，構(gòu)建了如式(10)所示的 APHS-R 搜索策略，即從種群G'(0)隨機(jī)選擇的個(gè)體利用種群的相關(guān)信息即指導(dǎo)當(dāng)前粒子更新.

式中 c1為通過式(9)確定的自適應(yīng)參數(shù)，c2、c3為［0，1］之間的隨機(jī)數(shù).

APHS-P搜索策略:為了平衡局部搜索與全局搜索，當(dāng)μ2≤rand≤μ1時(shí)粒子向?qū)бＷ觩t學(xué)習(xí)，導(dǎo)引粒子pt是根據(jù)式(11)所示的個(gè)體維度信息確定的.然后利用式(12)所示的APHS-P 搜索策略更新個(gè)體，利用個(gè)體間的相互協(xié)作即將搜索的范圍推廣到整個(gè)種群中，通過獲取種群中所有個(gè)體信息來擴(kuò)大搜索的范圍.

由于種群的多樣性會隨著迭代而逐漸減小，導(dǎo)致算法迭代后期易陷入局部最優(yōu).本文根據(jù)文獻(xiàn)［17］提出的擬熵值QE(t)作為判斷種群多樣性的指標(biāo).其中Pi(t)是根據(jù)式(16)確定歷史最優(yōu)粒子的適應(yīng)度值，當(dāng)?shù)?t 次迭代的擬熵值QE(t)滿足式(17)時(shí)種群的多樣性喪失.

自適應(yīng)變異策略:文獻(xiàn)［18］將Levy 飛行機(jī)制應(yīng)用到船舶分配泊位問題中，提高了種群的多樣性，避免算法陷入局部最優(yōu).本文將聚類思想［15］引入到Levy 飛行機(jī)制的離散步長因子中，建了如式(18)的自適應(yīng)步長因子α.在［0，α］之內(nèi)隨機(jī)選擇區(qū)間［N1，N2］作為變異位置，并利用levy 飛行機(jī)制建立如式(19)所示的擾動函數(shù)產(chǎn)生變異位置的值.

式中 U 為標(biāo)準(zhǔn)均勻分布，μ=t－β，1＜β＜3，μ 和 ν 服從正態(tài)分布:μ ～ N(0，φ2)，ν ～ N(0，1).由式(18)可知當(dāng)個(gè)體越接近最優(yōu)個(gè)體，比例因子的值越大，自適應(yīng)步長因子α 越大，產(chǎn)生變異區(qū)間的范圍越廣，更新粒子與原粒子的差異越大.

當(dāng)滿足公式(17)時(shí)，利用自適應(yīng)的變異策略增加種群的多樣性.設(shè)第t 次迭代時(shí)種群的隨機(jī)粒子根據(jù)式(18)產(chǎn)生自適應(yīng)步長因子α=6，選擇區(qū)間［4，6］作為變異位置，根據(jù)擾動函數(shù)生成變異位置的值Nt=313.利用自適應(yīng)的變異策略即公式(20)產(chǎn)生更新粒子1233131.

2.3 HDPSO-DE 算法步驟

步驟1.隨機(jī)生成初始種群，并利用自適應(yīng)的反向?qū)W習(xí)策略構(gòu)建反向種群，選取兩個(gè)種群中較好的個(gè)體建立初始種群;

步驟2.當(dāng)自適應(yīng)學(xué)習(xí)因子μ1≤rand 時(shí)粒子向?qū)бＷ覩t學(xué)習(xí)學(xué)習(xí)，根據(jù)APHS-G 搜索策略更新粒子，增強(qiáng)算法的局部搜索;

步驟3.當(dāng)自適應(yīng)學(xué)習(xí)因子μ2≥rand 時(shí)粒子向?qū)бＷ觴rand學(xué)習(xí)，根據(jù)APHS-R 搜索策略更新粒子，增強(qiáng)算法的全局搜索;

步驟 4.當(dāng) μ2≤rand≤μ1時(shí)粒子向?qū)бＷ?Pt學(xué)習(xí)，根據(jù)APHS-P 搜索算子更新粒子，平衡算法的局部搜索與全局搜索;

步驟5.種群中的全部粒子更新完之后，根據(jù)種群公式(15)計(jì)算種群的多樣性，并根據(jù)式(17)判斷種群的多樣性是否喪失，滿足條件時(shí)轉(zhuǎn)到步驟6 產(chǎn)生新個(gè)體.否則跳轉(zhuǎn)至步驟7;

步驟6.根據(jù)自適應(yīng)變異策略產(chǎn)生新個(gè)體增加種群多樣性，提高算法跳出局部最優(yōu)能力;

步驟 7.若滿足t＜tmax，則t=t+1，跳轉(zhuǎn)步驟2;否則輸出種群中適應(yīng)度最大的粒子即MPE 問題的最佳解釋.

2.4 HDPSO-DE 算法收斂性分析

根據(jù)概率測度法［19］分析算法HDPSO-DE 的收斂性.

引理 1.HDPSO-DE 算法滿足:f(N(z，ξ))≥f(z)，若 ξ∈Sgbest，則 f(N(z，ξ))≥f(ξ).

其中f 為HDPSO-DE 算法求解最大化問題的適應(yīng)度函數(shù)，N 為產(chǎn)生較優(yōu)最新解的函數(shù)，z 為搜索空間S 的子集最優(yōu)解空間Sgbest中的粒子，是在S 上產(chǎn)生可接受函數(shù)值的上確界，ξ 為算法在S 上隨機(jī)粒子.

證明:根據(jù)2.2 節(jié)的描述，在 HDPSO-DE 算法可將函數(shù)N 定義為:

引理 2.HDPSO-DE 算法的最優(yōu)解空間 Sgbest，當(dāng)滿足L［Sgbest］＞0時(shí)，式(22)成立.

式中，μt( * )為第t 次迭代結(jié)果的概率測度.

證明:HDPSO-DE 算法中粒子的搜索空間為S，顯然它的Lebesgue［20］總是大于 0，即 L［S］＞0.其中 HDPSO-DE 算法的最優(yōu)解空間Sgbest屬于 Borel［20］的一個(gè)子集，由算法的最優(yōu)解定義可得 L［Sgbest］＞0且0＜μi，t(Sgbest)＜1，由 μt產(chǎn)生的對Sgbest的概率測度為:

將式(23)代入式(22)可到:

至此引理2 得證.

根據(jù)概率測度法［20］可知HDPSO-DE 算法滿足式(25).

式(25)說明表示在t 第次的結(jié)果xt落到Sgbest里的概率值為1，即算法經(jīng)過有限次迭代后，HDPSO-DE 算法中一定有存在最佳區(qū)域Sgbest的個(gè)體.由算法的迭代性原則可知尋找到最佳個(gè)體之后的所有迭代中，種群中所有個(gè)體都向Sgbest靠攏，最終收斂于Sgbest.

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

為了驗(yàn)證HDPSO-DE 算法性能，在操作系統(tǒng)為Windows7，處理器為 Intel i3 3.40 GHz CPU，內(nèi)存為 4GB，軟件環(huán)境為M atlab 2010a.基于貝葉斯網(wǎng)絡(luò)工具箱 FullBNT-1.0.7 中進(jìn)行實(shí)驗(yàn)仿真，選擇經(jīng)典的網(wǎng)絡(luò)有Asia 網(wǎng)絡(luò)、Insurance 網(wǎng)絡(luò)、Alarm 網(wǎng)絡(luò)、Hailfinder 網(wǎng)絡(luò).其中標(biāo)準(zhǔn)的 A-sia 網(wǎng)絡(luò)具有 8 個(gè)節(jié)點(diǎn)、8 條邊;Insurance 網(wǎng)絡(luò)具有 27 個(gè)節(jié)點(diǎn)、52 條邊;Alarm 網(wǎng)絡(luò)具有 37 個(gè)節(jié)點(diǎn)、46 條邊;Hailfinder 網(wǎng)絡(luò)具有 56 個(gè)節(jié)點(diǎn)、66 條邊.選擇的對比項(xiàng)為適應(yīng)度F:貝葉斯網(wǎng)絡(luò)聯(lián)合概率的對數(shù)值.Ext(Execution Time):找到最佳解釋所需的時(shí)間.

3.1 算法不同算子貢獻(xiàn)度分析

為了驗(yàn)證不同的搜索策略對算法收斂精度的影響，在Asia 網(wǎng)絡(luò)、Insurance 網(wǎng)絡(luò)、Alarm 網(wǎng)絡(luò)、Hailfinder 網(wǎng)絡(luò)中，以2-M PE 問題為例分析了不同搜索策略對搜索精度以及搜索效率的貢獻(xiàn)度，具體的實(shí)驗(yàn)結(jié)果如表1 和圖1 所示.其中G 表示包括自適應(yīng)的反向?qū)W習(xí)策略與APHS-G 搜索策略，R 表示自適應(yīng)的反向?qū)W習(xí)策略與 APHS-R 搜索策略，P 表示包含自適應(yīng)的反向?qū)W習(xí)策略與APHS-P 搜索策略，L 表示僅有根據(jù)levy 飛行機(jī)制建立的自適應(yīng)變異策略，NL 表示全部的策略.

表1 HDPSO-DE 算法不同搜索策略的貢獻(xiàn)度分析Table 1 Contribution analysis of different search strategies in HDPSO-DE algorithm

根據(jù)表1 可知在節(jié)點(diǎn)數(shù)較少的網(wǎng)絡(luò)如Asia 網(wǎng)絡(luò)中自適應(yīng)變異策略并未提高算法的收斂精度，這是由于在小網(wǎng)絡(luò)中搜索的范圍較小，迭代后期不需要增加種群的多樣性來跳出局部最優(yōu).但在節(jié)點(diǎn)較多的網(wǎng)絡(luò)如Insurance 網(wǎng)絡(luò)、Alarm 網(wǎng)絡(luò)、Hailfinder 網(wǎng)絡(luò)，由于節(jié)點(diǎn)增多，搜索的范圍的較大，在迭代后期利用自適應(yīng)變異策略增加種群的多樣性，避免算法陷入局部最優(yōu)，因而算法的搜索精度與 APHS-G 搜索策略、APHS-R 搜索策略、APHS-P 搜索策略相比分別提升了12.32%、8.35%、9.97%.HDPSO-DE 算法的搜索精度在同時(shí)使用自適應(yīng)的反向?qū)W習(xí)策略、APHS 搜索策略與自適應(yīng)的變異策略時(shí)最高.與其他四種情況相比分別提升了22.32%、18.35%、17.97%、15.43%.這是由于自適應(yīng)的反向?qū)W習(xí)策略增加迭代初期的搜索范圍，APHS 搜索策略平衡了迭代過程中的局部搜索與全局搜索，而自適應(yīng)變異策略增加了迭代后期算法的搜索范圍，避免算法陷入局部最優(yōu).

圖1 不同策略的時(shí)間對比圖Fig.1 Time comparsion of different strategies

由圖1 可知利用自適應(yīng)的反向?qū)W習(xí)策略與APHS-G 搜索策略的搜索效率雖然是最高，但是其收斂精度較低，這是由于迭代后期種群多樣性喪失而易陷入局部最優(yōu).而同時(shí)使用自適應(yīng)的反向?qū)W習(xí)策略、APHS 搜索策略與自適應(yīng)的變異策略雖然搜索效率比利用ALBO 策略與APHS-G 搜索策略低1.74%，但其收斂精度比其高22.32%，這是由于APHS 搜索策略中的APHS-G 搜索策略提高了算法的搜索效率，APHS-R搜索策略提高了算法的搜索精度，并通過自適應(yīng)學(xué)習(xí)因子μ1、μ2平衡算法的局部搜索與全局搜索.HDPSO-DE算法使用全部搜索策略的搜索效率比只使用APHS-R 搜索策略平均高出10.74%，比只使用APHS-P 搜索策略平均高出7.74%，比僅適用自適應(yīng)變異搜索策略平均高出11.65%.總體而言HDPSO-DE 算法在保證算法搜索精度的基礎(chǔ)上提高了搜索效率.

3.2 與其他算法的對比

在相同的實(shí)驗(yàn)平臺下，HDPSO-DE 算法與DOSI 算法、DMVPSO 算法、SimpleSGS 算法、NGA 算法進(jìn)行實(shí)驗(yàn)對比.其中本文算法最大迭代次數(shù)為100，初始種群的規(guī)模為50.根據(jù)文獻(xiàn)［7］設(shè) NGA 中的變異概率為 0.01，交叉概率 α 為 0.9.根據(jù)文獻(xiàn)［9］設(shè)SimpleSGS 算法的噪聲概率pn為0.021，選擇度量CN為0.7，終止下限 Umin為0.0032.根據(jù)文獻(xiàn)［10］設(shè)DMVPSO 算法中獨(dú)立性測試的置信度 w 為0.01，c1、c2統(tǒng)計(jì)閾值分別設(shè)置為0.05、0.16.根據(jù)文獻(xiàn)［11］設(shè)DOSI 算法的子種群規(guī)模為20，精英個(gè)體閾值 σ 為 0.2，尺度因子 c1、c2為［0，0.2］之間的隨機(jī)數(shù).分別在 Asia 網(wǎng)絡(luò)、Insurance 網(wǎng)絡(luò)、A-larm 網(wǎng)絡(luò)、Hailfinder 網(wǎng)絡(luò)下計(jì)算 k-MPE(k=2，4，6，8)問題的最佳解釋.實(shí)驗(yàn)結(jié)果如下:表2、表3、表4、表5 是不同的網(wǎng)絡(luò)算法適應(yīng)度F 值，其中BEST 表示100 次實(shí)驗(yàn)中搜索的最佳結(jié)果，AVERAGE 表示100 次實(shí)驗(yàn)結(jié)果的平均值;圖2 是算法在不同網(wǎng)絡(luò)的時(shí)間.

表2 Asia 網(wǎng)絡(luò)不同算法的適應(yīng)度值Table 2 Fitness value of different algorithms in Asia network

由表2 可知，在Asia 網(wǎng)絡(luò)雖然本文算法與DOSI 算法的BEST 值是相同，但本文算法的AVERAGE 值比DOSI 算法高1.24%，表明本文算法的穩(wěn)定性高于DOSI 算法.這是由于在迭代過程中APHS-P 搜索策略平衡了算法的全局搜索與局部搜索，提高了算法的穩(wěn)定性.本文的AVERAGE 值與DMVPSO 算法、SimpleSGS 算法、NGA 算法相比平均提高了7.32%、8.35%、10.97%，這是由于迭代初期利用APHS-R 搜索策略提高粒子群算法的全局搜索，提高粒子群算法的搜索范圍，避免算法陷入局部最優(yōu).

由表3 可知，在Insurance 網(wǎng)絡(luò)本文算法的BEST 值與DOSI 算法、DMVPSO 算法、SimpleSGS 算法、NGA 算法相比平均提高了1.01%、2.37%、5.19%、8.64%，這是由于節(jié)點(diǎn)的增多搜索范圍變廣，而HDPSO-DE 算法利用自適應(yīng)的反向?qū)W習(xí)策略增加了初始種群的多樣性，提高了算法的全局搜索能力，避免算法陷入局部最優(yōu).與其他算法相比，本文算法的AVERAGE 值平局提升了2.18%、5.68%、8.94%、12.92%，這是由于本文算法利用APHS-P 搜索策略平衡算法的局部搜索與全局搜索，即保證搜索效率又提高搜索精度.

表3 Insurance 網(wǎng)絡(luò)不同算法的適應(yīng)度值Table 3 Fitness value of different algorithms in Insurance network

表4 Alarm 網(wǎng)絡(luò)不同算法的適應(yīng)度值Table 4 Fitness value of different algorithms in Alarm network

由表4 可知，在Alarm 網(wǎng)絡(luò)下，本文算法的BEST 值與DOSI 算法、DMVPSO 算法、SimpleSGS 算法、NGA 算法相比平均提高了2.18%、3.85%、6.45%、8.05%，這是由于迭代后期自適應(yīng)學(xué)習(xí)因子μ1的值較大，利用APHS-G 搜索策略提高算法迭代后期的局部搜索;迭代初期自適應(yīng)學(xué)習(xí)因子μ2的值較大，利用APHS-R 搜索策略提高算法迭代初期的全局搜索.與其他算法相比，本文算法的 AVERAGE 值平局提升了5.18%、8.68%、10.94%、15.92%，這是由于本文算法根據(jù)自適應(yīng)學(xué)習(xí)因子μ1、μ2以及APHS-P 搜索策略平衡算法的局部搜索與全局搜索，提高了算法的搜索精度.

表5 Hailfinder 網(wǎng)絡(luò)不同算法的適應(yīng)度值Table 5 Fitness value of different algorithms in Hailfinder network

由表5 可知，在Hailfinder 網(wǎng)絡(luò)下，本文算法的 BEST 值在8-MPE 問題時(shí)比DOSI 算法小，這是由于本文算法利用APHS-G 搜索策略提高了算法的搜索速度，但也縮小搜索的范圍，降低了搜索精度.而DOSI 算法根據(jù)馬爾科夫毯的性質(zhì)將Hailfinder 網(wǎng)絡(luò)劃分為多個(gè)子網(wǎng)絡(luò)進(jìn)行迭代更新，在大網(wǎng)絡(luò)中擴(kuò)大算法的搜索范圍，提高了搜索的精度.但是本文算法的AVERAGE 值與 DOSI 算法、DMVPSO 算法、SimpleSGS 算法、NGA 算法相比平均提升了 4.38%、9.08%、11.37%、19.92%，這是由于本文算法利用自適應(yīng)的反向?qū)W習(xí)策略增加了初始種群的多樣性，提高了算法迭代初期的全局搜索，算法的迭代后期根據(jù)levy 飛行機(jī)制建立的自適應(yīng)變異策略增加了迭代后期的種群多樣性，避免算法陷入局部最優(yōu).

圖2 不同算法的時(shí)間對比圖Fig.2 Time comparison of different algorithms

由圖2 可知，在節(jié)點(diǎn)較少的網(wǎng)絡(luò)如Asia 網(wǎng)絡(luò)中算法的時(shí)間比DOSI 算法的時(shí)間稍長，這是由于HDPSO-DE 算法為了提升算法的全局尋優(yōu)能力，利用自適應(yīng)的反向?qū)W習(xí)算子增加初始種群的搜索空間，但同時(shí)也增加算法的搜索時(shí)間;為了避免迭代后期陷入局部最優(yōu)，根據(jù)levy 飛行機(jī)制建立的自適應(yīng)變異策略同樣也增加了算法的搜索時(shí)間.但是在節(jié)點(diǎn)較多的網(wǎng)絡(luò)如Insurance 網(wǎng)絡(luò)、Alarm 網(wǎng)絡(luò)、Halifinder 網(wǎng)絡(luò)中本文算法時(shí)間最少，與 DOSI 算法、DMVPSO 算法、SimpleSGS 算法、NGA 算法算法相比平均縮短了6.23%，12.04%，8.42%，15.12%.這是由于隨著節(jié)點(diǎn)增多搜索的空間變廣，根據(jù)差分變異算子構(gòu)建的APHS 策略平衡了迭代的過程中局部搜索與全局搜索，APHS策略中的自適應(yīng)學(xué)習(xí)因子μ1的值隨著迭代逐漸變小，即利用利用APHS-G 搜索策略提高算法迭代后期的局部搜索，因而能夠較短的時(shí)間搜索到最佳解釋.總體而言HDPSO-DE 算法在大型網(wǎng)絡(luò)中比其它算法搜索效率的優(yōu)勢明顯.

4 結(jié)束語

本文提出了基于混合粒子群-差分算法的貝葉斯網(wǎng)絡(luò)推理學(xué)習(xí)算法HDPSO-DE.算法通過ALBO 策略擴(kuò)大了初始種群的多樣性，保證算法迭代初期的全局搜索.將差分變異算子引入到PSO，根據(jù)概率分層思想構(gòu)建APHS 搜索策略，平衡算法迭代過程中的全局搜索與局部搜索.根據(jù)levy 飛行機(jī)制構(gòu)建自適應(yīng)的變異策略增強(qiáng)迭代后期種群的多樣性，避免算法陷入局部最優(yōu).利用概率測度法可知:HDPSO-DE 算法通過種群的迭代可以搜索到MPE 問題的最佳解釋，實(shí)驗(yàn)仿真證明HDPSO-DE 算法與其他算法相比搜索精度與搜索效率有明顯的優(yōu)勢.