張海峰,　陳君達(dá)

(1.中國(guó)北車長(zhǎng)春軌道客車股份有限公司,吉林 長(zhǎng)春　130062; 2.上海杰之能信息科技有限公司,上?！?00072)

?

順序故障診斷策略的測(cè)試費(fèi)用期望值估計(jì)

張海峰1,陳君達(dá)2

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

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

關(guān)鍵詞:信息熵;貪婪算法;測(cè)試費(fèi)用估計(jì)

0引言

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

文獻(xiàn)[2]闡述了順序診斷的動(dòng)態(tài)規(guī)劃算法,且給出了測(cè)試費(fèi)用的期望值估計(jì);文獻(xiàn)[3]給出了一種計(jì)算機(jī)輔助故障樹(shù)分析方法;文獻(xiàn)[4]給出了基于熵權(quán)法的故障診斷方法;文獻(xiàn)[5]介紹了一個(gè)基于信息熵的貪婪算法,本文進(jìn)一步討論其性能,給出其測(cè)試費(fèi)用期望值的一個(gè)上下界；文獻(xiàn)[6]敘述了Huffman算法在順序故障診斷策略中的應(yīng)用,對(duì)于特殊的測(cè)試集可以達(dá)到最優(yōu)解,但是沒(méi)有給出對(duì)測(cè)試集的要求。本文給出一大類測(cè)試集,證明可以應(yīng)用Huffman算法對(duì)其構(gòu)造最優(yōu)解,并給出了測(cè)試費(fèi)用期望值的估計(jì)。

1問(wèn)題描述

設(shè)X為故障事件所對(duì)應(yīng)的隨機(jī)變量。假定系統(tǒng)有N種可能發(fā)生的故障,設(shè)為s1,s2,…,sN共N個(gè)可能發(fā)生的故障,默認(rèn)其滿足:

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

(2) 設(shè)ti(i=1,…，M)為M個(gè)二元測(cè)試集,即每個(gè)測(cè)試結(jié)果只有“通過(guò)”和“未通過(guò)”2種狀態(tài)。

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

(4) 測(cè)試矩陣D為一個(gè)0-1矩陣, 0表示當(dāng)故障為si時(shí),測(cè)試tj不通過(guò)；1表示故障為si時(shí),測(cè)試tj通過(guò)。

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

根據(jù)上述條件給出一個(gè)測(cè)試序列,使得測(cè)試費(fèi)用的期望值最小,為本文所研究的問(wèn)題。測(cè)試費(fèi)用期望值最小的測(cè)試序列的后一項(xiàng)可以隨著前若干項(xiàng)的測(cè)試結(jié)果而改變。比如有測(cè)試t1,t2,…,tM,一個(gè)可行的測(cè)試序列為:當(dāng)t1通過(guò)時(shí),下一步測(cè)試t2,否則下一步測(cè)試t3。當(dāng)之前的測(cè)試結(jié)果足以確定故障時(shí),停止測(cè)試。所以嚴(yán)格來(lái)說(shuō),需要一個(gè)測(cè)試序列的決策樹(shù),使得其測(cè)試費(fèi)用的期望值最小。

2概念及符號(hào)定義

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

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

(1)

信息熵的單位為bit。

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

(2)

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

直觀地說(shuō),條件熵代表當(dāng)Y確定后,X的熵的期望值。信息熵代表一個(gè)隨機(jī)變量的混亂程度,也代表為了“確定”該變量所要花費(fèi)的努力。問(wèn)題描述中的故障狀態(tài)和測(cè)試結(jié)果都是一個(gè)隨機(jī)變量,以X和Ti來(lái)表示。X代表究竟發(fā)生的是哪個(gè)故障,Ti代表測(cè)試ti的結(jié)果。下文將應(yīng)用這些隨機(jī)變量的信息熵。

3故障診斷策略算法

3.1動(dòng)態(tài)規(guī)劃

文獻(xiàn)[2]敘述了動(dòng)態(tài)規(guī)劃算法,作為引理復(fù)述如下:

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

上述遞歸表達(dá)式導(dǎo)出一個(gè)動(dòng)態(tài)規(guī)劃算法,但當(dāng)問(wèn)題規(guī)模大時(shí),計(jì)算效率較低。

3.2貪婪算法

以信息熵作為下一步測(cè)試選擇的依據(jù),是貪婪算法的出發(fā)點(diǎn)[5]。

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

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

(3)

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

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

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

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

(4)

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

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

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

同理有:

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

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

3.3哈夫曼算法及期望值估計(jì)

考慮所有測(cè)試費(fèi)用均相等的情形。不失一般性,假定測(cè)試費(fèi)用均為1,此時(shí)測(cè)試費(fèi)用的期望值即為總的測(cè)試次數(shù)的期望值。

如文獻(xiàn)[8]所述,對(duì)于一個(gè)離散隨機(jī)變量X,可以得到其對(duì)應(yīng)的二元哈夫曼樹(shù),樹(shù)的葉節(jié)點(diǎn)為X的可能取值,每個(gè)分支節(jié)點(diǎn)對(duì)應(yīng)了一個(gè)二元分割。整個(gè)哈夫曼樹(shù)等價(jià)于用一系列二元問(wèn)題來(lái)確定X值的過(guò)程。令EL(X)為其所需提問(wèn)的次數(shù)的期望值。文獻(xiàn)[7]證明了哈夫曼算法的最優(yōu)性,即此時(shí)EL(X)是最小的,且

(5)

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

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

定義3稱一個(gè)測(cè)試集t1,t2,…,tM是“可分割”的,如果存在故障序列的一個(gè)排序s1,s2,…,sN,使得對(duì)于每個(gè)故障sk,都有一個(gè)測(cè)試ti,使得ti通過(guò)即等價(jià)于發(fā)生的故障s1,s2,…,sN的下標(biāo)大于等于k。 通俗地說(shuō),此時(shí)可以給故障序列一個(gè)適當(dāng)?shù)呐判?使得對(duì)每個(gè)二元問(wèn)題“故障下標(biāo)大于等于k”,都對(duì)應(yīng)有一個(gè)測(cè)試ti,且問(wèn)題“Ti=1”等價(jià)于“故障下標(biāo)大于等于k”。

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

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

再由測(cè)試集可分割的定義,對(duì)于每個(gè)問(wèn)題“故障下標(biāo)大于等于k”都對(duì)應(yīng)一個(gè)測(cè)試ti,且問(wèn)題“Ti=1”等價(jià)于“故障下標(biāo)大于等于k”。

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

4結(jié)束語(yǔ)

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

[參考文獻(xiàn)]

[1]中國(guó)北車長(zhǎng)客股份公司.動(dòng)車組數(shù)據(jù)監(jiān)控與分析平臺(tái)使用手冊(cè)[Z].長(zhǎng)春：中國(guó)北車長(zhǎng)客股份公司，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ì)算機(jī)輔助故障樹(shù)分析[J].合肥工業(yè)大學(xué)學(xué)報(bào);自然科學(xué)版, 2003,26(5):971-974.

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

[5]景小寧,李全通,陳云翔,等.基于信息熵的最少測(cè)試費(fèi)用故障診斷策略[J].計(jì)算機(jī)應(yīng)用, 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.

(責(zé)任編輯張镅)

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

中圖分類號(hào):U279.2

文獻(xiàn)標(biāo)識(shí)碼：A

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

Doi:10.3969/j.issn.1003-5060.2016.02.026

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

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