王麗麗, 林 海2, 包 亮3, 萬(wàn) 賀

(1.北京交通大學(xué) 機(jī)械與電子控制工程學(xué)院，北京 100044；2.北京宇航系統(tǒng)工程研究所，北京 100076； 3.北京航天自動(dòng)控制研究所，北京 100854)

科技發(fā)展所帶來(lái)的電子系統(tǒng)的結(jié)構(gòu)和功能越來(lái)越復(fù)雜，特別是在航空航天和軍事等重要領(lǐng)域，對(duì)電子系統(tǒng)的測(cè)試效率和正確率要求非常嚴(yán)格。但是，普遍存在的測(cè)試手段是通過(guò)測(cè)試人員(受過(guò)專業(yè)培訓(xùn))在經(jīng)驗(yàn)的基礎(chǔ)上分析、診斷；因測(cè)試人員的不同造成測(cè)試結(jié)果的不穩(wěn)定性很高，并且受人本身能力的限制，測(cè)試效率也不高。為解決以上問(wèn)題，系統(tǒng)首先需要解決測(cè)試序列優(yōu)化的問(wèn)題，目前國(guó)內(nèi)外已經(jīng)提出了一系列相關(guān)技術(shù)，主要分為三類，分別為：基于圖論的方法、基于搜索的方法和其他方法[1]。針對(duì)實(shí)現(xiàn)測(cè)試策略生成的問(wèn)題，目前已經(jīng)有很多種方法,包括遺傳算法、差分進(jìn)化、量子遺傳算法、BP神經(jīng)網(wǎng)絡(luò)、模擬退火算法，以及對(duì)于這些算法的融合算法[2-4]。

由于AO*算法在研究測(cè)試序列問(wèn)題上應(yīng)用的比較多,但是AO*算法在搜索最優(yōu)路徑的過(guò)程中需要對(duì)每個(gè)測(cè)試進(jìn)行擴(kuò)展，這對(duì)于復(fù)雜的信息系統(tǒng)而言，計(jì)算量太大[5-6]。為了改進(jìn)該算法，采用離散粒子群算法，對(duì)每次需要擴(kuò)展的測(cè)試集進(jìn)行優(yōu)化選擇，然后AO*算法只對(duì)優(yōu)化的結(jié)果進(jìn)行擴(kuò)展，這樣的處理使得整個(gè)過(guò)程的計(jì)算量大大減少，搜尋最優(yōu)路徑的時(shí)間也大大縮短。

1 測(cè)試序列優(yōu)化問(wèn)題的數(shù)學(xué)模型

1.1 系統(tǒng)的多信號(hào)流圖模型和相關(guān)矩陣

建立了復(fù)雜裝備信息處理系統(tǒng)，在此基礎(chǔ)之上，計(jì)算了該系統(tǒng)的故障測(cè)試相關(guān)矩陣，然后基于系統(tǒng)的相關(guān)矩陣進(jìn)行測(cè)試優(yōu)化選擇問(wèn)題研究[7]。建立的復(fù)雜裝備信息處理系統(tǒng)的多信號(hào)流圖模型如圖1所示。

圖1 復(fù)雜裝備信息處理系統(tǒng)多信號(hào)流圖模型

如圖2給出了計(jì)算系統(tǒng)相關(guān)矩陣的方法，得到系統(tǒng)的故障-測(cè)試相關(guān)矩陣如表1所示。

圖2 系統(tǒng)相關(guān)矩陣的計(jì)算流程圖

CTt1t2t3t4t5t6t7t8t9t10t11C1(F)10000000000C2(F)01000000000C3(F)00100000000C4(F)00010000000C5(G)00001000000C6(G)00000100000C7(F)00000010000C8(F)00000001000C9(F)00000000100C10(F)00000000110C11(F)00000001001C12(G)01011111000

表1中行向量表示信息處流系統(tǒng)中可能發(fā)生的故障，C(F)表示功能故障模式，C(G)表示完全故障模式；列向量分別表示針對(duì)系統(tǒng)的故障源設(shè)計(jì)的測(cè)試。本文的目的就是對(duì)這些測(cè)試項(xiàng)進(jìn)行優(yōu)化選擇，期望在系統(tǒng)發(fā)生故障時(shí)，以最少的測(cè)試項(xiàng)對(duì)系統(tǒng)故障進(jìn)行檢測(cè)和隔離，使產(chǎn)生的測(cè)試代價(jià)最小。

1.2 數(shù)學(xué)描述

p=[999640,28,7,31,27,8,9,127,31,26,29,27,10]T×10-6

四元組參數(shù)中T={t1,t2,…，tn}是n個(gè)可用測(cè)試組成的集合，已知n=11。c=[c1,c2,…,cn]T表示測(cè)試費(fèi)用的向量[8]。

1.3 與或樹搜索算法及解樹的代價(jià)

與或樹能將搜索路徑清晰地展示出來(lái)，構(gòu)造與或樹的過(guò)程就相當(dāng)于將問(wèn)題一步一步分解，直到分解成不能再分解的子問(wèn)題。這種方式會(huì)搜索所有的路徑然后去判斷每個(gè)路徑的好壞，所以對(duì)于復(fù)雜的信息處理系統(tǒng)而言，這種方法代價(jià)會(huì)很高，不適合采取[9]。

本文將利用AO*算法，由于該系統(tǒng)相關(guān)的系統(tǒng)參數(shù)引導(dǎo)，使進(jìn)行的每一步搜索均為最佳路徑，避免了一次性搜索所有路徑從而求得最佳路徑,搜索效率明顯高出很多。

① 如果xi是“或節(jié)點(diǎn)”，它的子節(jié)點(diǎn)有(xj1,xj2,…,xjx)，則xi的代價(jià)計(jì)算公式如下：

h(xi)=min{c(xi,xj)+h(xjx)}

(1)

在這里取子集的最小代價(jià)值，當(dāng)搜索最優(yōu)路徑的時(shí)候，只需要代價(jià)值最小的節(jié)點(diǎn)。

② 如果xi是“與節(jié)點(diǎn)”，則xi的代價(jià)分為和代價(jià)法與最大代價(jià)法,如式(2)、式(3)所示。

(2)

h(xi)=max{c(xi,xjx)+h(xjx)}

(3)

由于本文中總代價(jià)等于每個(gè)故障源測(cè)試代價(jià)的總和，故采用式(2)帶入計(jì)算。

③ 如果xi是決策樹最低端的節(jié)點(diǎn)(已被隔離)，那么h(xi)=0。

④ 如果xi不可擴(kuò)展，而且不是終端節(jié)點(diǎn)，則h(xi)=∞。

2 選擇系統(tǒng)擴(kuò)展節(jié)點(diǎn)

此處介紹系統(tǒng)初始節(jié)點(diǎn)的擴(kuò)展原理，由前述數(shù)學(xué)模型中的S與p，得到系統(tǒng)在初始狀態(tài)時(shí)的霍夫曼編碼，系統(tǒng)初始狀態(tài)的霍夫曼樹如圖3所示。

圖3中，圓為系統(tǒng)的狀態(tài)，圓下面標(biāo)出的數(shù)字表示該狀態(tài)的p值。由圖3可計(jì)算出系統(tǒng)各狀態(tài)的霍夫曼編碼長(zhǎng)度為w*=[5,7,5,5,7,7,2,5,5,5,5,7]，再由表1中相關(guān)矩陣，對(duì)系統(tǒng)初始節(jié)點(diǎn)S={s1,s2,…,s12}進(jìn)行擴(kuò)展，根據(jù)11個(gè)測(cè)試得11個(gè)解,樹擴(kuò)展結(jié)果圖如圖4所示。

圖3 信息處理系統(tǒng)初始狀態(tài)對(duì)應(yīng)的霍夫曼樹

圖4 初始節(jié)點(diǎn)擴(kuò)展圖

圖4中，G為通過(guò)測(cè)試的信息處理系統(tǒng)狀態(tài)的集合；NG為沒(méi)有通過(guò)測(cè)試的信息處理系統(tǒng)狀態(tài)的集合[10]。

在初始故障狀態(tài)集S={s1,s2,…,s12}中進(jìn)行測(cè)試tj(1≤j≤11)后，容易知道d0j=0(j=1,2,…,11)[1]。

由式(1)可知其解樹的代價(jià)估計(jì)值如下：

h*(xi)=min{cj+h*(x,tj)}

(4)

式中，cj為測(cè)試tj的代價(jià);h*(x,tj)為應(yīng)用子節(jié)點(diǎn)tj對(duì)x進(jìn)行隔離的代價(jià)，由于x是tj的子節(jié)點(diǎn)，所以“與節(jié)點(diǎn)”(x,tj)的代價(jià)值是h*(x,tj)。因此根據(jù)式(2)可得：

h*(xi.tj)=p(xjp)h*(xjp)+p(xjf)h*(xjf)

(5)

式中，xjp為通過(guò)檢測(cè)的故障子集；xjf為沒(méi)有通過(guò)檢測(cè)的故障子集，而且xjp∪xjf=x(j=1,2,…,n)。結(jié)合式(4)和式(5)可得任意狀態(tài)集節(jié)點(diǎn)x的估價(jià)值如下[1]：

h*(x)=min{cj+p(xjp)h*(xjp)+p(xjf)h*(xjf)}

(6)

式中,h*(xjp)和h*(xjf)分別是節(jié)點(diǎn)xjp和xjf估價(jià)值的啟發(fā)函數(shù)[11]。由式(6)可以看出，在全部的擴(kuò)展子節(jié)點(diǎn)中，狀態(tài)集節(jié)點(diǎn)的估價(jià)值是最小的。式(6)中，p(xjp)和p(xjf)分別由式(7)和式(8)計(jì)算：

(7)

(8)

基于霍夫曼編碼理論的啟發(fā)函數(shù)在與或圖中的搜索效率效果良好[12]，由式(9)表示：

(9)

(10)

同理可計(jì)算出各節(jié)點(diǎn)xjp的啟發(fā)函數(shù)值，如表2第3列所示。

由式(6)計(jì)算各測(cè)試項(xiàng)的估價(jià)函數(shù)值，例如測(cè)試項(xiàng)t1的h(s)為：h(s)=c1+h(x1p)p(x1p)+h(x1f)p(x1f)=1+4.06×0.000332+5×0.000028=1.001487，經(jīng)過(guò)計(jì)算，各個(gè)測(cè)試的估價(jià)函數(shù)值見(jiàn)表2第4列，由于整數(shù)位都是1，所以該列僅列出了h(s)的小數(shù)點(diǎn)后6位。

表2 各節(jié)點(diǎn)計(jì)算結(jié)果一覽表

根據(jù)表2中第4列的真實(shí)值，將個(gè)測(cè)試的估價(jià)函數(shù)值繪制成曲線圖，如圖5所示。

圖5 各個(gè)測(cè)試的估價(jià)函數(shù)值曲線

由圖5可知，最小估價(jià)函數(shù)值屬于t6，所以搜索最佳路徑時(shí)，t6就是搜索首節(jié)點(diǎn)。然后再分別擴(kuò)展t6的兩個(gè)子集，繼續(xù)對(duì)最佳路徑的節(jié)點(diǎn)進(jìn)行搜索。

3 擴(kuò)展測(cè)試集的優(yōu)選

首先確定優(yōu)化完成后測(cè)試集中測(cè)試項(xiàng)的數(shù)目。然后再確定N個(gè)群落中的粒子數(shù)。第i個(gè)粒子的速度值和位置為：vi=(vi1,vi2,…,viD)和xi=(xi1,xi2,…,xiD)，i=1,2,…,N。群落中粒子的速度更新[1]和位置更新如下。

(11)

(12)

式中，w為慣性權(quán)重；c1為粒子的自我認(rèn)知程度；c2為粒子對(duì)整體的認(rèn)知程度；ξ、η為區(qū)間[0,1]內(nèi)的隨機(jī)數(shù)；r為速度的約束參數(shù)[1]。

w值的大小決定粒子群算法的局部搜索能力；本文考慮到粒子的位置和速度優(yōu)勢(shì)與整個(gè)群體的優(yōu)勢(shì)，取w=1,c1=2,c2=2[1]。

以上是傳統(tǒng)的做法，本文未使用式(12)，使用了離散粒子群算法算法，在該算法中，粒子的速度值介于[0,1]之間，在代碼中借助式(13)實(shí)現(xiàn)[0,1]的值域值：

s(v)=(1+ev)-1

(13)

式(13)是每個(gè)粒子的速度更新公式，粒子的位置更新見(jiàn)式(14)。

(14)

式中，rand為[0,1]區(qū)間的隨機(jī)數(shù)。

基于以上所述，本文設(shè)計(jì)了測(cè)試項(xiàng)評(píng)價(jià)函數(shù)見(jiàn)式(15)，可根據(jù)式(15)對(duì)測(cè)試項(xiàng)相對(duì)于各測(cè)試發(fā)生概率的重要性做出評(píng)估[1]。

(15)

式中，p(ti)為系統(tǒng)所有可能發(fā)生故障的平均概率；N(ti)為ti能夠檢測(cè)到的故障數(shù)；S(ti)為系統(tǒng)所有故障中故障的最小可測(cè)度；a為調(diào)節(jié)值，本文中取a=1。通過(guò)表1得到測(cè)試項(xiàng)的評(píng)價(jià)函數(shù)值如表2第5列、第6列、第7列、第8列所示。

由表2第5～8列數(shù)據(jù)，可以看到任意一個(gè)測(cè)試項(xiàng)的重要性。為評(píng)估測(cè)試集的優(yōu)劣，給出式(16)：

(16)

式中，Ts為隨機(jī)選擇的測(cè)試集；T為信息處理系統(tǒng)所有的測(cè)試項(xiàng)；N為Ts的數(shù)目；ηFD為系統(tǒng)的故障檢測(cè)率；ηFI為系統(tǒng)的故障隔離率；ci為測(cè)試ti的費(fèi)用；h(ti)為測(cè)試ti的評(píng)價(jià)函數(shù)值[13]。

結(jié)合本文研究的測(cè)試序列優(yōu)化問(wèn)題將離散粒子群算法的粒子定義為一個(gè)二進(jìn)制向量xi=(xi1,xi2,…,xiN)[1]，計(jì)算粒子在位置的速度值，位置更新按式(14)計(jì)算。

4 實(shí)驗(yàn)驗(yàn)證

本文通過(guò)編寫C++代碼，多次運(yùn)行算法程序，識(shí)別狀態(tài)集s6p的測(cè)試集，多次運(yùn)行算法的結(jié)果如圖6所示。

圖6 離散粒子群算法運(yùn)行結(jié)果

算法運(yùn)行結(jié)果中，位置若為1，則表示選中對(duì)應(yīng)的測(cè)試，若為0，則表示未選中對(duì)應(yīng)的測(cè)試。由圖6得，{t1,t3,t5,t7}為算法最后優(yōu)選出的測(cè)試集。

接下來(lái)對(duì)t1,t3,t5,t7擴(kuò)展即可，不需要對(duì)其他10個(gè)測(cè)試操作，從計(jì)算量來(lái)說(shuō)，明顯縮減。

表2第9列、第10列中，h(s6p,tj)為測(cè)試tj對(duì)s6p的估價(jià)值，δ為新的估價(jià)值與原來(lái)估價(jià)值的差值。圖7繪制了優(yōu)選測(cè)試的估價(jià)函數(shù)值曲線。

圖7 優(yōu)選測(cè)試的估價(jià)函數(shù)值曲線

由表2第9列和圖7得：最小的評(píng)估函數(shù)值是t1，所以t1就可以被當(dāng)做隔離出來(lái)最好的子集。類似地，擴(kuò)展s6f={t6,t12}，并用DPSO算法優(yōu)選出將要擴(kuò)展的系統(tǒng)測(cè)試項(xiàng)集合{t2,t4,t5,t7}(備選測(cè)試集不包括t1)，其中t1為測(cè)試代價(jià)最優(yōu)。接著擴(kuò)展t1的一個(gè)子集s1p={s2,s3,s4,s5,s7,s8,s9,s10,s11}，結(jié)果如圖8所示。

圖8 離散粒子群算法運(yùn)行結(jié)果

由圖8得：{t5,t7,t8}為優(yōu)選出的測(cè)試集，估價(jià)函數(shù)值最小的是t5。然后對(duì)s1f進(jìn)行擴(kuò)展，用DPSO算法選擇s1f將要擴(kuò)展的系統(tǒng)測(cè)試項(xiàng)集合，得到信息處理系統(tǒng)最優(yōu)測(cè)試策略決策樹如圖9所示。

圖9 信息處理系統(tǒng)最優(yōu)測(cè)試策略決策樹

基于以上整個(gè)過(guò)程，本文顯著減少了計(jì)算量，同時(shí)基于DPSO算法本身具有獨(dú)有的優(yōu)勢(shì)，系統(tǒng)每一次進(jìn)行的優(yōu)化選擇都是全局最優(yōu)。

5 結(jié)論

由圖9可得：該復(fù)雜信息處理系統(tǒng)所有的故障都能被獨(dú)立隔離。按照?qǐng)D9對(duì)故障進(jìn)行定位，可使故障源迅速確定，同時(shí)保證理論上總的測(cè)試代價(jià)最小。

當(dāng)系統(tǒng)同一時(shí)間只發(fā)生了一個(gè)故障，可由圖9中的測(cè)試順序，利用一次測(cè)試即可將故障源定位。若多個(gè)故障同時(shí)發(fā)生，或存在隱藏故障時(shí)，也可利用圖9進(jìn)行故障定位，只需進(jìn)行多次測(cè)試，將故障一一定位。