基于DPSO-AO*算法系統(tǒng)測試序列優(yōu)化問題研究

王麗麗, 林 海2, 包 亮3, 萬 賀

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

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

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

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

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

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

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

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

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

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)表示完全故障模式；列向量分別表示針對系統(tǒng)的故障源設(shè)計的測試。本文的目的就是對這些測試項(xiàng)進(jìn)行優(yōu)化選擇，期望在系統(tǒng)發(fā)生故障時，以最少的測試項(xiàng)對系統(tǒng)故障進(jìn)行檢測和隔離，使產(chǎn)生的測試代價最小。

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個可用測試組成的集合，已知n=11。c=[c1,c2,…,cn]T表示測試費(fèi)用的向量[8]。

1.3 與或樹搜索算法及解樹的代價

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

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

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

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

(1)

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

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

(2)

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

(3)

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

③ 如果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)時的霍夫曼編碼，系統(tǒng)初始狀態(tài)的霍夫曼樹如圖3所示。

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

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

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

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

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

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

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

(4)

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

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

(5)

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

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

(6)

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

(7)

(8)

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

(9)

(10)

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

由式(6)計算各測試項(xiàng)的估價函數(shù)值，例如測試項(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)過計算，各個測試的估價函數(shù)值見表2第4列，由于整數(shù)位都是1，所以該列僅列出了h(s)的小數(shù)點(diǎn)后6位。

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

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

圖5 各個測試的估價函數(shù)值曲線

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

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

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

(11)

(12)

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

w值的大小決定粒子群算法的局部搜索能力；本文考慮到粒子的位置和速度優(yōu)勢與整個群體的優(yōu)勢，取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)是每個粒子的速度更新公式，粒子的位置更新見式(14)。

(14)

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

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

(15)

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

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

(16)

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

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

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

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

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

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

接下來對t1,t3,t5,t7擴(kuò)展即可，不需要對其他10個測試操作，從計算量來說，明顯縮減。

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

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

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

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

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

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

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

5 結(jié)論

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

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