張延生，喬中濤，井建輝

（軍械工程學(xué)院導(dǎo)彈工程系，石家莊 050003）

基于廣度優(yōu)先搜索算法的故障隔離矩陣生成方法

張延生，喬中濤，井建輝

（軍械工程學(xué)院導(dǎo)彈工程系，石家莊 050003）

相關(guān)性矩陣表示故障與測試之間的邏輯關(guān)系；隔離矩陣表示在給定的測試順序下，故障隔離與測試之間的需求關(guān)系；測試順序?qū)υ\斷費用影響可以通過隔離矩陣進行計算；所以求解隔離矩陣是診斷費用優(yōu)化的前提；針對相關(guān)性矩陣與隔離矩陣易于混淆的問題，以及傳統(tǒng)分析方法求解隔離的不足，詳述隔離矩陣的概念和生成原理，設(shè)計基于廣度優(yōu)先搜索的隔離矩陣生成算法；示例表明，生成算法是可行的和有效的。

測試性；隔離矩陣；廣度優(yōu)先搜索算法

0 引言

隨著測試診斷費用在武器裝備全壽命周期費用中所占比例不斷提高，測試性研究也越來越受到重視。測試性作為系統(tǒng)的重要設(shè)計特性之一，描述的是系統(tǒng)的故障檢測和隔離能力［1］。把故障定位到實施修理時可更換的單元的過程稱為故障隔離。故障診斷隔離費用與系統(tǒng)狀態(tài)概率、測試費用和測試順序密切相關(guān)。測試順序?qū)υ\斷費用的影響可用故障隔離矩陣表示。設(shè)系統(tǒng)故障隔離需要n個測試，對應(yīng)的測試順序有n！個。在系統(tǒng)狀態(tài)概率和測試費用確定后，診斷費用的優(yōu)化就是在n！個測試順序中尋找最優(yōu)的測試順序，使系統(tǒng)故障診斷隔離費用最低。一些文獻在計算最優(yōu)診斷費用時，用到隔離矩陣，但就隔離矩陣概念和生成方法沒有詳述［2-3］。有些文獻甚至將故障隔離矩陣與故障測試相關(guān)性矩陣混淆，錯誤地將相關(guān)性矩陣代替隔離矩陣進行優(yōu)化計算［4］。因此，準確地求解測試順序?qū)?yīng)的故障隔離矩陣就顯得十分必要。

1 故障測試相關(guān)性矩陣

建立故障與測試之間聯(lián)系是進行故障診斷的基礎(chǔ)。故障與測試之間的關(guān)系可用故障測試相關(guān)性矩陣D＝［dij］（m＋1）×n表示，如式（1）所示。其中，F(xiàn)0表示系統(tǒng)無故障狀態(tài)，F(xiàn)i（i＝1，2，…，m）表示系統(tǒng)的組成單元，tj（j＝1，2，…，n）表示測試。如果dij＝1表示Fi單元發(fā)生故障時，tj能夠測得，即Fi與tj相關(guān)；如果dij＝0表示Fi單元發(fā)生故障時，tj不能夠測得，即Fi與tj無關(guān)［1］。

圖1某雷達頻綜系統(tǒng)功能結(jié)構(gòu)圖

圖1 為某雷達頻綜系統(tǒng)的功能結(jié)構(gòu)圖，F(xiàn)1、F2、…、F9為組成單元，T1、T2、…、T9為測試。它的相關(guān)性矩陣如式（2）所示。其中，C＝［C1，C2，…，Cn］1×n為測試費用向量。測試Tj（j ＝1，2，…，n）的費用為Cj，包括了測試時間、測試硬件軟件消耗、測試人力消耗等費用。P＝［P0，P1，P2，…，Pm］1×（m＋1）為狀態(tài)概率向量。系統(tǒng)處于狀態(tài)Fi（i＝0，1，2，…，m）時，對應(yīng)的狀態(tài)概率為Pi，且滿足。

2 診斷推理與測試響應(yīng)矩陣

在相關(guān)性矩陣基礎(chǔ)上，可以進行故障診斷。診斷推理過程是在以下假設(shè)下進行：

1）當(dāng)系統(tǒng)發(fā)生故障時，認為只有一個單元發(fā)生故障；

2）測試結(jié)果準確可靠，測試結(jié)果只有通過和不通過兩種情況，分別用邏輯“0”和“1”表示，且任何兩個測試之間是相互獨立的。

設(shè)在測試順序T1、T2、…、Tn下，根據(jù)測試結(jié)果，得到測試響應(yīng)向量R＝［x1，x2，…，xn］，其中xi∈｛0，1｝且i＝1，2，…，n。在相關(guān)性矩陣基礎(chǔ)上，根據(jù)測試響應(yīng)向量R確定故障過程即為診斷推理過程。例如，如果響應(yīng)向量R1＝［0，1，X，X，X，X，X，X，X］，其中X表示0或1，它的取值不影響診斷推理的結(jié)果，診斷推理的過程可用圖2表示。當(dāng)T1＝0時，根據(jù)相關(guān)性矩陣D，系統(tǒng)狀態(tài)是模糊組［F0、F2、F3、F4、F5、F6、F7、F8、F9］；當(dāng)T2＝1時，由相關(guān)性矩陣D，可判斷是F2發(fā)生故障。系統(tǒng)的任何單元發(fā)生故障時，都會有相應(yīng)的測試響應(yīng)向量和診斷推理圖，將所有測試響應(yīng)向量放在一起就構(gòu)成了響應(yīng)矩陣，將所有診斷推理圖畫在一起就形成了診斷樹。本例中測試響應(yīng)矩陣和診斷樹分別如式（3）和圖3所示。

圖2 測試響應(yīng)R1診斷推理過程

圖3 測試順序T1、T2、…、Tn下的診斷樹

3 故障隔離矩陣

圖3診斷推理過程和式（3）響應(yīng)矩陣是在測試順序T1、T2、T3、T4、T5、T6、T7、T8、T9得到的。那么改變測試順序，診斷推理過程和響應(yīng)矩陣也將改變。仍以圖1為例，測試順序變?yōu)門8、T9、T7、T3、T4、T5、T6、T1，診斷推理過程則如圖4所示，響應(yīng)矩陣如式（4）所示。

圖4 測試順序T8、T9、T7、T3、T4、T5、T6、T1下的診斷樹

比較響應(yīng)矩陣式（3）和式（4）可知，在不同測試順序下，響應(yīng)矩陣是不同的。對于F0而言，在測試順序T1、T2、T3、T4、T5、T6、T7、T8、T9下，用到了所有的測試，才能確定是F0狀態(tài)；而在T8、T9、T7、T3、T4、T5、T6、T1下，只用到了T8、T9、T7三個測試，就可以確定。對于其他狀態(tài)也類似，即在不同測試順序下，確定系統(tǒng)狀態(tài)所使用的測試個數(shù)存在差異。確定狀態(tài)Fi（i＝0，1，2，…，m）時所需要測試可以用隔離向量Ii＝［bi1，bi2，…，bin］表示，其中bij∈｛0，1｝。bij＝1表示確定狀態(tài)Fi時，用到了測試Tj；bij＝0表示確定狀態(tài)Fi時，沒有用到測試Tj。例如，在測試T1、T2、T3、T4、T5、T6、T7、T8、T9下，T7的隔離向量為I7＝［111111101］，在T8、T9、T7、T3、T4、T5、T6、T1下，為I7＝ ［000100111］。

將所有狀態(tài)的隔離向量放在一起就構(gòu)成了隔離矩陣。系統(tǒng)的隔離矩陣用I＝［bij］（m＋1）×n表示，即式（5）所示。隔離矩陣物理意義表示在給定測試順序下進行故障診斷推理，故障隔離到各個單元時，所用的測試。

T1、T2、T3、T4、T5、T6、T7、T8、T9測試順序下的故障隔離矩陣I1如式（6）所示。

T8、T9、T7、T3、T4、T5、T6、T1測試順序下的故障隔離矩陣I2如式（7）所示。

4 故障隔離矩陣對診斷費用的影響

診斷費用是指在系統(tǒng)相關(guān)性矩陣和給定的測試順序下，確定系統(tǒng)狀態(tài)所需總的平均測試費用CZ。

其中：C＝［C1，C2，…，Cn］1×n為測試費用向量。P＝［P0，P1，P2，…，Pm］1×（m＋1）為狀態(tài)概率向量。I＝［bij］（m＋1）×n為故障隔離矩陣。

式（8）中，系統(tǒng)的狀態(tài)概率向量P通常是不變的；所選測試一旦確定以后，它的費用向量C也是不變的；而故障隔離矩陣I隨測試順序改變而改變，直接影響著測試費用CZ。例如在測試順序T1、T2、T3、T4、T5、T6、T7、T8、T9和T8、T9、T7、T3、T4、T5、T6、T1情況下總測試費用分別為CZ1和CZ2，如式（9）、（10）所示?？梢?，測試順序的不同，隔離矩陣也將不同，導(dǎo)致總測試費用也不同。為了尋找最低費用的測試順序，需要遍歷所有測試順序下故障隔離矩陣。依靠傳統(tǒng)的分析方法獲取隔離矩陣，既不現(xiàn)實也不可能，如何自動生成故障隔離矩陣就變得非常必要。

5 隔離矩陣生成原理

隔離矩陣求解過程，就是用測試T（1）、T（2）、…、T（n－1）、T（n）不斷對系統(tǒng)狀態(tài)F＝［F0，F(xiàn)1，F(xiàn)2，…，F(xiàn)m］分割的過程，每次分割都將產(chǎn)生新的模糊組，然后繼續(xù)用其它測試再對新的模糊組進行分割，分割的過程不斷循環(huán)，直至隔離到單個故障，或所有測試均用完為止［5］，記錄下分割標記，就可得到隔離矩陣。

設(shè)該系統(tǒng)的初始狀態(tài)為模糊組R0＝［F0，F(xiàn)1，F(xiàn)2，…，F(xiàn)m］。通過一組測試對模糊組R0逐漸分割，直到分割為單個狀態(tài)Fi（i＝0，1，2，…，m）。不妨用測試順序為T1，T2，…，Tn的測試進行分割，且模糊組R0經(jīng)過T1、T2、…、Tk－1分割后，當(dāng)前的模糊組為Rp，Rp＋1，…，Rp＋q，下一步要用Tk進行分割。根據(jù)相關(guān)性矩陣，與Tk相關(guān)的模糊組（Tk可以檢測到的故障）為：

與Tk無關(guān)的模糊組為：

當(dāng)用Tk對模糊組為Rp，Rp＋1，…，Rp＋q分割時，有兩種結(jié)果，一種是Tk通過，其邏輯值為“0”，說明與Tk無關(guān)的系統(tǒng)狀態(tài)被分割出；另一種結(jié)果是Tk沒通過，其邏輯值為“1”，說明與Tk相關(guān)的系統(tǒng)狀態(tài)被分割出。設(shè)對Rp分割出的模糊組為Rp＋q＋1和Rp＋q＋2，即：

當(dāng)前系統(tǒng)狀態(tài)模糊組Rp，Rp＋1，…，Rp＋q被Tk分割完成后，分割結(jié)果即系統(tǒng)的狀態(tài)模糊組為：Rp＋q＋1，Rp＋q＋2，…，Rp＋q＋（2q＋1），Rp＋q＋（2q＋2）。

在分割出的模糊組中，某個模糊組Rp＋q＋2i（1≤i≤q）可能存在以下幾種情況。

1）Rp＋q＋2i或Rp＋q＋（2i＋1）是已經(jīng)分割為單個狀態(tài)Fi（i＝0，1，2，…，m），該狀態(tài)Fi路徑到此為止；

2）Rp＋q＋2i＝?且Rp＋q＋（2i＋1）＝Rp＋q＋i，表明Tk沒有對父輩模糊組Rp＋q＋i進行分割；

3）Rp＋q＋2i或Rp＋q＋（2i＋1）仍然包含多個狀態(tài)，繼續(xù)用Tk＋1進行分割。

當(dāng)所有模糊組僅包含有一個狀態(tài)時，或者所有測試都已用完，則分割過程結(jié)束。此時，記錄下每個狀態(tài)所用到的測試，且該測試確實對狀態(tài)路徑中的模糊組進行了分割，即可得到該狀態(tài)的隔離向量。所有狀態(tài)的隔離向量即可構(gòu)成隔離矩陣。

6 隔離矩陣生成算法

依據(jù)隔離矩陣的生成原理，采用廣度優(yōu)先搜索算法［6］。首先把初始模糊組作為當(dāng)前狀態(tài)，調(diào)用分割子程序?qū)ζ溥M行分割，生成一組新的模糊組。按照廣度優(yōu)先搜索原則依次將這些狀態(tài)存入到OPEN表中。然后從OPEN表中取出下一狀態(tài)作為當(dāng)前狀態(tài)，繼續(xù)調(diào)用分割子程序，直到分割到單個單元，或所有測試已用完為止。

1）分割子程序：診斷樹生成過程也可以認為是用測試對模糊組不斷的分割過程，診斷樹枝上的每個節(jié)點就是一次分割。為了使診斷樹生成算法更加簡明，可將分割過程作為子程序嵌入到診斷樹生成算法。圖5為分割子程序的流程圖。

圖5 分割子程序

2）OPEN表及其指針：在隔離矩陣生成算法中，OPEN表采用5個屬性和兩個指針，如圖6所示。

屬性1：模糊組F，它的元素用非負整數(shù)0、1、2、3、…表示，且順序從小到大排列。

屬性2：模糊組對應(yīng)元素個數(shù)NF。

屬性3：下次分割該模糊組時，采用的測試。

屬性4：該模糊組父輩模糊組地址FA。

屬性5：該模糊組故障隔離標記。

AD指針：用于OPEN表地址計數(shù)，當(dāng)有新的模糊組產(chǎn)生時，AD指針加1，并在相應(yīng)的OPEN地址中存入F、NF、 PF、FA和FI，存放順序按照廣度優(yōu)先原則進行，即新狀態(tài)放入OPEN表尾部。

BD指針：用于依次從OPEN中取出F、NF、PF、FA 和FI，并判斷是否可以進行相關(guān)的分割操作。從OPEN表中取出一個狀態(tài)，則BD指針加1。

當(dāng)BD＝AD時，表示已經(jīng)將OPEN表1中模糊組已經(jīng)分割完畢，分割程序結(jié)束。

3）其它問題：

（1）當(dāng)前模糊組個數(shù)NF＝1時，表明該模糊組分割結(jié)束，記錄它的隔離向量。

（2）測試已用完，表示分割結(jié)束。

（3）當(dāng)所選測試未對該模糊組進行分割時，將該模糊組存入OPEN表尾部，繼續(xù)下一次測試分割。

（4）當(dāng)BD＝AD時，程序結(jié)束。

4）算法流程圖：

圖7為OPEN表的算法流程圖。

圖6 OPEN表及其指針

7 算例

某雷達電子系統(tǒng)共有18個單元，即F1、F2、…、F17、F18，設(shè)有6個檢測點，即T1、T2、T3、T4、T5、T6。它的相關(guān)矩陣如式（17）所示。

圖7 算法流程圖

根據(jù)隔離矩陣生成算法，求得在T1、T2、T3、T4、T5、T6測試順序下的隔離矩陣如式（18）所示。采用分析法求解該測試順序下隔離矩陣，與式（18）相同，驗證了隔離矩陣的求解算法是有效的。

8 結(jié)論

故障隔離矩陣與相關(guān)性矩陣既有聯(lián)系，又有區(qū)別。在相關(guān)性矩陣的基礎(chǔ)上進行故障診斷時，不同測試順序?qū)?yīng)著不同的故障隔離矩陣，不同測試順序也會產(chǎn)生不同測試費用。測試順序?qū)y試費用的影響是通過隔離矩陣來計算。測試順序優(yōu)化的前提是求解測試順序?qū)?yīng)的隔離矩陣?；趶V度優(yōu)先搜索的隔離矩陣生成算法實現(xiàn)了隔離矩陣自動生成，為測試順序優(yōu)化提供了基礎(chǔ)。

［1］石君友.測試性設(shè)計分析與驗證［M］.北京：國防工業(yè)出版社，2011.

［2］呂曉明，黃考利，連光耀.基于混沌粒子群優(yōu)化的系統(tǒng)級故障診斷策略優(yōu)化［J］.系統(tǒng)工程與電子技術(shù)，2010，32（1）：217-220.

［3］石 翌，胡 鷹，李俊杰，等.基于粒子群算法的診斷策略優(yōu)化技術(shù) ［J］.計算機測量與控制，2014，22（8）：2387-2390，2395.

［4］于勁松，張 帆，萬九卿.基于故障相關(guān)矩陣的最優(yōu)測試序列生成方法［J］.計算機測量與控制，2009，17（6）：1077 1079，1083.

［5］楊 鵬.基于相關(guān)性模型的診斷策略優(yōu)化設(shè)計技術(shù)［D］.長沙：國防科技大學(xué)，2008.

［6］王永慶.人工智能原理與方法［M］.西安：西安交通大學(xué)出版社，2006.

Generating Fault Isolation Matrix Based on Breadth First Search Algorithm

Zhang Yansheng，Qiao Zhongtao，Jing Jianhui

（Department of Missile Engineering，Ordnance Engineering College，Shijiazhuang 050003，China）

Dependency matrix describes the logical relationship between fault and test.isolation matrix describes demand relationship between fault isolation and test in a given test sequence.The effect of test sequence on diagnostic cost can be calculated by isolation matrix.So solving the isolation matrix is a basic condition for optimizing diagnostic cost.There are several problems of isolation matrix，such as easy to confuse with dependency matrix and difficult to solve with traditional analysis method.In this paper，the concept and generation principle of isolation matrix are detailed，and the generation algorithm based on the breadth first search is designed.At last，an example shows that the algorithm is feasible and effective.

test；isolation matrix；breadth first search algorithm

1671-4598（2016）08-0016-05

10.16526／j.cnki.11－4762／tp.2016.08.005

：TP206

：A

2016-02-12；

：2016-02-28。

張延生（1974-），男，河北武安人，博士，主要從事測試性與人工智能方向的研究。