摘要：針對基于進(jìn)化方法的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)易陷入局部最優(yōu)和尋優(yōu)效率低的問題，提出一種利用遺傳算法聯(lián)姻策略學(xué)習(xí)貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)的技術(shù). 首先設(shè)計了“同”聯(lián)姻策略，兩個種群使用相同的搜索策略和評估模型完成貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí). 對學(xué)習(xí)到質(zhì)量最好的子代個體進(jìn)行聯(lián)姻，將所得的質(zhì)量最佳的子代個體共同返回兩個種群中進(jìn)行迭代. 由于聯(lián)姻的子代保留了另一個種群的片段，對種群中基因的多樣性起到很好的保障，有效規(guī)避了近親繁殖造成的缺陷. 針對同代理模型的聯(lián)姻策略無法同時兼顧網(wǎng)絡(luò)結(jié)構(gòu)質(zhì)量及學(xué)習(xí)效率的問題，提出基于集成的遺傳算法聯(lián)姻策略，兩個種群分別使用不同的代理模型和搜索策略進(jìn)行學(xué)習(xí)，對各自學(xué)習(xí)到的當(dāng)代最優(yōu)個體進(jìn)行聯(lián)姻迭代. 實驗表明，提出的算法在小、中和大規(guī)模網(wǎng)絡(luò)上的學(xué)習(xí)精度和有效性都優(yōu)于對比算法.

關(guān)鍵詞：遺傳算法，聯(lián)姻策略，代理模型，貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)

中圖分類號：TP181 文獻(xiàn)標(biāo)志碼：A

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

在各類學(xué)習(xí)方法中，進(jìn)化算法是一種基于生物進(jìn)化思想尋找最優(yōu)解的技術(shù)，遺傳算法是其中最具代表性的一類，與常規(guī)算法相比，能更好地利用全局信息，因其具有快速、易于實現(xiàn)、自適應(yīng)等優(yōu)點被廣泛應(yīng)用于貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)［6］. 但該類算法在學(xué)習(xí)過程中存在因種群單一導(dǎo)致早熟易于陷入局部最優(yōu)和搜索效率低的問題.

針對上述問題，涌現(xiàn)出許多相關(guān)的研究方法，主要圍繞高質(zhì)量的初始種群和收斂緩慢兩個問題來設(shè)計優(yōu)化策略. 部分學(xué)者著眼于初始種群的優(yōu)化. 如武夢嬌和劉繼［7］提出MIC?MGA，利用最大信息系數(shù)有效地度量變量間的相互依賴關(guān)系. 汪春峰和張永紅［8］提出利用“-步”依賴系數(shù)矩陣獲得無向圖的方法，極大地減弱了單純使用遺傳算法學(xué)習(xí)對初始群體的依賴性. 許建銳等［9］提出KDE?CGA，通過優(yōu)化核密度函數(shù)對小規(guī)模初始化種群進(jìn)行拓展. 劉浩然等［10］基于改進(jìn)狼群捕食行為，提出用于節(jié)點序?qū)?yōu)的GWPA 算法，使用深度優(yōu)先搜索方法對定向的最大支撐樹進(jìn)行拓?fù)渑判蛏沙跏挤N群，提出自適應(yīng)動態(tài)因子，增強(qiáng)算法局部搜索能力.

由于遺傳算法存在迭代次數(shù)難以控制、收斂緩慢的現(xiàn)象［11］，所以，學(xué)者們關(guān)注遺傳操作的改進(jìn). 如曹如勝等［12］提出CGASA，將云遺傳算法和模擬退火算法相結(jié)合，有效地避免了算法陷入局部最優(yōu)的缺陷. 汪春峰和將妍［13］提出混合型算法ABC?GA，利用蜂群食物源尋優(yōu)規(guī)則進(jìn)行優(yōu)化.Khanteymoori et al［14］提出混合算法BSPSO，將PSO 更新規(guī)則與GA 相結(jié)合. 粒子之間的復(fù)制增加了在搜索空間中制造更理想粒子的概率. 簡敏［15］將遺傳算法與K2 算法相結(jié)合，提出GA?K2.吳家皋等［16］在GA ? K2 算法的基礎(chǔ)上提出BS ?GAK2 算法和SA?GAK2 以二分搜索方式進(jìn)行多時間段貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)的學(xué)習(xí)和優(yōu)化. Kabli etal［17］提出Chain?GA 算法，將鏈模型作為評估方法，有效減小了計算復(fù)雜度. Alonso?Barba et al［18］提出樹代理模型，進(jìn)一步提高算法準(zhǔn)確率. 在此基礎(chǔ)上，王慧玲等［19］提出一種新的評估序質(zhì)量的方法，即完全代理模型評估法，合理利用了變量間依賴強(qiáng)度，對父節(jié)點的計算量進(jìn)行有效控制，變量序結(jié)構(gòu)空間的規(guī)模大幅度縮小，并有效提高了評價序質(zhì)量的精度.

上述基于遺傳技術(shù)的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)分別在精度和收斂性上得到了很大的提升，但如何同時優(yōu)化這兩者，還沒有好的解決方案. 針對該問題，本文提出基于遺傳算法聯(lián)姻策略的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)技術(shù)，其貢獻(xiàn)如下.

（1）提出基于同代理模型的聯(lián)姻策略，兩個種群使用相同的搜索策略和評估模型完成貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí). 由于該策略的子代保留了另一個種群的片段，對種群中基因的多樣性起到很好的保障，有效規(guī)避了近親繁殖造成的缺陷.

（2）針對同代理模型聯(lián)姻策略無法同時兼顧網(wǎng)絡(luò)結(jié)構(gòu)質(zhì)量及學(xué)習(xí)效率的問題，設(shè)計了基于不同代理模型和不同搜索策略的集成聯(lián)姻遺傳策略的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)技術(shù). 該技術(shù)既保證了種群多樣性和學(xué)習(xí)效率，也能夠?qū)λ锌赡艹霈F(xiàn)的網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行高質(zhì)量的評估.

對比實驗表明，本文提出的算法在小、中和大規(guī)模網(wǎng)絡(luò)上的精度和有效性都優(yōu)于對比算法.

1 基于同代理模型的聯(lián)姻策略

一般地，在生物的進(jìn)化過程中，普遍存在一種現(xiàn)象，即若父代近親進(jìn)行繁殖，其后代的表現(xiàn)往往不如父系，而若有較小的血緣關(guān)系或地域差別較大的父系雜交，其后代往往表現(xiàn)出較好的特征.另一方面，在單一群體下，群體規(guī)模受限，且有相當(dāng)比例的子代可能來自同一血緣，基因片段過于接近，算法的收斂性無法得到保障.

遺傳算法引入聯(lián)姻策略［20］，是一種多種群并行進(jìn)化的遺傳算法，其基本思想是設(shè)置多個種群并行優(yōu)化，當(dāng)種群與種群之間滿足某種條件時，不同種群間的當(dāng)代最佳個體兩兩聯(lián)姻，并將聯(lián)姻后代中的最佳個體復(fù)制到相應(yīng)的兩種群中，參與下一代的進(jìn)化過程. 由于聯(lián)姻后代攜帶了另一個種群的基因，聯(lián)姻策略一方面能保持種群中基因的多樣性，避免近親繁殖帶來的危害，另一方面由于引進(jìn)其他種群的優(yōu)良基因，因而加快算法的搜索過程. 圖1 為雙種群聯(lián)姻模式圖.

本文首先提出基于同代理模型的聯(lián)姻策略.設(shè)置兩個種群同時并行進(jìn)化，在每次迭代后分別取兩種群中的當(dāng)代最佳個體進(jìn)行聯(lián)姻，將聯(lián)姻后的個體復(fù)制到原來的種群中，并與當(dāng)前種群的最佳個體進(jìn)行比較，保留最優(yōu)秀的個體作為“種子”進(jìn)入到種群的下一代進(jìn)化過程.