顺序故障诊断策略的测试费用期望值估计

张海峰,　陈君达

(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