劉建敏,劉遠宏,馮輔周,江鵬程

(裝甲兵工程學(xué)院機械工程系,北京 100072)

基于貪婪算法的測試優(yōu)化選擇

劉建敏,劉遠宏,馮輔周,江鵬程

(裝甲兵工程學(xué)院機械工程系,北京 100072)

針對傳統(tǒng)測試優(yōu)化選擇算法存在的通用性較差等問題,提出了基于貪婪算法的測試優(yōu)化選擇方法,分別應(yīng)用于面向故障檢測和故障隔離的測試優(yōu)化選擇。其基本思想是以測試數(shù)量最少為目標(biāo),先選擇必需的測試,即某一故障只能被單個測試檢測或隔離,然后采用貪婪式搜索逐步選擇最優(yōu)測試。通過二值和多值測試優(yōu)化選擇案例驗證了該算法的有效性,并從理論上分析了算法的時間復(fù)雜度。理論和案例分析結(jié)果表明,該算法能有效挖掘測試的故障檢測和隔離能力,且適用于隔離到更換單元和具體故障模式的二值和多值測試優(yōu)化選擇,時間復(fù)雜度較傳統(tǒng)算法明顯降低。

兵器科學(xué)與技術(shù)；測試優(yōu)化；貪婪算法；故障檢測；故障隔離

0 引言

現(xiàn)代裝備功能越來越先進,技術(shù)和結(jié)構(gòu)也變得越來越復(fù)雜,因此對測試和診斷提出了更高、更新、更嚴(yán)的要求,對其開展測試性設(shè)計已是當(dāng)務(wù)之急[1]。系統(tǒng)測試性方案優(yōu)化設(shè)計是測試性設(shè)計的重要組成部分。作為測試性方案的重要內(nèi)容之一,測試優(yōu)化選擇是測試性方案優(yōu)化工作的開始,關(guān)系到整個測試性設(shè)計工作的好壞。測試選擇的目的在于:在系統(tǒng)所有可能的測試配置中,尋找滿足系統(tǒng)測試性參數(shù)指標(biāo)要求的最佳測試組合。美國QSI公司依據(jù)多信號模型設(shè)計的TEAMS軟件和DSI公司提出的eXpress軟件可以依據(jù)測試集生成最優(yōu)診斷策略[2-3],也是優(yōu)化后的測試序列,然而其測試集優(yōu)化選擇過程是一循環(huán)往復(fù)過程,即依據(jù)建立的模型計算測試性指標(biāo),判斷是否滿足要求,從而確定是否再添加測試,并不能自動生成最優(yōu)測試集。從數(shù)學(xué)上講,測試選擇問題是一個組合優(yōu)化問題,現(xiàn)有測試選擇方法如各種遺傳算法、粒子群算法、布爾邏輯算法等[4-8],都取得了一定的效果。但遺傳算法、粒子群算法存在明顯的不收斂問題,布爾邏輯算法存在維數(shù)災(zāi)難問題。上述算法也只針對二值測試,即測試只有“通過”和“不通過”兩種,然而二值測試是一種簡化假設(shè),描述系統(tǒng)狀態(tài)信息很有限,實際中很多測試具有多值輸出,稱為多值測試。如液壓系統(tǒng)中的壓力,具有壓力偏高、壓力正常、壓力偏低3種狀態(tài),分別對應(yīng)系統(tǒng)不同狀態(tài),因此多值測試可以獲得更多系統(tǒng)信息,將系統(tǒng)測試都簡化為二值測試損失了大量信息,降低了診斷效率和診斷精度。多值測試大多基于整數(shù)編碼方法,因此其精度受制于整數(shù)編碼表,Yang等通過理論分析和統(tǒng)計實驗結(jié)果表明該技術(shù)隨著系統(tǒng)復(fù)雜程度的提高,測試與故障源數(shù)目的增加,集合規(guī)模增大,故障-測試相關(guān)性矩陣增大,其精度急劇下降[9]?，F(xiàn)有算法在進行測試優(yōu)化選擇時,直接隔離到了具體故障模式,而實際測試性設(shè)計時常只要求隔離到可更換單元(RU),現(xiàn)有隔離到具體故障模式的算法得到的優(yōu)化測試集測試數(shù)量仍偏多,不利于降低裝備全壽命周期費用。因此針對現(xiàn)有算法的不足,提出了一種新的貪婪式搜索算法,用于面向故障檢測和故障隔離的二值和多值測試優(yōu)化選擇。

1 測試優(yōu)化選擇問題

測試選擇是建立在故障-測試相關(guān)性矩陣的基礎(chǔ)上,假設(shè)系統(tǒng)共有m個故障狀態(tài)和n個測試,即系統(tǒng)故障集為S={s1,…,sm},si(1≤i≤m)表示系統(tǒng)不同故障狀態(tài),n維可測試集為{t1,t2,…,tn}.系統(tǒng)狀態(tài)-測試矩陣[dij],dij表示第j個測試對第i個故障的測試輸出取值,當(dāng)dij=0或1時,測試為二值測試,當(dāng)dij取多值時,為多值測試;故障-測試相關(guān)性矩陣如表1所示。

表1 測試系統(tǒng)相關(guān)性矩陣Tab.1 Dependency matrix of test system

現(xiàn)有的測試優(yōu)化選擇方法大都可以分為兩類:包含法和排除法。主要由測試評估標(biāo)準(zhǔn)和測試選擇策略兩因素構(gòu)成。測試評估標(biāo)準(zhǔn)從不同角度刻畫測試的故障檢測和隔離能力,沒有理論證據(jù)能證明某個標(biāo)準(zhǔn)相對于其他標(biāo)準(zhǔn)的優(yōu)越性,統(tǒng)計實驗也證明了這一點[10]。Prasad等總結(jié)了5條評估標(biāo)準(zhǔn)用于評估測試的故障隔離能力[11]。

標(biāo)準(zhǔn)1 測試含有的模糊組數(shù)最多為最好;

標(biāo)準(zhǔn)2 含有故障數(shù)最多的模糊組含有的故障數(shù)目在所有測試中最少;

標(biāo)準(zhǔn)3 考慮模糊組中故障的分布情況分布越均勻越好,其意義接近于信息熵;

標(biāo)準(zhǔn)4 隔離故障數(shù)目最多為最好;

標(biāo)準(zhǔn)5 用信息熵衡量的信息量,信息量越多越好。

2 測試優(yōu)化選擇問題的貪婪算法

貪婪算法分多個任務(wù)階段依次進行搜索,每一階段中尋求當(dāng)前情況下的局部最優(yōu)解,以迭代的方式做出相繼的貪婪選擇,每做一次選擇就將求解的問題轉(zhuǎn)化為更小規(guī)模的問題,最終得到整體最優(yōu)解或近似解。傳統(tǒng)貪婪算法多以信息量為基礎(chǔ)提出測試評價標(biāo)準(zhǔn),實際應(yīng)用中裝備故障率信息較難獲取,即便獲取的故障率數(shù)據(jù)多是經(jīng)驗數(shù)據(jù),準(zhǔn)確率也有待商榷,算法多適用于二值而非多值測試的優(yōu)化選擇,且無法進行隔離到RU的測試優(yōu)化計算。因此本文提出一種新的貪婪算法,在選擇測試時,以測試數(shù)量最少為目標(biāo),選擇檢測或隔離故障數(shù)目最多作為測試評估標(biāo)準(zhǔn)。

2.1 面向故障檢測的測試優(yōu)化選擇

故障檢測率實際上是指測試能檢測到的故障數(shù)與實際發(fā)生的故障總數(shù)之比,因此進行面向故障檢測的測試優(yōu)化選擇時,選擇故障檢測數(shù)目最多為最好作為評估標(biāo)準(zhǔn)。無論是二值或是多值測試,只要故障發(fā)生時,測試值異常,則表明該測試能檢測該故障。當(dāng)測試值較多時,故障與測試的對應(yīng)關(guān)系相比二值測試更為精確,測試能檢測的故障數(shù)彼此差異更明顯,一定程度上有利于測試優(yōu)化選擇。即以測試能檢測的故障數(shù)作為測試評價標(biāo)準(zhǔn)不僅適用于二值測試,也適用于多值測試。算法流程如下,其中NTi表示能檢測第i個故障的測試數(shù),I(tj)表示測試tj能檢測的故障數(shù)。

步驟1 初始化最小測試集TFDopt為空;

步驟2 將表中所有NTi=1的故障行所對應(yīng)的測試加入到TFDopt中。在故障-測試相關(guān)性表中將測試能檢測的故障行從表中刪除,然后再刪除這些測試,得到剩余故障-測試相關(guān)性表;

步驟3 如果剩余故障-測試相關(guān)性表中所有故障均能被檢測到(即剩余故障-測試相關(guān)性表為空),或沒有故障能繼續(xù)被檢測,則算法退出,否則進入步驟4;

步驟4 計算剩余故障-測試相關(guān)性表中所有測點的I(tj),將max(I(tj))所對應(yīng)的測試tj加入TFDopt中,然后從故障-測試相關(guān)性表中刪除tj能檢測到的故障,并刪除測試tj,得到剩余故障-測試相關(guān)性表,進入步驟3循環(huán)。

2.2 面向故障隔離的測試優(yōu)化選擇

2.2.1 隔離到故障模式的測試優(yōu)化選擇

步驟1 初始化最小測試集TFIopt為空

步驟2 將故障對布爾表中所有NTi=1的故障對所對應(yīng)的測試加入到TFIopt中。在故障對布爾表中將這些測試所對應(yīng)的列做或運算。根據(jù)運算結(jié)果,對應(yīng)為1的行(故障對)從表中刪除,然后再刪除這些測試,得到剩余故障對布爾表;

步驟3 如果剩余故障對布爾表中所有故障對均能被測試區(qū)分(即故障對布爾表為空),或沒有故障對繼續(xù)可以被區(qū)分(即剩余故障對的所有故障模式不能被隔離)。則算法退出,否則進入步驟4;

步驟4 計算剩余故障對布爾表中所有測試的I(tj)將max(I(tj))所對應(yīng)的測試tj加入TFIopt中,從故障對布爾表中刪除tj能隔離的故障對,并刪除該測試,得到剩余故障對布爾表,進入步驟3.

2.2.2 隔離到RU的測試優(yōu)化選擇

當(dāng)要求隔離到RU時,實際上考慮的是通過測試值差異將RU彼此能區(qū)分開來,即將RU的故障模式相互區(qū)分開來。由于只需要隔離到RU,RU內(nèi)部故障模式組成的故障對不必區(qū)分,因此刪除故障對布爾表中所屬同一個RU的故障對,組成新的故障對布爾表,依據(jù)隔離到故障模式的測試優(yōu)化選擇方法,得到優(yōu)化測試集和未被區(qū)分的故障對。

當(dāng)故障對不能被現(xiàn)有測試區(qū)分時,表明該故障對所屬RU對不能被區(qū)分,若該RU對中沒有其他故障模式,則算法結(jié)束,得到最優(yōu)測試集和不能被隔離的RU;反之若RU對中還有其他故障模式,則在原始故障-測試相關(guān)性矩陣中刪除RU對的所有故障模式行,重新編碼組成故障對布爾表進行測試優(yōu)化選擇,直到選出最優(yōu)測試集。

3 案例分析

實際測試優(yōu)化選擇時,為使測試能檢測和隔離系統(tǒng)故障狀態(tài)和正常狀態(tài),構(gòu)建系統(tǒng)故障-測試相關(guān)性表時,將系統(tǒng)正常狀態(tài)當(dāng)成是一種特殊的故障狀態(tài)。

3.1 二值測試優(yōu)化選擇

已知某系統(tǒng)由8個RU組成(U0表示系統(tǒng)正常),系統(tǒng)有10種故障狀態(tài)(包括系統(tǒng)正常狀態(tài))和7個測試,其中U1和U2各有兩種故障模式[6,12]。系統(tǒng)故障-測試相關(guān)性矩陣如表2所示,其中“1”表示該故障能被測試tj觀測,“0”表示不能被觀測。

表2 某系統(tǒng)的故障-二值測試相關(guān)性矩陣Tab.2 Fault binary test dependency matrix of a system

3.1.1 面向故障檢測的二值測試優(yōu)化選擇

表2中所有NT7=NT8=NT9=1,對應(yīng)的測試為t5、t6和t7,將這3個測試加入到TFDopt中,同時刪除其能檢測的故障模式和這3個測試,得到剩余故障-測試相關(guān)性表,由于剩余故障-測試相關(guān)性表為空,算法退出,得到的面向故障檢測的最小測試集為TFDopt={t5,t6,t7},故障檢測率為100%.

3.1.2 面向故障隔離的二值測試優(yōu)化選擇

1)隔離到故障模式的測試優(yōu)化選擇

對表2進行故障對編碼,獲得的故障對布爾表如表3所示。

表3 故障對布爾表Tab.3 Fault-pair Boolean table

表3中NTi=1對應(yīng)的測試為t1和t2,將t1和t2加入到TFIopt中,刪除表3中t1和t2能隔離的故障對及測試t1、t2,得到剩余故障對布爾表如表4所示。

表4中max(I(tj))=8,對應(yīng)的測試為t5,將t5加入到TFIopt,同時刪除表4中測試t5及其能隔離的故障對,得到剩余故障對布爾表,再將表中max(I(tj))對應(yīng)的測試加入到TFIopt中,同時刪除表中該測試能隔離的故障對及測試本身,得到新的剩余故障對布爾表,依次循環(huán)。最終得到的優(yōu)化測試集合為TFIopt={t1,t2,t5,t7,t3(t6)},剩余故障對布爾表為空,即故障隔離率為100%.

表4 剩余故障對布爾表Tab.4 Remaining fault-pair Boolean table

結(jié)合故障檢測的優(yōu)化測試集,最優(yōu)測試集為{t1,t2,t5,t7,t6},故障檢測率和隔離率均為100%. 2)隔離到RU的測試優(yōu)化選擇

將故障隔離到RU時,由于故障模式s1和s2,s3和s5屬同一RU,不需要被區(qū)分,因此將表3中故障對(s1,s2)和(s3,s5)刪除,剩下43個故障對,得到新的故障對布爾表中NTi=1對應(yīng)的測試為t1,將t1加入到TFIopt中,刪除表中t1能隔離的故障對及測試t1,得到剩余故障對布爾表如表5所示。表5中max(I(tj))=13,對應(yīng)的測試為t5,將t5加入到TFIopt,同時刪除表5中測試t5及其能隔離的故障對,得到剩余故障對布爾表中max(I(tj))對應(yīng)的測試為t7,刪除t7能隔離的故障對及測試t7,依次循環(huán),直到剩余故障對布爾表中沒有故障對能被區(qū)分。最終優(yōu)化測試集合TFIopt={t1,t5,t7,t3(t6)},最終的剩余故障對布爾表為空,所有故障對被區(qū)分,即通過優(yōu)化測試集{t1,t5,t7,t3(t6)}能將系統(tǒng)隔離到單個RU,故障隔離率為100%.

結(jié)合故障檢測的優(yōu)化測試集,最優(yōu)測試集為{t1,t5,t7,t6},故障檢測率和隔離率均為100%.

表5 剩余故障對布爾表Tab.5 Remaining fault-pair Boolean table

3.2 多值測試優(yōu)化選擇

已知某裝備系統(tǒng)由5個RU組成(U0表示系統(tǒng)正常),系統(tǒng)有8種故障狀態(tài)(包括系統(tǒng)正常狀態(tài))和5個測試,其中U2有兩種故障模式,U3有3種故障模式。系統(tǒng)的故障-測試相關(guān)性矩陣如表6所示,其中0表示測試輸出正常,+1表示測試輸出值偏大,-1表示測試輸出值偏小[13]。

3.2.1 面向故障檢測的多值測試優(yōu)化選擇

由表6可知,不存在NTi=1的行,max(I(tj))=8,對應(yīng)5個測試,即5個測試任選其一加入到TFDopt中,同時從表6中刪除該測試能檢測的故障模式和測試本身,得到的剩余故障-測試相關(guān)性表為空,算法退出,得到的面向故障檢測的最小測試集為5個測試任選其一,故障檢測率為100%.

表6 故障-多值測試相關(guān)性矩陣Tab.6 Faultmulti-valued test dependencymatrix

3.2.2 面向故障隔離的多值測試選擇

1)隔離到故障模式的測試優(yōu)化選擇

對表6進行故障對編碼,獲得的故障對布爾表如表7所示。表7中NT9=1,NT18=1,NT23=1和NT24=1,對應(yīng)的測試分別為t2、t3、t4、t5.這4個測試應(yīng)加入到TFIopt中。從表7中刪除這4個測試能隔離的故障對,再將測試t2、t3、t4、t5從表中刪除,得到故障對布爾表為空,即通過這4個測試就能將故障全部隔離,故障隔離率為100%.

表7 故障對布爾表Tab.7 Fault-pair Boolean table

結(jié)合故障檢測的優(yōu)化測試集,得到最優(yōu)測試集合為{t2,t3,t4,t5},故障檢測率和隔離率均為100%.

2)隔離到RU的測試優(yōu)化選擇

將故障隔離到RU時,由于故障模式s2和s3,s4、s5和s6分別屬于RU U2和U3,不需要被區(qū)分,因此將表3中故障對的(s2,s3)、(s4,s5)、(s4,s6)和(s5,s6)刪除,剩下25個故障對組成新的故障對布爾表如表8所示。表8中NT9=1,NT17=1和NT20=1,對應(yīng)的測試分別為t3、t4.將其加入到TFIopt中。從表8中刪除這兩個測試及其能隔離的故障對,得到剩余故障對布爾表中只剩故障對(s1,s7),可選測試為t1、t2或t5.最終得到隔離到RU的最優(yōu)測試集TFIopt={t3, t4,t1或t2或t5},即通過3個測試就能將故障全部隔離到RU,故障隔離率為100%.

表8 故障對布爾表Tab.8 Fault-pair Boolean table

結(jié)合故障檢測的優(yōu)化測試集,得到最優(yōu)測試集為{t3,t4,t1或t2或t5},故障檢測率和隔離率均為100%.

4 時間復(fù)雜度分析

4.1 面向故障檢測的算法時間復(fù)雜度

算法中故障行數(shù)為N,測試數(shù)為Nt,第2步計算次數(shù)為N,第4步計算次數(shù)為N×Nt,假設(shè)循環(huán)k次,則計算次數(shù)為O(Nt×N×k+N).由于在每次循環(huán)中,被檢測出的故障已經(jīng)被刪除,所以算法的實際復(fù)雜度小于O(Nt×N×k+N).顯然較基于布爾邏輯的測試優(yōu)化選擇算法的時間復(fù)雜度O(NNt)有較大的提升,且適用于二值和多值測試。

4.2 面向故障隔離的算法時間復(fù)雜度

5 結(jié)論

1)提出了面向故障檢測和隔離的測試優(yōu)化貪婪式搜索算法,通過二值和多值測試相關(guān)性矩陣進行了實例分析。分析結(jié)果表明該算法不僅適用于隔離到故障模式的二值和多值測試優(yōu)化選擇,同時適用于隔離到RU的二值和多值測試優(yōu)化選擇,適用范圍廣,通用性強。

2)提出的算法能有效挖掘每個測試的故障檢測和隔離能力,面向故障檢測的貪婪式搜索方法的時間復(fù)雜度遠低于基于布爾邏輯的測試優(yōu)化選擇算法,面向故障隔離的貪婪式搜索方法時間復(fù)雜度遠低于基于整數(shù)編碼技術(shù)的窮舉算法;在系統(tǒng)給定測試條件下,可快速計算出系統(tǒng)可達到的故障檢測率和故障隔離率指標(biāo)及最小測試集合。

3)實際工程應(yīng)用中,可以先通過矩陣分析剔除冗余測試(列矢量相同的測試)、合并模糊組(行矢量相同的故障,在給定測試下不可隔離),以降低矩陣維數(shù),從而進一步減少計算量。

References)

[1] 韓慶田,盧洪義,楊興根.軍用裝備測試性發(fā)展趨勢分析[J].儀器儀表學(xué)報,2006,27(6):352-354.

HAN Qing-tian,LU Hong-yi,YANG Xing-gen.Development trend analysis of testability technologies for military equipment [J].Chinese Journal of Scientific Instrument,2006,27(6): 352-354.(in Chinese)

[2] Pattipati K R,Raghavan V,ShakeriM,et al.TEAMS:testabilityengineering and maintenance system[C]∥American Control Conference.Baltimore,MD,US:IEEE,1994:1989-1995.

[3] Eric Gould.Modeling it both ways:hybrid diagnostic modeling and its application to hierarchical system designs[C]∥AUTOTESTCON 2004.San Antonio,TX,US:IEEE,2004:576-582.

[4] 楊鵬,邱靜,劉冠軍,等.基于布爾邏輯的測試選擇算法[J].測試技術(shù)學(xué)報,2007,21(5):386-390.

YANG Peng,QIU Jing,LIU Guan-jun,et al.The test selection algorithms based on Boolean logic[J].Journal of Test and Measurement Technology,2007,21(5):386-390.(in Chinese)

[5] Jing Qiu,Xiaodong Tan,Guanjun Liu,et al.Test selection and optimization for PHM based on failure evolution mechanism model [J].Journal of Systems Engineering and Electronics,2013,24(5): 780-792.

[6] 吳濤,葉曉慧,王紅霞,等.基于量子遺傳算法測試選擇問題的研究[J].計算機測量與控制,2010,18(11):2508-2510.

WU Tao,YE Xiao-hui,WANG Hong-xia,et al.Research on problem of test selection based on quantum genetic algorithm[J]. Computer Measurement&Control,2010,18(11):2508-2510. (in Chinese)

[7] 冉紅亮,張琦,朱春生.基于自適應(yīng)遺傳算法的工程裝備液壓系統(tǒng)測試選擇研究[J].機械制造與研究,2010,39(6):79-81.

RAN Hong-liang,ZHANG Qi,ZHU Chun-sheng.Research on engineering equipment hydraulic system test selection based on adaptive genetic algorithm[J].Machine Building&Automation, 2010,39(6):79-81.(in Chinese)

[8] 陳希祥,邱靜,劉冠軍.基于混合二進制粒子群-遺傳算法的測試優(yōu)化選擇研究[J].儀器儀表學(xué)報,2009,30(8):1674-1680.

CHEN Xi-xiang,QIU Jing,LIU Guan-jun.Optimal test selection based on hybrid BPSO and GA[J].Chinese Journal of Scientific Instrument,2009,30(8):1674-1680.(in Chinese)

[9] Yang C L,Tian SL,Long B,et al.A novel test points selection method for analog fault dictionary techniques[J].JElectron Test, 2010,26(5):523-534.

[10] Yang C L,Tian S L,Long B.Test points selection for analog fault dictionary techniques[J].JElectron Test,2009,25(2/ 3):157-168.

[11] Prasad V C,Babu N SC.Selection of test nodes for analog fault diagnosis in dictionary approach[J].IEEE Transactions on Instrumentation and Measurement,2000,49(6):1289-1297.

[12] Simpson W R,Sheppard JW.System test and diagnosis[M]. Boston:Kluwer Academic Publishers,1994.

[13] Rudov-Clark SD,Ryan A J,Stecki CM,et al.Automated design and optimization of sensor sets for condition-basedmonitoring [C]∥AIAC-13 Thirteenth Australian International Aerospace Congress.Melbourne,Australia:Defence Science and Technology Organisation,2010.

The Optim ization Selection of Tests Based on Greedy Algorithm

LIU Jian-min,LIU Yuan-hong,FENG Fu-zhou,JIANG Peng-cheng
(Department of Mechanical Engineering,Academy of Armored Force Engineering,Beijing 100072,China)

A novel test selection method is proposed based on greedy algorithm,which is used for fault detection and isolation,to overcome the shortcomings of the traditional test optimization algorithms,such as poor universality.The method is used to select the required test with aim of the minimal number of tests.Then the optimal test is selected gradually by greedy search.Finally,the validity of the proposed method is verified by using the binary-value and multi-value test optimization cases.Theoretical and case studies show that the proposed method is not only effective to excavate the fault detection and isolation ability of tests with low time complexity,but also applicable to the binary-value and multi-value test optimization of isolating the fauts to replaceable unit and specific failuremode.

ordnance science and technology;test optimization;greedy algorithm;fault detection;fault isolation

TP306+.3

A

1000-1093(2014)12-2109-07

10.3969/j.issn.1000-1093.2014.12.026

2014-03-13

總裝備部科技創(chuàng)新工程項目(ZYX1206006)

劉建敏(1963—),教授,博士生導(dǎo)師。E-mail:qingyun1032012@sina.com