王曉明，袁乾臣，王婧舒，李 璠

(1.北京宇航系統(tǒng)工程研究所，北京 100076；2.北京質(zhì)遠恒峰科技有限公司，北京 100080)

0 引言

相關性模型(dependency model)，也稱為相關性矩陣，是測試性建模的經(jīng)典模型[1-3]。相關性模型是對電氣產(chǎn)品的組成、故障模式、故障率、測試點、測試方法以及它們之間的邏輯關系進行描述的模型，其數(shù)學表達為依存矩陣(dependency matrix，簡稱為D矩陣)[2]。以D矩陣為輸入，通過分析測試點對故障的檢測與隔離的次序能夠得出產(chǎn)品測試序列即排故引導樹。然而故障模式的故障率不同，不同測試點的測試權(quán)重、測試費用、測試時間都是不同，從不同測試點出發(fā)所形成的排故引導樹也是不同[4]。

在解算復雜電氣產(chǎn)品的相關性矩陣時往往消耗的時間巨大[5]。目前，常用的診斷策略構(gòu)建方法主要包括：目前解決診斷策略設計問題的方法主要有三類：DP算法、群智能算法和啟發(fā)式搜索算法。

1)DP算法：

DP是一種遞歸算法，其中故障診斷樹形成過程是由上而下，按通過優(yōu)先方法進行搜索，隔離出全部故障為止[17]。對于診斷策略優(yōu)化問題，DP算法的儲存與計算需求為，其中m為故障數(shù)，n為測試數(shù)量，因此當n較小時是可行的，而對于大的復雜系統(tǒng)，其儲存和計算量將呈指數(shù)增長。因而不適合復雜電氣產(chǎn)品的診斷策略設計工作。

2)群智能算法：

群智能算法簡單來說就是一種一類仿生算法，仿造自然界中某些規(guī)律進行優(yōu)化，常見的有蟻群算法、粒子群算法等。

蟻群算法是一種用來解決多線路最優(yōu)的概率型算法。Dorigo等[15-16]根據(jù)螞蟻尋找食物過程中路徑尋優(yōu)的行為提出了蟻群算法。目前最常用的解決方式是將測試序貫優(yōu)化問題轉(zhuǎn)換為搜索最小完備測試序列問題，進而利用蟻群的記憶性與信息素積累反饋機制解決該問題。該算法著眼于每一只“螞蟻”的搜索，結(jié)構(gòu)簡單編程容易，算法具備反饋機制，可通過反饋不斷修正缺陷。但測試序列優(yōu)化問題與搜索最小完備測試序列問題并不完全等同，得到的測試序列與診斷策略存在區(qū)別，應用受限。

3)啟發(fā)式搜索算法：

常用于診斷策略優(yōu)化設計問題的啟發(fā)式搜索算法有貪婪算法、AO*算法、準深度算法等。

貪婪算法是快速搜索算法。該算法搜索速度快，采用固定順序方法構(gòu)造診斷樹。該算法對整個診斷樹采取局部擇優(yōu)搜索的策略，搜索速度極快，但效果不佳。

AO*算法被廣泛應用于測試性設計中，如TEAMS軟件就采用AO*生成診斷樹。算法優(yōu)勢是可以找到近似的全局最優(yōu)解，相比于DP算法效率有所提高，但需要處理的數(shù)據(jù)非常大，計算復雜，不適合大型系統(tǒng)。

準深度算法可以看成是深度算法的簡化，類似于貪婪算法，但考慮更多，每一步考慮的是之后的診斷樹的預估值，因而速度較快，大概率可找到全局最優(yōu)解。但該算法結(jié)構(gòu)復雜，且缺少反饋過程，難以應用于拓展場合。

以上三種啟發(fā)式搜索算法各有優(yōu)劣，在解決不可靠測試條件下的診斷策略優(yōu)化問題過程中可發(fā)揮一定作用。

本項目提出了一種結(jié)合全局最優(yōu)的啟發(fā)式AO*算法的Rollout策略的排故引導策略生成方法，其作為一種近優(yōu)的結(jié)算方法在解的復雜度方面要低于啟發(fā)式搜索算法，能夠確保運算速率。

1 基于全局最優(yōu)的啟發(fā)式AO*算法的測試序列生成方法

1.1 AO*算法概述

測試序列的生成方法直接影響故障診斷的準確度和執(zhí)行效率，基于全局最優(yōu)的啟發(fā)式AO*算法所生成的測試序列是一種全局最優(yōu)的測試策略[6]，該算法同三種信息啟發(fā)式(霍夫曼編碼、熵、熵+1)函數(shù)相結(jié)合，通過向下擴展以及向上反饋修正兩個基本操作來得到最優(yōu)的測試序列，它的計算量小于DP算法和群智能算法，在搜索過程中會進行不斷回溯，以實現(xiàn)最優(yōu)解[7]。

1.2 AO*算法的基本元素及輸出策略

AO*算法的輸入包括以下內(nèi)容：

1)系統(tǒng)狀態(tài)集合：

S={s0，s1，...sm}

(1)

其中：s0為系統(tǒng)的無故障狀態(tài)，si為故障狀態(tài)1～m。

2)故障概率向量：

p=[p(s0)，p(s1)，...p(sm)]T

(2)

其中：p(s0)為系統(tǒng)完好率，p(s1)，...p(sm)為各故障模式的頻數(shù)比*(1-完好率)。

3)測試集合：

t={t1，t2，...tn}

(3)

4)成本向量(時間、人力、其他經(jīng)濟因素)：

c=[c1，c2，...cn]T

(4)

AO*算法的輸出綜合考慮故障發(fā)生概率、測試時間，測試費用等的最優(yōu)診斷樹，AO*算法使用啟發(fā)式評估函數(shù)(HEF)指導測試搜索過程[8]，其計算公式為：

(5)

(6)

1.3 AO*算法步驟

采用AO*算法實現(xiàn)測試序列的優(yōu)化的基礎是啟發(fā)式評估函數(shù)的構(gòu)造。AO*算法是基于啟發(fā)式評估函數(shù)h(x)，選擇最有可能達到目標節(jié)點的子節(jié)點進行擴展。其基本步驟如下。

Step 1：建立一個搜索圖G，使其僅僅包含起始節(jié)點S，設F(s)=h(s)。如果S為終節(jié)點，則標記S為SOLVED，離開算法步驟。

Step 2：重復以下步驟，直到S己經(jīng)標記為SOLVED，此時J=F(s)為期望的測試代價，并以標記的解樹為測試算法。

Step 2.1：通過跟蹤G中從S出發(fā)的、有標記的、連接符，計算G中的一個局部解圖G′。選擇G′中最高h(x)的節(jié)點x進行擴展。最初時x=S(x為系統(tǒng)狀態(tài)集合)。

Step 2.2：擴展節(jié)點x，生成它的所有后繼節(jié)點的二元集合，表示為(xjp，xjf)，tj?Πx。其中，Πx為在通向x的路徑上已經(jīng)標記使用的測試集。初始Πx為空。對于每一個在G中未曾出現(xiàn)過的x的后繼節(jié)點，設：

F(y)=h(y)

(7)

y=xjp，xjf，tj?Πx

(8)

其中：如果任意y屬于終節(jié)點，則標記其為SOLVED。

Step 2.3：建立一個僅包含節(jié)點x的節(jié)點集合Z。

Step 2.4 ：執(zhí)行以下步驟，直到Z為空：

Step 2.4.1：從Z中移出這樣的節(jié)點y，這個y在G中的后裔不出現(xiàn)在Z中。(移出當前沒有后裔的，最底層的節(jié)點進行分析)

Step 2.4.2：修正y的值如下所示：

(9)

其中：p(yip)為相對概率。令k為測試代價最小值的坐標，并對這個具有最小值的連接符加以標記，包括(y，ykp)和(y，ykf)。如果ykp和ykf都已標記SOLVED，則標記此節(jié)點y為SOLVED。

Step 2.4.3：如果F(y)≠e，設F(y)=e。(由于測試的選擇及向下擴展的節(jié)點而導致的成本改變，修正y的值為選擇當前最小成本的測試tk的情況下的成本值e。

Step 2.4.4：如果F(y)在2.4.3中修正了值，或己標記為SOLVED，則把沿著標記路徑的y的所有父輩節(jié)點都添加到Z中，忽略了沒有由標記的連接符連接到y(tǒng)的先輩節(jié)點。(若y被修正或已下溯到根節(jié)點，則將其上游的、當前標記路徑中的先輩節(jié)點都添加到Z中，對先輩節(jié)點進行修正計算，即執(zhí)行2.4.1到2.4.4的步驟，直到Z為空。(Z為空表示已回溯結(jié)束，或已到起始節(jié)點，或已到?jīng)]有發(fā)生修正的節(jié)點)。

2 基于Rollout策略的測試序列生成方法

2.1 Rollout算法概述

Rollout算法的基本思想是用一個基準策略經(jīng)過Rollout仿真得到一個更新策略，再把更新策略作為基準策略進行迭代更新，逐步逼近最優(yōu)策略[9]。該方法能得到比基準策略更加精確的結(jié)果，但是不能保證是全局最優(yōu)解。

2.2 Rollout算法基本元素

設某產(chǎn)品共有(m+1)類狀態(tài)，故障測試相關矩陣表示為D=[dij]，根據(jù)測試結(jié)果值的不同，可分為二值測試和多值測試，二值測試即dij只有兩個狀態(tài)，比如(0，1)、(通過，不通過)，多值測試即dij存在三個或三個以上的狀態(tài)[9]，比如(0，0.5，1)、(0，1，2，3)、(通過，不通過，待定)。

測試序列產(chǎn)生目標是合理規(guī)劃測試順序，使得在達到故障隔離目的的情況下測試費用最小。

定義所需測試費用為：

(10)

其中：pi表示隔離故障si所用的測試集合，|pi|表示測試集合的容量。

2.3 Rollout算法步驟

Step 1：初始化創(chuàng)建一個模糊集Z，只包含根節(jié)點S。初始化一個圖G。如果S是終端節(jié)點，則將S加入到G，則G就是問題的解。

Step 2：重復以下操作，直到模糊集Z為空后停止，則G就是問題的解。

Step 2.1：從模糊集Z中移除一個模糊集節(jié)點xi，加入到圖G中，如果xi是一個已解節(jié)點則從模糊集Z中取下一個模糊集節(jié)點。對模糊節(jié)點xi的可用測試集Tj中的所有測試tj，重復以下步驟。

Step 2.1.1：初始化一個模糊集節(jié)點Y′，創(chuàng)建一個圖G′，將測試tj加入到圖G′中，用tj將xi分解成兩個模糊子集，測試通過xijp和測試失敗xijf，將xijp和xijf加入到Y(jié)′中，重復以下步驟直到Y(jié)′為空。

(11)

IG(x，tj)=-p(xjp)log2p(xjp)-p(xjf)log2p(xjf)

(12)

(13)

Step 2.1.2：計算測試的費用開銷：

(14)

其中：xl是xijp的模糊子集，lj表示xijp的模糊子集個數(shù)，Pq表示隔離的節(jié)點到xijp節(jié)點的測試序列，|Pq|表示測試序列中的元素個數(shù)，cpq[r]表示Pq的第r個測試費用。

Step 2.2：令

htj(xi)=cj+h(xijp)p(xijp)+h(xijf)p(xijf)

(14)

選擇t*∈Tj使得：

h(xi，t*)=mintj∈Tjhtj(xi)

(15)

并將節(jié)點xi展開。將t*加入到圖G中。把用t*拆解的模糊子集xip和xif加入Z中，然后返回Step 2.1。

3 基于全局最優(yōu)的A0*信息啟發(fā)式Rollout算法

為了減輕計算量并獲得比啟發(fā)式算法更好的結(jié)果，我們將Rollout策略與基于全局最優(yōu)的AO*啟發(fā)式方法相結(jié)合，以基于錯誤狀態(tài)概率，測試成本和依賴矩陣有效地構(gòu)建測試序列。

3.1 算法概述

此算法中，如果它最大化了以下測試的單位成本信息增益，則從歧義狀態(tài)中選擇測試。

(16)

其中：IG(x，tj)是信息增益，由以下公式給出：

IG(x，tj)=-{p(xjp)log2p(xjp)log2p(xjp)+

p(xjf)log2p(xjf)log2p(xjf)}

(17)

因此，信息啟發(fā)式是一個具有計算復雜性O(mn)的一步前向程序。其它相關啟發(fā)式有“分別啟發(fā)式”，dc(x，tj)，(又稱為可區(qū)分性啟發(fā)式)，定義如下：

dc(x，tj)=p(xjp)·p(xjf)

(18)

選擇一個測試tk，以最大化每個歧義節(jié)點的可區(qū)分性標準。很容易表明，測試成本相等時，信息啟發(fā)式提供了與可分辨性標準相同的測試樹?；诙嗔x的或節(jié)點對決策樹進行的深度優(yōu)先擴展，信息啟發(fā)式(稱為多步信息啟發(fā)式算法)的變體涉及給定級別(基于多步前向)的選擇測試。測試給定級別的有效性仍根據(jù)其每單位測試成本的信息增益進行評估。

3.2 算法步驟

Step 1：建立一個節(jié)點集Z，僅包含根節(jié)點S與一個空圖形G。如果S是一個終止節(jié)點，添加S至圖形G中，退出解。

Step 2：重復下列步驟至Z為空集，然后退出，以解決方案樹作為測試算法。

Step 2.1：從Z中移出一個或節(jié)點i至G。如果i是一個目標節(jié)點，繼續(xù)Z中的下一個或節(jié)點；否則，考慮可行測試集Ti中的每一個測試ti，它們將節(jié)點i分為通過/失敗子集：xijp與xijf(i的直接后續(xù)或節(jié)點)。創(chuàng)建一個集合Y與圖形G′，兩者均由i的直接后續(xù)或節(jié)點構(gòu)成。重復下列程序(信息啟發(fā)式)直至Y為空。

Step 2.1.1：從Y中移除一個或節(jié)點r。如果這是一個非目標節(jié)點，計算該節(jié)點每一個可行測試的單位成本信息增益；否則，前往Y的下一個或節(jié)點。

Step 2.1.2：選擇r中單位成本信息增益達到最高的測試。通過選擇最小指數(shù)的測試解決關系。將該項測試加入G′。分別根據(jù)選定測試的通過/失敗結(jié)果將r分為通過/失敗子集。將獲得的通過/失敗或節(jié)點加入Y與G′。

Step 2.2：基于測試序列(存于G′)，計算每個i的后續(xù)或節(jié)點預期測試成本(如xijp)，公式如下：

(19)

Step 2.3：計算或節(jié)點i的每個候選測試ti∈Ti的期望測試成本，公式如下：

htj(xi)=cj+p(xijp)h(xijp)+p(xijf)h(xijf)

(20)

其中：h(xijp)和h(xijf)分別對應通過/失敗或節(jié)點子集xijp與xijf生成測試樹中的預期測試成本。

Step 2.4：選擇t*∈Ti，獲得最小期望測試成本。使用Step 2.1信息啟發(fā)式，通過有利于測試生成，還有最小指數(shù)目標解決關系。將t*加入G，然后分別將t*測試生成的通過/失敗結(jié)果加入通過/失敗或子集G與Z。

3.3 算法實例

表1給出某電氣系統(tǒng)的相關性矩陣[10-12]。S(i)為某電氣系統(tǒng)的故障模式，TPj為系統(tǒng)的測試項，P(si)為S(i)的故障模式頻數(shù)比。在相關性矩陣中1代表測試項TP與故障模式S相關，0代表不相關。

表1 某電氣系統(tǒng)相關性矩陣

初始節(jié)點S包含所有可能狀態(tài)s0，s1，...s5。首先，我們采用Step 2.1，應用圖1列舉的所有5種可行測試將S分為通過/失敗節(jié)點。

圖1 測試分割

對于t1子樹，分別有子集{s0，s1，s2}與{s3，s4，s5}對應通過與失敗或節(jié)點。我們在{s0，s1，s2}上執(zhí)行步驟Step 2.1.1和Step 2.1.2(即信息啟發(fā)式)。

圖2 測試t1通過選擇第二個測試點

測試t2單位成本信息增益：

IGIG(x，t2)=-{p(x2p)log2p(x2p)log2p(x2p)+

p(x2f)log2p(x2f)log2p(x2f)}=

(21)

測試t3單位成本信息增益：

IG(x，t3)=-{p(x3p)log2p(x3p)log2p(x3p)+

p(x3f)log2p(x3f)log2p(x3f)}=

(22)

測試t4單位成本信息增益：

IG(x，t4)=-{p(x4p)log2p(x4p)log2p(x4p)+

p(x4f)log2p(x4f)log2p(x4f)}=

(23)

測試t5單位成本信息增益：

IG(x，t5)=-{p(x5p)log2p(x5p)log2p(x5p)+

p(x5f)log2p(x5f)log2p(x5f)}=

(24)

根據(jù)：

(25)

得到k={3，4}。

t2和t5的單位成本信息增益均為0.104 4，t4與t3的單位信息成本增益最大，為0.181 2。t4與t3的增益相等，選擇測試序號較小的測試，則選擇測試t3為第二個測試點。

反復應用信息啟發(fā)式，直到為或節(jié)點{s0，s1，s2}構(gòu)建的測試子樹完整，如圖3所示。測試t2和t5分割結(jié)果相同，選擇t2。

圖3 測試t1通過側(cè)生成完整診斷樹

對測試t1失敗子集或節(jié)點{s3，s4，s5}執(zhí)行相同的過程：我們在{s3，s4，s5}上執(zhí)行Step 2.1.1和Step 2.1.2(即信息啟發(fā)式)。

圖4 測試t1不通過選擇第二個測試點

測試t2單位成本信息增益：

IG(x，t2)=-{p(x2p)log2p(x2p)log2p(x2p)+

p(x2f)log2p(x2f)log2p(x2f)}=

(26)

測試t3單位成本信息增益：

IG(x，t3)=-{p(x3p)log2p(x3p)log2p(x3p)+

p(x3f)log2p(x3f)log2p(x3f)}=

(27)

測試t4單位成本信息增益：

IG(x，t4)=-{p(x4p)log2p(x4p)log2p(x4p)+

p(x4f)log2p(x4f)log2p(x4f)}=

(28)

測試t5單位成本信息增益：

IG(x，t5)=-{p(x5p)log2p(x5p)log2p(x5p)+

p(x5f)log2p(x5f)log2p(x5f)}=

(29)

綜上所述，測試t3單位成本信息增益最大，所以選擇測試t3為第二個測試點。

在{s3，s4}上執(zhí)行Step 2.1.1和Step 2.1.2，計算得到，測試t2、測試t4、測試t5單位成本信息增益相同，因此選擇測試t2。

圖5 測試t1不通過側(cè)生成完整診斷樹

最終采用Rollout信息啟發(fā)式算法選擇第一個測試t1得到完整的診斷樹如下：

圖6 Rollout信息啟發(fā)式算法完整的診斷樹

可見，基于全局最優(yōu)的A0*信息啟發(fā)式Rollout算法能夠快速得到有效的測試序列樹，基于測試序列樹可進一步轉(zhuǎn)化為ATE(自動測試設備)中TPS(測試程序集)的測試程序，作為ATE的測試策略，同時，也可以進一步轉(zhuǎn)化為符合S1000D標準和GJB6600的排故引導數(shù)據(jù)模塊，作為IETM(交互式電子技術(shù)手冊)的重要組成部分。

4 結(jié)束語

裝備的復雜度與性能一直呈正相關關系，這使得隨著武器裝備的發(fā)展，對裝備開展測試性設計的難度也越來越大，需要考慮的因素也越來越多。如何利用現(xiàn)有的數(shù)據(jù)信息建立精度最高的測試性模型，采用何種算法才能快速有效地解決診斷策略生成問題，是測試性設計的核心問題。

采用基于全局最優(yōu)的啟發(fā)式AO*算法的測試序列生成方法可既考慮到可靠性，也考慮測試費用最小。其優(yōu)點是診斷結(jié)果為“全局最優(yōu)”診斷樹。其缺點是由于在搜索過程中需要存儲的臨時支路和數(shù)據(jù)非常大[13]，一般只用于規(guī)模較小的系統(tǒng)[14](故障模式<50)?；赗ollout策略的測試序列生成方法既考慮可靠性，也考慮測試費用最小。其優(yōu)點是診斷結(jié)果為“近似最優(yōu)”診斷樹，診斷效率高。既減輕龐大的計算量，又獲得了比次優(yōu)啟發(fā)式算法更好的診斷結(jié)果。該方法缺點是需要算出全部潛在診斷樹之后再進行尋優(yōu)，不適用于規(guī)模過于龐大的系統(tǒng)。