用于測試序列優(yōu)化的DPSO-WAO*算法研究

汪芊芊，林 臻，蘇 晗，王海濤，藍 鯤

(北京宇航系統(tǒng)工程研究所，北京 100076)

0 引言

由于測試項目對系統(tǒng)資源的占用，在對系統(tǒng)進行測試的過程中，所有的測試并不能同時進行，需對測試進行排序，而不同的測試執(zhí)行順序?qū)τ谙到y(tǒng)的測試效果和測試成本均會產(chǎn)生較大影響[1-3]。因此，在執(zhí)行測試前，需要對測試序列進行優(yōu)化設(shè)計，使其盡可能早并精確地隔離故障，同時降低測試代價(包括費用、故障隔離時間等綜合評價因素)，這正是測試策序列優(yōu)化設(shè)計問題。

針對該問題，國內(nèi)外學(xué)者提出了優(yōu)化算法。常用的方法有動態(tài)規(guī)劃(DP)算法[4-6]和啟發(fā)式算法[7-13]。動態(tài)規(guī)劃是自底向上構(gòu)造測試樹，具有指數(shù)級的計算量，無法應(yīng)用于復(fù)雜設(shè)備的測試序列優(yōu)化；啟發(fā)式算法是利用啟發(fā)式評估函數(shù)對測試成本進行評估，以評估結(jié)果進行測試點篩選的一類貪婪搜索算法，目前應(yīng)用最為廣泛的是由Krishna R.Pattipati以及其團隊提出的AO*(AND/OR*)算法[12]。但傳統(tǒng)AO*算法由于需要通過測試成本回溯實現(xiàn)全局最優(yōu)，導(dǎo)致節(jié)點擴展量巨大，當(dāng)測試個數(shù)增加時，易導(dǎo)致計算量爆炸。為此，國內(nèi)外學(xué)者提出了眾多改進方法，主要從兩方面考慮：(1)減少傳統(tǒng)AO*算法的擴展節(jié)點[14]；(2)結(jié)合現(xiàn)代優(yōu)化算法降低計算復(fù)雜度[15-20]。以上方法一定程度上降低了傳統(tǒng)AO*算法的計算復(fù)雜度，但未從全局的角度考慮各個測試項目的代價和故障概率對于測試選擇的影響，導(dǎo)致算法的優(yōu)化性能下降，難以達到最佳優(yōu)化效果。

針對傳統(tǒng)AO*算法計算量大，而現(xiàn)有對于AO*算法的改進無法同時滿足計算效率和優(yōu)化性能的問題，本文從啟發(fā)式評估函數(shù)的改進出發(fā)，設(shè)計了基于加權(quán)Huffman編碼的啟發(fā)式評估函數(shù)，對基于離散粒子群的AO*算法(DPSO-AO*)進行改進，提出了DPSO-WAO*(DPSO-Weight_AO*)算法。實例證明，基于加權(quán)Huffman編碼的啟發(fā)式評估函數(shù)較傳統(tǒng)AO*算法使用的啟發(fā)式評估函數(shù)更為準(zhǔn)確地評估了全局測試成本，在取消了成本回溯的情況下，算法計算復(fù)雜度與DPSO-AO*算法相當(dāng)，但算法尋優(yōu)性能較DPSO-AO*算法得到了較大提升，很好地解決了傳統(tǒng)AO*算法存在的計算效率和優(yōu)化性能的矛盾，適用于大型復(fù)雜對象的測試序列設(shè)計。

1 測試序列優(yōu)化問題分析與建模

對于被測系統(tǒng)來說，其系統(tǒng)狀態(tài)和測試信息可以定義為五元組(S，p，T，c，D)，式中：

S={s1，s2，…，sm}是系統(tǒng)故障狀態(tài)集合，si(1≤i≤m)表示系統(tǒng)不同的故障狀態(tài)，也即故障模式；

p=[p(s1)，p(s2)，…，p(sm)]T是系統(tǒng)各故障狀態(tài)S的故障率集合；

T={t1，t2，…，tn}是系統(tǒng)可選的測試集合；

c=[c1，c2，…，cn]T是各可行測試的測試成本集合，可以測試時長、人力成本或其它指標(biāo)評價。

Dm×n是測試與系統(tǒng)狀態(tài)的相關(guān)性矩陣。其基本形式為：

(1)

di，j表示故障fi與測試tj之間的相關(guān)性，若di，j=1，則表示測試tj可以檢測到故障狀態(tài)fi，若di，j=0，則表示測試tj無法檢測到故障狀態(tài)fi。

假定同一時刻只有一個故障狀態(tài)si發(fā)生，且每次只施加一個測試項目，則測試序列優(yōu)化就是設(shè)計一個方法，能夠通過合理安排測試項目的實施順序，來識別系統(tǒng)故障狀態(tài)集中的故障模式，且使期望的測試成本最小，測試成本通過如下公式評估：

(2)

式(2)中A(m+1)×n=[aij]是一個二值矩陣，如果在識別系統(tǒng)狀態(tài)si的過程中采用了測試tj，則aij=1；否則aij=0。如何能在滿足系統(tǒng)故障隔離率和故障檢測率要求的前提下，使式(2)中測試成本最小，是本文的研究目標(biāo)。

2 現(xiàn)有AO*算法及DPSO-AO*算法

AO*算法通過構(gòu)建與或圖采用top-down的搜索方法進行故障隔離，如圖1所示?；蚬?jié)點對應(yīng)故障集節(jié)點X；與節(jié)點對應(yīng)可用測試節(jié)點tj，其各子節(jié)點分別代表tj應(yīng)用于故障狀態(tài)集節(jié)點X后根據(jù)其測試結(jié)果和相關(guān)矩陣所得的通過故障子集Xjp和失敗故障子集Xjf。

AO*算法是兩個運算階段的反復(fù)：

1)自上而下進行節(jié)點擴展。從初始模擬故障集開始，評估所有可選測試用于隔離模糊故障集的測試代價，并選取代價最小的測試進行與或樹擴展，直至所有故障集節(jié)點均為單節(jié)點，則解樹生成，實現(xiàn)故障隔離的目的。

2)自下而上進行成本回溯。在與或樹擴展過程中，單純根據(jù)局部極值進行節(jié)點擴展，可能陷入局部最優(yōu)，因此，需要在每一次節(jié)點擴展后自下而上進行成本回溯，計算初始模擬故障集的測試成本，并與該次擴展前的成本評估值比較，若相等，則繼續(xù)擴展，否則，選取啟發(fā)式函數(shù)值次小的測試進行該節(jié)點的擴展，直至回溯成本與擴展前成本相同(若各可用測試所達到的成本回溯值均大于擴展前的評估值，則選取回溯成本最小的測試進行與或樹擴展)。

AO*算法利用Huffman編碼構(gòu)造啟發(fā)式評估函數(shù)。假設(shè)測試費用滿足：0≤c1≤…≤cn，構(gòu)造評估隔離故障集X的最小平均測試代價啟發(fā)式函數(shù)如式(3)所示：

(3)

若故障集X被測試tj區(qū)分為兩個故障子集Xjp和Xjf(Xjp∪Xjf=X)，其中Xjp表示測試tj無法檢測到的故障子集，Xjf表示測試tj可以檢測到的故障子集。利用測試點tj隔離故障集X的最小測試代價近似估計為：

hx=cj+p(xjp)×h(xjp)+p(xjf)×h(xjf)

(4)

其中：h(xjp)和h(xjf)分別表示估計隔離故障集Xjp和Xjf的最小測試代價，利用HEF(X)估計；p(xjp)和p(xjf)分別表示測試tj通過和失敗的相對概率。傳統(tǒng)AO*算法利用式(4)中hx的值評價測試點tj，選取hx最小的tj向下擴展。并在每次向下擴展之后將測試成本向上回溯，以確保當(dāng)前所擴展測試的全局最優(yōu)性。

傳統(tǒng)AO*算法通過不斷回溯以尋得最優(yōu)測試序列，對于運載火箭電氣系統(tǒng)、電氣設(shè)備這樣規(guī)模龐大的優(yōu)化對象，由于涉及的測試項目、故障模式均較多，因此所需運算時間急劇增加，很容易出現(xiàn)計算爆炸問題。為解決傳統(tǒng)AO*算法回溯次數(shù)多，計算量大的問題，文獻[18]將離散粒子群算法(DPSO)與AO*算法相結(jié)合，對AO*算法的可擴展節(jié)點進行篩選，并取消了成本回溯，大大減少了AO*算法的計算復(fù)雜度。

DPSO-AO*算法的基本思想是[18，20]：利用DPSO算法優(yōu)選AO*算法中每個待擴展節(jié)點的測試集，進而減少待擴展測試的個數(shù)，并取消成本回溯，降低算法計算復(fù)雜度。DPSO-AO*算法采用式(5)所示的適應(yīng)度函數(shù)對備選測試集T進行優(yōu)化：

(5)

其中：Ts代表所選的最優(yōu)測試集，N代表測試集Ts中測試項目的個數(shù)，ηFD、ηFI分別代表Ts的故障檢測率和故障隔離率；ci、cj分別代表測試ti、tj的測試代價；h(ti)代表測試集T的單個測試ti的優(yōu)劣程度，如式(6)所示：

(6)

式(6)中，P(ti)代表測試ti能檢測到的故障可能發(fā)生的總概率；S(ti)代表ti所能檢測到的故障的最小可測度，a為其系數(shù)，需根據(jù)實際優(yōu)化結(jié)果進行調(diào)整。

3 基于改進評估函數(shù)的DPSO-WAO*算法

3.1 基于加權(quán)Huffman編碼的啟發(fā)式評估函數(shù)

傳統(tǒng)AO*算法依據(jù)評估函數(shù)選擇最優(yōu)測試，實現(xiàn)故障樹的向下擴展，并結(jié)合向上回溯來保證測試選擇的正確性，其優(yōu)化性能主要取決于以下兩點。

1)啟發(fā)式評估函數(shù)對于故障集的測試代價描述的準(zhǔn)確性：

啟發(fā)式評估函數(shù)越接近真實的最小測試代價，則對于測試的選擇越準(zhǔn)確，越接近全局最優(yōu)。

2)回溯步數(shù)：

回溯的目的是檢驗當(dāng)前所選測試的全局最優(yōu)性，向上回溯步數(shù)越多，則越接近全局最優(yōu)，若每一次測試選擇都向頂端節(jié)點回溯，則所生成的測試序列一定為全局最優(yōu)。

傳統(tǒng)AO*算法利用向頂端節(jié)點回溯來確保算法的全局優(yōu)化性能，但回溯步數(shù)過多會導(dǎo)致擴展節(jié)點數(shù)目增多，因此計算量巨大，不適用于大規(guī)模系統(tǒng)的測試序列優(yōu)化。DPSO-AO*算法結(jié)合離散粒子群算法對傳統(tǒng)AO*算法進行改進，通過DPSO算法對擴展測試集進行優(yōu)選，并取消成本回溯來減少節(jié)點擴展數(shù)目，降低計算復(fù)雜度。DPSO-AO*算法所用的啟發(fā)式函數(shù)(3)主要通過故障集中各個故障狀態(tài)的平均Huffman編碼來確定所需測試數(shù)量，并按照測試成本由低到高的原則選取測試項目用于計算總測試成本。

在理論編碼中，Huffman樹(最優(yōu)二叉樹)具有帶權(quán)路徑長度最小(即成本最小)的特點，因此，可用于近似估計測試集的最小測試成本。但該方法忽略了每個故障狀態(tài)的Huffman編碼信息，而是求取各故障狀態(tài)的平均Huffman編碼用于評估最小測試代價。事實上，Huffman編碼越短的故障，對應(yīng)故障率越高，越應(yīng)該被提前隔離，而僅通過平均Huffman編碼，無法體現(xiàn)該原則。因此，本文在DPSO-AO*算法的基礎(chǔ)上，從啟發(fā)式評估函數(shù)的改進這一角度出發(fā)，構(gòu)建了基于加權(quán)Huffman編碼的啟發(fā)式函數(shù)，對DPSO-AO*算法進行改進。加權(quán)Huffman編碼的啟發(fā)式函數(shù)基本思想如下：

隔離系統(tǒng)各狀態(tài)的測試總代價是通過將隔離各個狀態(tài)的測試代價相疊加而得的，而各個狀態(tài)的測試代價為隔離該狀態(tài)所需的測試代價與該故障狀態(tài)的故障率的乘積。因此，在對某個模糊狀態(tài)集的測試代價進行評估時，分別考慮模糊集中的各個狀態(tài)，利用故障率作為故障模式Huffman編碼的權(quán)重，提出如下基于加權(quán)Huffman編碼的啟發(fā)式函數(shù)：

(7)

其中：測試費用滿足0≤c1≤…≤cn，ω(si)表示故障模糊集X中si的Huffman編碼長度。

1)優(yōu)先隔離故障率高的故障；

2)優(yōu)先選擇測試成本低的測試。

由測試成本定義式(2)可知，該值即為測試成本的下限值。

基于加權(quán)Huffman編碼的啟發(fā)式函數(shù)與傳統(tǒng)的啟發(fā)式函數(shù)的差別在于：傳統(tǒng)AO*算法利用模糊故障集的平均Huffman編碼來表征隔離故障集的平均最少測試步驟，而丟失了故障集中的隔離各個故障所需的最少測試步驟這一信息，未體現(xiàn)優(yōu)先隔離故障率高的故障的這一原則。而基于加權(quán)Huffman編碼的啟發(fā)式函數(shù)構(gòu)建了滿足最優(yōu)測試序列優(yōu)化原則的診斷樹，并準(zhǔn)確計算了該最優(yōu)診斷樹的測試代價。因此，利用基于加權(quán)Huffman編碼的啟發(fā)式函數(shù)評估測試代價更為準(zhǔn)確。

3.2 DPSO-WAO*算法實施步驟

基于DPSO-WAO*算法的測試序列優(yōu)化方法與傳統(tǒng)AO*算法基本相同，但由于啟發(fā)式函數(shù)的準(zhǔn)確性更高，因此取消了向上回溯這一步驟，流程如圖2所示。

圖2 基于DPSO-WAO*算法的測試序列優(yōu)化流程

具體流程如下：

1)建立一個僅由根節(jié)點(系統(tǒng)故障狀態(tài)集)構(gòu)成的有向圖。

2)對于模糊故障集 (初始值為系統(tǒng)故障狀態(tài)集)，利用DPSO算法對當(dāng)前可用測試集進行優(yōu)選；利用評估函數(shù)評估采用各優(yōu)選出的測試隔離當(dāng)前模糊故障集的測試代價，并選出測試代價最低的測試擴展有向圖，直到中僅含有一個元素。具體步驟如下：

①利用DPSO算法對當(dāng)前可用測試集進行篩選，獲得優(yōu)化的測試子集；

②在測試子集中，每個測試將模糊故障集(模糊故障集的初始值為)分為左右兩個子集和，由式(7)估計兩個子集的最優(yōu)隔離代價，由式(4)計算利用測試隔離模糊故障集的最小代價；

③找出測試子集中隔離模糊故障集所用代價最小的測試，利用該測試擴展有向圖，獲得左右兩個子集；

④分別以故障子集作為模糊故障集，重復(fù)2)進行有向圖的擴展，直至為單元素集合，此時，系統(tǒng)故障狀態(tài)集中各個狀態(tài)均能被區(qū)分。

4 實例校驗及算法對比

4.1 實例校驗

為驗證DPSO-WAO*算法的有效性，在matlab平臺上實現(xiàn)了DPSO-WAO*算法，并利用該算法對文獻[18]中的超外差接收器系統(tǒng)進行測試序列優(yōu)化工作，與文獻[18]提出的DPSO-AO*算法進行比對。

文獻[18]所給出的超外差接收器系統(tǒng)包括22個不同的系統(tǒng)狀態(tài)，各狀態(tài)發(fā)生概率不等；包括36種測試，各測試的成本相同，均設(shè)為1。

然而，在實際測試條件下，各個測試的成本并不完全相同，由測試難易程度、測試時間、測試人力成本、資金成本等影響因素決定，對最終的系統(tǒng)測試總成本產(chǎn)生較大的影響。因此，本文對文獻[18]中給出的超外差接收器系統(tǒng)的36個測試項目賦予測試成本屬性，形成超外差接收器測試成本集合cjsq，如式(8)所示，測試成本從2到67不等，數(shù)值越高代表測試成本越高。

cjsq=[10，25，2，7，10，10，30，29，30，50，50，

20，4，5，67，34，30，50，50，20，4，20，4，5，67，

20，4，5，67，29，30，50，50，45，5，67]T

(8)

假設(shè)該系統(tǒng)同一時刻只有一個故障發(fā)生，且同一時刻只進行一種測試。對于測試成本相同及測試成本不同的情況，在matlab平臺上分別利用傳統(tǒng)AO*算法、DPSO-AO*算法、DPSO-WAO*算法對式(8)描述的系統(tǒng)進行測試序列優(yōu)化。其中，DPSO的粒子數(shù)目取15，迭代次數(shù)取100時，優(yōu)化性能較好。通過3種不同優(yōu)化算法形成的優(yōu)化結(jié)果如表1及圖3、圖4所示，表1中的數(shù)據(jù)為對應(yīng)算法連續(xù)運行10次所得結(jié)果的平均值或標(biāo)準(zhǔn)差。

表1 各算法性能參數(shù)比較

圖3 測試序列優(yōu)化算法性能比對(測試成本相同)

圖4 測試序列優(yōu)化算法性能比對(測試成本不同)

分別比較了測試成本相同(均為1)和測試成本不同(各項目的測試成本設(shè)置參見式(8))兩種工況下，3種算法尋得的最小平均測試代價、測試代價標(biāo)準(zhǔn)差、平均允許運行時間及平均擴展節(jié)點數(shù)目。其中：

1)平均最小測試代價。代表算法優(yōu)化性能，該數(shù)值越小，則代表算法優(yōu)化得出的測試代價越小，優(yōu)化性能越好。

2)測試代價標(biāo)準(zhǔn)差。代表算法尋優(yōu)性能的穩(wěn)定性，該數(shù)值越小，代表各次優(yōu)化結(jié)果一致性好，算法運行穩(wěn)定可靠。

3)平均運行時間。代表算法計算效率，該數(shù)值越小，代表算法運行時間越少，計算效率越高。

4)平均擴展節(jié)點數(shù)目。代表算法計算復(fù)雜度，該數(shù)值越小，代表算法遍歷次數(shù)越少，算法復(fù)雜度越低。

從表1結(jié)果可以看出，DPSO-WAO*算法可有效尋得最小測試代價，算法性能穩(wěn)定，運算效率較高。

注:算法各性能參數(shù)均以連續(xù)運行10次所得結(jié)果取平均值。

4.2 算法比對

上文通過超外差接收器系統(tǒng)對DPSO-WAO*算法有效性進行了實例驗證，并與傳統(tǒng)AO*算法、文獻[18]提出的DPSO-AO*算法進行了性能比對，如表1及圖3、圖4所示，得到結(jié)論如下。

1)尋優(yōu)性能：

DPSO-WAO*算法的優(yōu)化性能稍差于傳統(tǒng)AO*算法，但二者優(yōu)化生成的測試序列的測試代價相差不超過3.9%，主要是由于傳統(tǒng)AO*算法通過不斷向上回溯找到全局最優(yōu)解，而DPSO-WAO*算法無回溯，得到的是近似全局最優(yōu)解，此結(jié)果與預(yù)期一致。

DPSO-WAO*算法與DPSO-AO*算法相比，生成的最小測試代價分別降低11.9%(測試代價相同)和10.1%(測試成本不同)，尋優(yōu)性能得到較大提升。由此證明，DPSO-WAO*算法同DPSO-AO*算法一樣，均取消了傳統(tǒng)AO*算法的回溯，但由于基于加權(quán)Huffman編碼的啟發(fā)式函數(shù)能更好的評估模糊故障集的隔離代價，使當(dāng)前測試節(jié)點的擴展路徑更接近全局最優(yōu)，因此，DPSO-WAO*算法優(yōu)化性能較DPSO-AO*算法可提升10%以上。

2)計算效率和復(fù)雜度：

DPSO-WAO*算法的平均運行時間與DPSO-AO*算法的平均運行時間相當(dāng)，且均遠小于傳統(tǒng)AO*算法，僅為傳統(tǒng)算法所需時間的約15%，其擴展節(jié)點數(shù)目也約為傳統(tǒng)AO*算法的15%?？梢宰C明，DPSO-WAO*算法在進行測試節(jié)點擴展前利用DPSO對當(dāng)前可用測試集進行優(yōu)選，避免陷入局部最優(yōu)，并大大減少了擴展節(jié)點的數(shù)目，提高了算法的計算效率，且越復(fù)雜的系統(tǒng)，采用DPSO-WAO*算法獲得的計算效率提升效果也越明顯。

5 測試序列優(yōu)化方法在運載火箭電子設(shè)備中的應(yīng)用模式思考

運載火箭電氣系統(tǒng)組成復(fù)雜，故障模式在數(shù)量和種類上呈現(xiàn)多樣性，需采取較多測試才能實現(xiàn)故障檢測及隔離需求，如果不對測試進行統(tǒng)籌規(guī)劃，將會耗費大量的時間和成本代價。現(xiàn)階段運載火箭電子設(shè)備的測試包括單機測試、系統(tǒng)綜合測試、全箭電氣測試等多個環(huán)節(jié)，各測試環(huán)節(jié)主要關(guān)注測試覆蓋性，及測試項目的設(shè)置需盡可能覆蓋產(chǎn)品的功能、性能、冗余設(shè)計和對外接口等，測試項目的設(shè)置和排序主要依賴測試人員經(jīng)驗，未考慮測試對故障的隔離定位能力、測試成本等影響因素。

隨著新型火箭的研制，傳統(tǒng)火箭測試設(shè)計思路已很難適應(yīng)新型火箭的測試需求，尤其是隨著智慧火箭、可回收火箭等新概念的提出，傳統(tǒng)依靠人工經(jīng)驗通過斷插頭、串轉(zhuǎn)接盒等測試、排故模式已經(jīng)無法適應(yīng)火箭的測試排故需求，新型火箭的測試項目和測試序列的設(shè)計逐步向如下趨勢發(fā)展：

1)從地面ATE測試、人工測試模式轉(zhuǎn)向箭上BIT測試模式；

2)測試項目的選擇和排序從依據(jù)人員經(jīng)驗和定性原則轉(zhuǎn)向依據(jù)定量優(yōu)化方法。

對于運載火箭來說，測試序列優(yōu)化設(shè)計可實現(xiàn)在常規(guī)測試或排故時，對測試項目進行優(yōu)選并形成最優(yōu)測試序列，達到快速、自動地識別故障并將故障隔離定位到設(shè)定的故障隔離層次，如功能電路層、板卡層、單機層的目的。新研火箭電氣系統(tǒng)設(shè)計可以在地面測試設(shè)備中嵌入測試序列優(yōu)化設(shè)計功能，實現(xiàn)從測試序列自動生成、到故障診斷模型生成、到測試程序集生成、到測試設(shè)備測試操作、最后到故障診斷報告生成的自動測試排故流程，輔助測試人員開展自動故障排查，減少當(dāng)前憑經(jīng)驗排故帶來的故障定位困難及大量的人力、時間成本，提高排故效率和自動化程度，適應(yīng)新型火箭的快速測試發(fā)射和排故需求。

6 結(jié)束語

通過對算法各性能參數(shù)的分析可以發(fā)現(xiàn)，基于加權(quán)Huffman編碼的啟發(fā)式評估函數(shù)能夠更準(zhǔn)確地評估隔離模糊故障集的測試代價，使當(dāng)前測試節(jié)點的擴展路徑更接近全局最優(yōu)，對于測試成本不同時的測試序列優(yōu)化具有更為明顯的效果。因此，DPSO-WAO*算法雖然取消了傳統(tǒng)AO*算法的回溯，但仍然取得了很好的優(yōu)化效果，并且大大降低了計算復(fù)雜度，同時較DPAO-AO*算法實現(xiàn)了尋優(yōu)性能的提升，可應(yīng)用于運載火箭、武器裝備等大型復(fù)雜系統(tǒng)的測試序列設(shè)計、故障診斷及定位中，具有重要意義。