順序故障診斷策略的測試費用期望值估計

張海峰,　陳君達

(1.中國北車長春軌道客車股份有限公司,吉林 長春　130062; 2.上海杰之能信息科技有限公司,上海　200072)

?

順序故障診斷策略的測試費用期望值估計

張海峰1,陳君達2

(1.中國北車長春軌道客車股份有限公司,吉林 長春130062; 2.上海杰之能信息科技有限公司,上海200072)

摘要:文章研究順序故障診斷策略,試圖最小化測試費用的期望值；闡述了3種經典算法及其思想,對信息熵和貪婪算法進行了深入討論;基于信息熵的貪婪算法,給出其測試費用期望值的一個上下界;當測試集滿足一定特征且測試費用相等時,給出了基于Huffman算法的一個估計。

關鍵詞:信息熵;貪婪算法;測試費用估計

0引言

順序故障診斷是指在已知故障可能范圍的前提下,通過一系列的測試來縮小這個范圍,最終達到確定某個故障的目的。以高鐵動車組的檢修[1]為例,維修檢測涉及一系列復雜機械和電子問題,其測試費用(或者因故障維修延遲而造成的鐵路運營損失)通常較高,因此,有必要對測試費用進行認真的估計,以便選取一個合適的測試順序,使得期望的測試費用最小化,這樣可以顯著降低診斷的成本,最終減少動車組的檢修成本。本文研究這類問題的數學基礎,為順序故障診斷的應用提供理論依據。

文獻[2]闡述了順序診斷的動態規劃算法,且給出了測試費用的期望值估計;文獻[3]給出了一種計算機輔助故障樹分析方法;文獻[4]給出了基于熵權法的故障診斷方法;文獻[5]介紹了一個基于信息熵的貪婪算法,本文進一步討論其性能,給出其測試費用期望值的一個上下界；文獻[6]敘述了Huffman算法在順序故障診斷策略中的應用,對于特殊的測試集可以達到最優解,但是沒有給出對測試集的要求。本文給出一大類測試集,證明可以應用Huffman算法對其構造最優解,并給出了測試費用期望值的估計。

1問題描述

設X為故障事件所對應的隨機變量。假定系統有N種可能發生的故障,設為s1,s2,…,sN共N個可能發生的故障,默認其滿足:

(1) 各種故障發生概率分別為pi(i=1,…，N),且最多只有一個故障發生。

(2) 設ti(i=1,…，M)為M個二元測試集,即每個測試結果只有“通過”和“未通過”2種狀態。

(3) 每個測試的費用分別是ci(i=1,…，M)。

(4) 測試矩陣D為一個0-1矩陣, 0表示當故障為si時,測試tj不通過；1表示故障為si時,測試tj通過。

(5) 測試集足夠區分所有的故障,即矩陣D的每行均不同。

根據上述條件給出一個測試序列,使得測試費用的期望值最小,為本文所研究的問題。測試費用期望值最小的測試序列的后一項可以隨著前若干項的測試結果而改變。比如有測試t1,t2,…,tM,一個可行的測試序列為:當t1通過時,下一步測試t2,否則下一步測試t3。當之前的測試結果足以確定故障時,停止測試。所以嚴格來說,需要一個測試序列的決策樹,使得其測試費用的期望值最小。

2概念及符號定義

本文算法描述中將使用信息熵和條件信息熵的概念[7]。

定義1設一個離散隨機變量X的概率分布為p1,p2,…,pN,則其信息熵為:

(1)

信息熵的單位為bit。

定義2設有離散隨機變量X與Y,且Y的概率分布為p1,p2,…,pN,則其信息熵為:

(2)

其中,y遍歷所有Y可能的取值。

直觀地說,條件熵代表當Y確定后,X的熵的期望值。信息熵代表一個隨機變量的混亂程度,也代表為了“確定”該變量所要花費的努力。問題描述中的故障狀態和測試結果都是一個隨機變量,以X和Ti來表示。X代表究竟發生的是哪個故障,Ti代表測試ti的結果。下文將應用這些隨機變量的信息熵。

3故障診斷策略算法

3.1動態規劃

文獻[2]敘述了動態規劃算法,作為引理復述如下:

引理1令EC(X)表示故障分布X的測試費用的期望最小值,并選取下一步測試ti,EC(X)的遞歸表達式如下:

上述遞歸表達式導出一個動態規劃算法,但當問題規模大時,計算效率較低。

3.2貪婪算法

以信息熵作為下一步測試選擇的依據,是貪婪算法的出發點[5]。

在當前已測試的所有結果的條件下,令X為當前故障分布。選取下一步測試為ti,使得每比特的費用ci/H(Ti)最小。

由于X可以完全確定Ti,從信息熵的性質可以得出:

(3)

(3)式左邊為測試導致的信息熵的減少量。所以上述貪婪算法的直觀意義為選取一個測試,使得其導致的信息熵減少量的每比特費用最小。下面給出上述貪婪算法得到的測試費用期望值的一個上界。

定理1令X為故障分布,取值范圍為1～N；EGC(X)為上述貪婪算法得到的測試費用的期望值，則有:

h=maxQmini[ci/H(Ti|Q)]，

l=minQmini[ci/H(Ti|Q)]

(4)

其中,Q為某可能的測試結果集;i、Q遍歷所有使得H(Ti|Q)≠0的組合。

證明使用歸納法。假定在貪婪算法的計算中,下一步選取的是測試ti,且假設對于取值范圍小于N的分布,上述定理已成立。

p(Ti=1)hH(X|Ti=1),

同理有:

且H(X)=0時定理1顯然成立,于是由定理1中h和l的表達式知定理1成立。

定理1給出了貪婪算法得到結果的一個估計,對其上界的估計表明在一般情況下,貪婪算法的效果不會太差,尤其當使用某些比較“均勻”的測試集ti,這里“均勻”是指不論對于什么樣的已測試結果Q，mini(ci/H(Ti|Q)都不會太大。

3.3哈夫曼算法及期望值估計

考慮所有測試費用均相等的情形。不失一般性,假定測試費用均為1,此時測試費用的期望值即為總的測試次數的期望值。

如文獻[8]所述,對于一個離散隨機變量X,可以得到其對應的二元哈夫曼樹,樹的葉節點為X的可能取值,每個分支節點對應了一個二元分割。整個哈夫曼樹等價于用一系列二元問題來確定X值的過程。令EL(X)為其所需提問的次數的期望值。文獻[7]證明了哈夫曼算法的最優性,即此時EL(X)是最小的,且

(5)

問題在于,必須用一系列測試來決定究竟發生的是哪個故障,從這些測試得到的問題都形如Ti=1,而從哈夫曼算法得出的二元問題集未必都具有此形式。

下文描述一大類測試集,其在某種意義上與哈夫曼算法是“相容”的,即可以從哈夫曼算法給出需要的測試序列決策樹,該類測試集導出的決策序列能達到理論上的最優,即測試次數的期望值的最小值與哈夫曼算法給出的值是一致的。

定義3稱一個測試集t1,t2,…,tM是“可分割”的,如果存在故障序列的一個排序s1,s2,…,sN,使得對于每個故障sk,都有一個測試ti,使得ti通過即等價于發生的故障s1,s2,…,sN的下標大于等于k。 通俗地說,此時可以給故障序列一個適當的排序,使得對每個二元問題“故障下標大于等于k”,都對應有一個測試ti,且問題“Ti=1”等價于“故障下標大于等于k”。

定理2當測試集是可分割的,那么哈夫曼算法提供的下界是可達的,即此時可以給出一個故障診斷策略樹,其測試次數的期望值等于哈夫曼算法得到的期望值EL(X)。

證明文獻[7]中指出,通過重新安排哈夫曼算法得到的葉節點,總可以使得分支節點的問題等價于一個分割“Xk”。也即,存在一個二元問題的決策樹,其每個問題都等價于一個分割 “故障下標大于等于k”,且其測試次數的期望值等于哈夫曼算法的期望值EL(X)。

再由測試集可分割的定義,對于每個問題“故障下標大于等于k”都對應一個測試ti,且問題“Ti=1”等價于“故障下標大于等于k”。

于是,只需測試集是可分割的,那么上述通過哈夫曼算法得到的二元問題的決策樹的每個分支節點的問題都等價于“ti=1”,即此時這個二元決策樹的每個節點的選擇都是通過測試集中的某個測試通過與否來決定的,所以這樣的一個二元決策樹是一個故障診斷策略樹,且其測試次數的期望值等于EL(X)。

4結束語

本文討論了故障診斷策略樹的3種算法。動態規劃算法需要列舉大量的可能結果,復雜度高,適用于小規模的問題。貪婪算法基于每比特信息熵減少量的費用來判斷下一步的行動,減少了大量的不必要計算,本文中提供的上界表明在一般情況下,其效果不會太差,該算法的上下界有待進一步改進。在測試費用相等的情況下且測試集可分割的情形下,可以使用哈夫曼算法來得到一個嚴格最優解。什么樣的測試集可以在多項式時間內給出一個嚴格最優解,有待進一步研究。

[參考文獻]

[1]中國北車長客股份公司.動車組數據監控與分析平臺使用手冊[Z].長春：中國北車長客股份公司，2014:1-33.

[2]Kuznetzov P I, Pchlintzev L A. The application of some mathematical methods in medical diagnostics[J].Math Biosci,1969, 5:365-377.

[3]戴茂方,趙韓,方艮海,等.客車前橋計算機輔助故障樹分析[J].合肥工業大學學報;自然科學版, 2003,26(5):971-974.

[4]林巨廣,嚴軍富,關鵬. 基于熵權法和灰色關聯度分析的軸承故障診斷[J].合肥工業大學學報:自然科學版, 2011, 34(11):1610-1614.

[5]景小寧,李全通,陳云翔,等.基于信息熵的最少測試費用故障診斷策略[J].計算機應用, 2005, 25(2):417-419.

[6]Hardy L M, Omberg E R.Using the Huffman code for sequential diagnosis[J]. IEEE Transactions on Systems，Man and Cybernetics,1971, 1(4):389-391.

[7]Cover T M,Thomas J A.Elements of information theory[M].2nd ed.Wiley-Blackwell, 2006:7-74.

[8]Huffman D A.A method for the construction of minimum-redundancy codes[J].Proc IRE, 1952, 40: 1098-1101.

(責任編輯張镅)

Cost estimation of testing by sequential fault detection strategy

ZHANG Hai-feng1,CHEN Jun-da2

(1.CNR Changchun Railway Vehicles Co., Ltd., Changchun 130062, China; 2.Shanghai Gener-Tech Co., Ltd., Shanghai 200072, China)

Abstract:In this paper, the algorithms of sequential fault detection strategy are described in order to minimize the expectation of testing cost. Firstly, three classical algorithms are described, especially the greedy algorithm and the information entropy. Secondly, the up bound and low bound of the expectation for the greedy algorithm are given based on the information entropy. Finally, the Huffman algorithm is applied to the problem and an expectation of testing cost is also given if the test set satisfies a certain condition and have identical cost.

Key words:information entropy; greedy algorithm; testing cost estimation

中圖分類號:U279.2

文獻標識碼：A

文章編號：1003-5060(2016)02-0280-03

Doi:10.3969/j.issn.1003-5060.2016.02.026

作者簡介：張海峰(1982-),男,吉林長春人，中國北車長春軌道客車股份有限公司工程師.

收稿日期：2015-09-08；修回日期：2015-12-20