用于測試序列優化的DPSO-WAO*算法研究

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

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

0 引言

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

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

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

1 測試序列優化問題分析與建模

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

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

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

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

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

Dm×n是測試與系統狀態的相關性矩陣。其基本形式為：

(1)

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

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

(2)

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

2 現有AO*算法及DPSO-AO*算法

AO*算法通過構建與或圖采用top-down的搜索方法進行故障隔離，如圖1所示。或節點對應故障集節點X；與節點對應可用測試節點tj，其各子節點分別代表tj應用于故障狀態集節點X后根據其測試結果和相關矩陣所得的通過故障子集Xjp和失敗故障子集Xjf。

AO*算法是兩個運算階段的反復：

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

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

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

(3)

若故障集X被測試tj區分為兩個故障子集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通過和失敗的相對概率。傳統AO*算法利用式(4)中hx的值評價測試點tj，選取hx最小的tj向下擴展。并在每次向下擴展之后將測試成本向上回溯，以確保當前所擴展測試的全局最優性。

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

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

(5)

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

(6)

式(6)中，P(ti)代表測試ti能檢測到的故障可能發生的總概率；S(ti)代表ti所能檢測到的故障的最小可測度，a為其系數，需根據實際優化結果進行調整。

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

3.1 基于加權Huffman編碼的啟發式評估函數

傳統AO*算法依據評估函數選擇最優測試，實現故障樹的向下擴展，并結合向上回溯來保證測試選擇的正確性，其優化性能主要取決于以下兩點。

1)啟發式評估函數對于故障集的測試代價描述的準確性：

啟發式評估函數越接近真實的最小測試代價，則對于測試的選擇越準確，越接近全局最優。

2)回溯步數：

回溯的目的是檢驗當前所選測試的全局最優性，向上回溯步數越多，則越接近全局最優，若每一次測試選擇都向頂端節點回溯，則所生成的測試序列一定為全局最優。

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

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

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

(7)

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

1)優先隔離故障率高的故障；

2)優先選擇測試成本低的測試。

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

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

3.2 DPSO-WAO*算法實施步驟

基于DPSO-WAO*算法的測試序列優化方法與傳統AO*算法基本相同，但由于啟發式函數的準確性更高，因此取消了向上回溯這一步驟，流程如圖2所示。

圖2 基于DPSO-WAO*算法的測試序列優化流程

具體流程如下：

1)建立一個僅由根節點(系統故障狀態集)構成的有向圖。

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

①利用DPSO算法對當前可用測試集進行篩選，獲得優化的測試子集；

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

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

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

4 實例校驗及算法對比

4.1 實例校驗

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

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

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

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)

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

表1 各算法性能參數比較

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

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

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

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

2)測試代價標準差。代表算法尋優性能的穩定性，該數值越小，代表各次優化結果一致性好，算法運行穩定可靠。

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

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

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

注:算法各性能參數均以連續運行10次所得結果取平均值。

4.2 算法比對

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

1)尋優性能：

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

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

2)計算效率和復雜度：

DPSO-WAO*算法的平均運行時間與DPSO-AO*算法的平均運行時間相當，且均遠小于傳統AO*算法，僅為傳統算法所需時間的約15%，其擴展節點數目也約為傳統AO*算法的15%。可以證明，DPSO-WAO*算法在進行測試節點擴展前利用DPSO對當前可用測試集進行優選，避免陷入局部最優，并大大減少了擴展節點的數目，提高了算法的計算效率，且越復雜的系統，采用DPSO-WAO*算法獲得的計算效率提升效果也越明顯。

5 測試序列優化方法在運載火箭電子設備中的應用模式思考

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

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

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

2)測試項目的選擇和排序從依據人員經驗和定性原則轉向依據定量優化方法。

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

6 結束語

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