基于平行多種群與冗余基因策略的置信規則庫優化方法

徐曉濱 朱 偉 徐曉健 侯平智 ,2 常雷雷

置信規則庫(Belief rule base,BRB)是一種基于D-S (Dempster-Shafer)證據理論的復雜系統建模、分析與評價的專家系統方法.該方法以置信規則(Belief rule)為基礎,能夠較好地表示、建模和集成不確定條件下的多種類型信息[1-2].同時,作為一種“白箱(White box)”方法,BRB 還具有較強的可解釋性,專家可以更好地參與BRB 的建模、訓練以及學習過程.自提出以來,BRB 已成功應用于各個領域,如智慧醫療[3]、多屬性決策分析[4]以及軍事能力評估[5]等.

然而,BRB 的規模不宜過大,否則將會給建模造成巨大的困難.同時,由于人的認知不完備或者數據缺失,專家給定的初始化BRB 可能面臨所篩選關鍵指標及其取值不準確的情況,因此采用初始BRB 進行建模、評估和預測時,其結果精度可能不高.為了解決這些問題,需要對初始BRB 進行學習優化以明確其規模和提高建模精度.眾多研究者在多個領域開展了相關研究,主要可以分為3 類:BRB結構學習、BRB 參數學習以及BRB 結構與參數聯合優化.

BRB 結構學習的目的是識別與篩選關鍵前提屬性及其參考值.Chang 等[5]首先提出了基于主成分分析等維度約減技術的BRB 結構學習方法,對裝備體系綜合能力評估問題開展了相關研究;Wang等[6]提出動態調整BRB 規則的結構學習方法;Li等[7]提出了基于極小方差的前提屬性參考值確定方法,并基于此提出了安全性評估方法.

BRB 參數學習的目的是通過優化BRB 相關參數的取值以提高建模精度.Yang 等[8]提出BRB優化模型優化BRB 的參數.Zhou 等[9]基于期望極大估計算法提出了在線參數學習方法,對于時效性有較高要求的復雜決策問題提供了在線建模方法.Chen 等[10]對前提屬性參考值存在的約束進行分析,改進了BRB 系統的優化模型,將前提屬性參考值作為被訓練的參數進行參數學習,并將原優化模型稱為局部訓練模型,改進后的優化模型稱為全局訓練模型.Savan 等[11]、Chang 等[12]和馬炫等[13]提出了基于演化算法(Evolutionary algorithms,EA)的BRB 參數學習方法.Chang 等[12]對比了多種演化算法的求解效率,包括遺傳算法(Genetic algorithm,GA)、差分進化(Differential evolutionary,DE)算法以及粒子群(Particle swarm optimization,PSO)算法等.這些優化算法在解決解空間較大的理論與實踐問題方面具有較強的優勢.

在結構學習和參數學習的基礎上,Chang 等[14-16]進一步提出了對BRB 參數和結構進行優化的BRB聯合優化方法,通過構建雙層優化模型,在外層模型中優化BRB 結構,在內層模型中優化BRB參數,實現對BRB 參數與結構的聯合優化.Yang 等[16]提出BRB 結構和參數的聯合優化方法,采用啟發式策略(Heuristic strategy)優化BRB 結構,采用差分進化算法優化BRB 參數.

以上有關BRB 結構學習、參數學習的相關工作僅關注單一層面,而文獻[14-16]雖然實現了對BRB結構與參數的優化,但是其對BRB 結構和參數的優化仍然是分別開展,更具體而言,在外層模型中僅優化BRB 結構,在內層模型中僅優化BRB 參數.在本質上仍然屬于迭代(Iterative)的過程,并未實現對BRB 結構與參數的同時優化.

基于此,本文提出一種基于平行多種群策略和冗余基因策略的BRB 優化方法.該方法中,采用具有不同基因數量的多個種群來編碼具有不同數量規則的BRB,多個不同種群共同參與優化過程來實現對BRB 結構與參數進行優化的目的;在優化過程中,為具有較少基因的個體(具有較少規則的BRB)補充部分冗余基因,以確保不同長度個體能夠同時參與優化過程.采用該方法,可以一次產生具有不同數量規則BRB 的最優解,并自動生成帕累托前沿,決策者可以根據自身偏好或實際問題需求在帕累托前沿上篩選最優解.最終以某輸油管道泄漏檢測問題為例對本文提出的方法進行驗證.

1 BRB 理論基礎及推理過程

1.1 BRB 基礎

在傳統D-S 證據理論的基礎上,Yang 等[8]進一步提出采用具有置信結構的IF-THEN 規則來表達、建模與推理不確定條件下的多種類型信息,包括定性定量信息、語義數值信息、完備與不完備信息等.由具有同一置信結構的IF-THEN 規則組合而成的規則庫即稱為置信規則庫(BRB),其中第k條規則如式(1)所示:

其中,xm(m=1,···,M)表示第m個前提屬性,(m=1,···,M;k=1,···,K)表示第k條規則中第m個前提屬性的參考值;βn,k(n=1,···,N)表示第k條規則中第n個評估結果Dn的置信度;“∧”表示規則滿足交集假設;θk和δm分別表示第k條規則和第m個前提屬性的權重.

相應的,當置信規則建立在并集假設下時,其表述形式如式(2)所示:

其中,“∨”代表規則滿足并集假設.

作為一種具有白箱特征的專家系統方法,BRB已經廣泛應用于解決多復雜系統問題[17-18].

1.2 BRB 的推理

BRB 系統的規則推理過程主要有4 個步驟.

步驟1.計算前提屬性與參考值之間的匹配度.

對于給定前提屬性xm的值為,第j條規則中第m個屬性的匹配度如式(3)所示:

其中,cm表示第m個屬性的置信度.如果沒有不完整的信息并且第m個屬性的置信度為1,則式(4)可以簡化為式(5):

步驟2.計算激活規則權重.

第k條規則的激活規則權重計算如式(6)所示:

其中,θk表示第k條規則的相對權重;表示第k條規則中第m個前提屬性與參考值集合xm之間的匹配度.如果wk＞0,表示第k條規則被激活,否則第k條規則未被激活.

步驟3.通過證據推理(Evidential reasoning,ER)算法融合被激活的規則,如式(7)(見本頁下方)和式(8)(見下頁上方)所示.式(7)和式(8)中,βn表示第n個評估結果的置信度.

步驟4.輸出結果.

融合相應的規則后得到評估結果的置信分布形式,如式(9)所示:

當評估結果輸出為單一值時,需要對步驟3 中的結果進行集成.假設評估等級Dn對應的效用值為U(Dn),則評估結果的綜合效用U可根據式(10)進行計算.

1.3 BRB 學習以及面臨的問題

當前BRB 的學習方法可大致分為3 類:

1)BRB 結構學習

BRB 結構學習主要思想是縮減BRB 規模或者是確定BRB 的最佳結構.BRB 規模與前提屬性的個數以及前提屬性的參考值有關[5-7].因此,BRB結構學習主要從這兩方面考慮.BRB 結構學習所解決的是由前提屬性的個數或者前提屬性的參考值個數過多而導致的組合爆炸的問題.

2)BRB 參數學習

BRB 參數學習主要思想是優化BRB 的參數提高建模精度[8-10].由于人的認知不完備或者數據缺失,專家給定的初始化BRB 可能面臨所篩選關鍵指標及其取值不準確的情況,因此采用初始BRB進行建模、評估和預測時,其結果精度可能不高.因此提出BRB 參數學習以提高對復雜非線性系統的建模能力.BRB 的參數優化模型取均方誤差或者絕對誤差作為優化目標函數,前提屬性的參考值,規則權重以及評估結果的置信度作為決策變量.目前BRB 的優化方法主要有主成分分析法(Principal component analysis,PCA)、牛頓法以及演化算法(Evolutionary algorithm,EA).

3)BRB 聯合優化

BRB 聯合優化的主要思想是對BRB 結構和參數同時優化以減小建模復雜度和提高建模精度[14-16].當前針對BRB 參數和結構優化的BRB 聯合優化方法[14-15]中,首先推導出集成模型精度(由均方差表示)與復雜度(與規則數量相關)的綜合優化目標,然后構建雙層優化模型,并提出基于演化算法的優化模型求解算法,最終實現對BRB 結構與參數的聯合優化.但是該方法對BRB 結構與參數的聯合優化是迭代進行,并未實現對BRB 結構與參數的同時優化.

根據彈性層狀體系理論，計算得到無機結合料層層底拉應力為0.263MPa。根據氣象資料，工程所在地區凍結指數F為1500.0℃·日，季節性凍土地區調整系數ka取0.74。計算得到現場綜合修正系數為-1.157。

綜上所述,當前BRB 學習相關研究中一般僅局限于結構學習或參數學習,而開展的BRB 結構與參數聯合優化的過程本質上也是迭代和分別進行,并未實現對BRB 結構與參數同時進行優化的目的.基于此,本文提出采用平行多種群策略和冗余基因策略的BRB 優化方法,實現對BRB 結構與參數進行同時優化的目的.

2 基于平行多種群策略的BRB 優化模型

2.1 平行多種群策略

當前,一般采用多種群策略來集成不同算子的優勢以解決大規模優化問題[19-22].具體而言,在不同種群中分別采用不同算子進行優化,在優化過程中進行對比并將其作為下一代分配優化資源的依據,綜合集成多種不同算子的共同優勢.這是由于傳統優化問題中并不涉及結構優化.因此,在將多種群策略應用于優化算法時,不同種群中的優化算子不同,但個體長度(編碼格式)仍是相同的.但這與本文要解決的核心問題有本質區別:本文研究的出發點是實現對BRB 結構和參數的同時優化,因此在本文采用的多種群策略中,不同種群中的個體長度(編碼格式)不同.

但是,同時優化BRB 結構與參數所面臨的最大挑戰在于,具有不同數量規則的BRB 規模不同,而采用演化算法進行求解時,要求種群中所有個體的長度相同.本文提出采用平行多種群策略解決這一問題.將具有不同數量規則的BRB 按照其規則數量劃分為多個種群,在單一種群中BRB 具有相同數量規則(個體長度相同),不同種群之間BRB規則數量不同(個體長度不同).換言之,將BRB 中規則數量K,也作為待優化參數之一引入第2.2 節中的優化模型中,以實現對BRB 結構與參數同時優化的目的.

圖1 表示平行多種群策略將初始種群劃分為具有不同規則數量的種群(種群規則數量相同),但仍不能用于交叉變異,需要添加冗余基因至所有個體長度相等(見第3 節).

圖1 平行多種群策略Fig.1 Parallel multiple population strategy

2.2 BRB 優化模型

基于第2.1 節提出的平行多種群策略,建立同時包含BRB 結構與參數的優化模型為

其中,k=1,···,K;n=1,···,N;m=1,···,M;pq∈[1,···,M].式(11b)表示規則數量在預定的最小規則數Kmin和最大規則數Kmax之間.式(11c)表示第m個前件屬性的參考值在下界lbm和上界ubm之間.式(11d)和式(11e)表示第m個前件屬性的參考值的上下界必須包含在規則中.式(11f)表示初始規則權重應該在 (0,1] 內.式(11g)表示評估結果的置信度應該在 [0,1] 內.式(11h)表示評估結果的置信度之和小于或者等于1 (當信息不完整時)＜1.

3 基于冗余基因策略的BRB 優化算法

為了求解第2.2 節中建立的優化模型,本節提出基于冗余基因策略的BRB 優化算法.基于冗余基因策略,對基因數量較少的個體(規則數量較少的BRB)補全部分冗余基因,至所有個體的長度相等.這樣所有個體的長度即一致,也就可以參與優化操作,而并不參與適應度計算.

基于冗余基因策略的BRB 優化求解算法共包括6 個步驟,如圖2 所示.

圖2 優化算法的6 個步驟Fig.2 Optimization algorithm with six steps

參數識別主要包括演化算法的參數設值和BRB 的參數設值.演化算法的參數包括種群個數、迭代次數等.BRB 的參數包括BRB 的規則個數、前提屬性(參考值)的個數、評估結果的置信度個數.

步驟2.初始化(編碼)

每一個個體代表一個具體的BRB.個體基因由BRB 的參數組成.BRB 的參數包括前提屬性的參考值、規則權重、評估結果的置信度以及表示BRB 中規則數量K.K的取值為離散整數,介于最小規則數Kmin和最大規則數Kmax之間.

不同的BRB 具有不同的規則數量,不同個體之間的基因個數也不相等,這就導致不同種群中的個體長度不同,因此不能進入下一步的交叉變異操作.

步驟3.交叉變異(補全冗余基因)

在進行交叉變異操作之前,首先需要對不同種群中的所有個體補全冗余基因,以確保所有個體的長度相同(所有個體包含基因數量相同),如圖3 所示.

圖3 添加冗余基因Fig.3 Add redundant genes

向各個個體中補全基因的操作步驟如下:首先識別具有最多基因數量的個體(即具有最多規則數量的BRB),以該個體的長度為標準長度;然后依次對每個個體補全冗余基因,需要注意補全基因應當滿足所在位置的上下限要求,且最后一位標志初始規則數量的基因K位置和取值不變.

補全基因后,所有個體長度將會相等,均為初始具有最多基因數量個體的長度.補全基因后個體將進入優化操作.本文采用的是差分進化[19-21]算法作為優化引擎,其優化操作包括交叉和變異.

其中,交叉算子CR=0.9,sn∈[1,2,···,n]是由每一個個體產生的隨機整數.

變異操作指出隨機選取種群中兩個不同個體,將其與待變異的個體進行合成,得到新的個體.第i個新個體可以由式(13)得到

其中,zr1,zr2和zr3是3 個隨機產生的個體,并且,變異算子F=0.5.

步驟4.適應度計算(刪除冗余基因、解碼)

經過交叉,變異操作后的個體中的基因已經得到優化,在進行適應度計算之前需要首先根據每個個體最后一位標志初始長度的基因K刪除在步驟3 中添加的冗余基因,換言之,只有與初始BRB 相關的基因才會進入適應度計算當中,步驟3 中添加的冗余基因不參與適應度計算,如圖4 所示.

圖4 刪除冗余基因Fig.4 Remove redundant genes

刪除冗余基因之后,根據基因編碼方案對剩余個體的基因進行解碼操作,然后進入適應度計算,包括輸入信息與前提屬性的匹配度計算,規則激活權重計算以及激活規則集成(見第1.2 節).

步驟5.選擇

通過比較個體的適應度值,選擇適應度值最小的個體作為最優個體作.在選擇適應度值的過程中,個體適應度值的比較僅局限于具有相同長度的個體或者具有相同規則數量的BRB.最終的最優個體是由不同規則數量的BRB 組成,而不是由特定數量規則的BRB 組成.

對于第i個個體,選擇個體的適應度函數獲得更低的額定值作為下一代.

其中,f(·)是適應度函數,本文中是指均方差(Mean square error,MSE).

步驟6.權衡分析

在選擇最優的個體之后,利用具有不同規則數量的最優BRB 導出帕累托前沿,通過考慮決策者的偏好和具體要求,進行權衡分析以產生最優解.

圖5 說明了具有兩個屬性(x1,x2)問題的權衡分析概念[23].圖5 表示包含兩個屬性(x1,x2)的帕累托前沿;Ⅰ點表示偏好x2的情況下決策者選擇的解決方案;Ⅱ點表示偏好x1的情況下決策者選擇的解決方案.

圖5 權衡分析Fig.5 Tradeoff analysis

4 案例分析

本節以輸油管道泄漏檢測為例,驗證本文中所提出方法的有效性.已知可以根據輸油管道進出口的流量差(FlowDiff)和壓力差(PressureDiff)推斷出輸油管道的泄漏尺寸值(Leaksize).流量差和壓力差是檢測管道中是否存在泄露并且與泄漏尺寸相關的兩個重要屬性.因此選擇流量差和壓力差作為BRB 的前提屬性,泄露尺寸作為輸出結果.為了便于對比分析,本文采用現有BRB 相關文獻中多次使用的實驗數據[9-10,24],該數據共包括從英國北部某地采集得到的2008 組輸油管道泄露數據.

為了與當前方法的進行公平比較,BRB 的參數設置與當前方法保持一致.首先構建BRB 的模型,BRB 采用5 個評估等級評估管道泄漏情況,其效用值分別為

前提屬性流量差FlowDiff∈[－10,2],壓力差PressureDiff∈[－0.02, 0.04].

本文研究的主要目的是實現BRB 結構和參數的同時優化,平行多種群與冗余基因策略適用于演化算法,如差分進化算法(DE),遺傳算法(GA),粒子群算法(PSO)等.在眾多優化算法中,DE 算法取得了較好的優勢,即其具有優化效率高,求解速度快且不易陷入局部最優解等優點.因此本文采用DE 作為BRB 結構與參數優化模型的求解算法,為了與當前方法進行比較,DE 優化算法的參數值和當前方法使用的參數值一致,其設置如下:

1)BRB 中規則數量取值范圍為3～8 條;

2)優化算法中個體數量設定為100;迭代次數為1 000 代;

3)交叉率和突變率設值為0.8 和0.8;

4)算法共運行30 次以驗證平行多種群與冗余基因策略方法的穩定性.

表1 給出了算法運行30 次之后具有不同數量規則的BRB 統計結果.通過表1 可以發現,當規則數量為3～8 條時,不同BRB 的最小值/平均值都遠小于其方差(小一個數量級),這說明本文提出的方法具有較好的穩定性.

圖6 進一步給出了本文提出方法在1 000代優化過程中帕累托前沿的優化過程.

通過表1 以及圖6,可以得出以下結論:

圖6 帕累托前沿的優化過程Fig.6 Optimal process of the Pareto frontier

表1 運行30 次的數據結果Table 1 Statistics of 30 runs

1)在1 000 代的優化過程中,帕累托前沿不斷向前推進;

2)當優化至100 代時(見圖6(b)),具有不同數量規則的BRB 實際上已經達到了比較穩定的可行解;

3)規則數量(即參數數量)對優化結果具有一定影響.當優化到100 代時,由于規則數量較多的BRB 的參數數量較多,此時具有6/7/8 條規則的BRB 并未取得較優解,也未在帕累托前沿上;

4)決策者可以根據自身偏好在帕累托前沿上選擇最優BRB.當不考慮偏好時,具有5 條規則BRB具有明顯優勢,其MSE 明顯小于前者,而后續隨著規則數量增加,MSE 也并未明顯大幅下降,即具有5 條規則的BRB 處于拐點(Elbow point)[25].

表2 給出了具有5 條規則的BRB,圖7 給出了模型預測結果與真實值之間的對比以及誤差.

表2 具有5 條規則的最優BRB 參數Table 2 Optimal BRB parameters with five rules

圖7 輸油管道泄漏檢測結果與誤差對比Fig.7 Pipeline leak detection test results and error comparison

表3 進一步對比了本文所得結果與已有文獻中針對該示例的計算結果.通過對比,可以發現:

表3 基于不同BRB 優化方法的實驗結果對比分析Table 3 Comparative analysis of experimental results based on different BRB optimization methods

1)與已有僅開展參數學習的研究[9-10,24]相比,根據不同的優化模型,BRB 參數學習的優化參數數量為336～349.其模型誤差MSE 均處于較高水平.文獻[6]提出動態優化方法,該方法涉及到的優化參數個數從349 降到39.其在降低建模復雜度方面與上述3 種方法相比取得了較好的結果.而本文采用的并行多種群與冗余基因策略的方法取得的模型誤差MSE 更小,即本文提出方法相對參數學習具有優勢.

2)本文所得結果稍劣于BRB 聯合優化方法[14]所得到的結果.原因在于:BRB 聯合優化方法屬于迭代方法,即在對BRB 參數進行優化時,并不優化其結構,而本文提出的方法在一次優化過程中同時實現對BRB 結構和參數的優化.換言之,在給定資源條件下,BRB 聯合優化仍然僅優化其參數(這是由其迭代優化的本質決定的),而本文所提出方法可以同時實現對BRB 結構與參數.在這種情況下,本文提出方法仍能取得與當前最優解(0.267 9)十分接近的結果(0.292 1)驗證了本文提出方法的有效性.

3)相比BRB 聯合優化方法,本文的另一優勢在于最終產生的結果以帕累托前沿的形式表示出來,決策者既可以根據自身需求或問題特點在帕累托前沿上選擇恰當的最優解,又可以在不考慮偏好的情況下,根據拐點原則通過權衡分析選擇無偏最優解.

5 結束語

為了實現對置信規則庫結構和參數同時優化的目的,本文提出一種基于并行多種群與冗余基因策略的置信規則庫優化方法.通過輸油管道泄漏檢測的例子驗證本文所提出方法的有效性.主要結論如下:

首先,通過并行多種群策略,具有不同規則數量的BRB 可以同時進入優化操作,因此可以同時優化BRB 的結構和參數.然后,通過提出冗余基因策略,具有不同長度的個體(BRB 具有不同的規則數量)可以進行交叉變異操作.只有與初始BRB 相關的基因才會進入適應度計算當中.最后,輸油管道泄漏檢測的例子結果表明,基于并行多種群與冗余基因策略的置信規則庫優化方法可以同時優化具有不同規則數量的多個BRB,隨著BRB 的優化,帕累托前沿不斷向前推進.最后可以通過拐點原則識別最佳BRB,也可以根據決策者的偏好來決定最佳BRB.下一步工作,需要對優化算法引擎展開進一步的研究.優化算法引擎需要大量的參數,這將導致優化效率下降.所以迫切需要找到更好的優化技術去解決這些問題.此外,還應當在更多理論和實際問題中對本文提出方法進行驗證.