單步和多步尋優結合的診斷策略構建方法*

杜小帥，胡冰，施端陽，張馨予

（1.空軍預警學院，湖北 武漢 430010；2.中國人民解放軍94005部隊，甘肅 酒泉 735000）

0 引言

隨著高新科技的發展和應用，武器裝備的結構和功能越來越復雜化、精細化，其使用條件和戰場環境的惡劣程度日趨提升，對裝備的測試與診斷提出了更高的要求。而要解決這一問題則需要采用“并行工程”的思想，在裝備設計階段就使其具有良好的測試性。診斷策略設計是測試性設計和分析的一項重要內容［1］，是提高故障診斷效率、改善裝備故障診斷能力、降低全壽命周期費用的關鍵。GJB 2547A-2012將診斷策略定義為“綜合考慮規定約束、目標和有關影響因素而確定的、用于依據觀測數據進行故障診斷的測試判斷邏輯”［1］。

Pattipati證明診斷策略問題是NP-Complete問題［2］，窮舉法雖然能夠得到最優解，但計算時間隨問題復雜程度成指數性增長。為降低計算復雜度，國內外學者將啟發式搜索方法應用在診斷策略構建問題中。AO*算法［2-3］主要以霍夫曼編碼平均字長構造啟發式評估函數，根據啟發式評估函數估計測試費用的下界值，通過不斷回溯修正找到測試費用最小的診斷策略，但回溯操作大大增加了AO*算法的計算復雜度。信息熵算法［4-5］等單步尋優搜索方法每次只選擇符合約束條件的最優測試，計算速度快，但最優性較差。多步尋優搜索方法［6］在單步尋優搜索方法的基礎上預先生成MSTEP層部分診斷樹［7］，通過計算部分診斷樹的診斷效果判斷測試的優劣。由于考慮了多步測試的共同信息，其最優性比單步尋優搜索方法好。Rollout算法［8-9］以信息熵算法為基準策略生成完整的診斷樹，通過回溯迭代找到比基準策略更為精確的結果，計算量較AO*算法小，但也存在回溯操作。Growing算法［10］將隔離單個故障的測試分為基本測試和不必要測試，在構建診斷策略時，先選擇故障，后確定測試，按照先驗概率的大小順序隔離故障，生成不包含不必要測試的測試序列，但是當故障的先驗概率相近時，其最優性不佳。

針對上述問題，本文以自上而下構造診斷策略的思想為基礎，提出了一種根據故障狀態模糊集的概率分布情況選擇單步或多步尋優搜索方法的診斷策略構建方法。首先分析了單步尋優搜索方法特點和不足。然后以隔離單個故障為目標，得到一種無回溯的多步尋優搜索方法，并將單步尋優搜索方法與多步尋優搜索方法相結合，使先驗概率較大的故障具有較少的測試步驟和費用。最后對實際案例進行了應用研究和分析計算，通過與信息熵算法、Rollout算法和AO*算法的診斷結果進行對比，驗證了方法的有效性。

1 診斷策略問題描述

1.1 診斷策略模型描述

故障診斷策略問題可描述為五元組：

（1）F=｛f0，f1，…，fm｝為裝備故障狀態集，包含裝備所有的故障狀態，其中，f0是無故障狀態，fi（i=1，2，…，m）表示當且僅當第i個故障發生時的故障狀態。

（2）P=｛P（f0），P（f1），…，P（fm）｝表示與裝備m+1個故障狀態對應的先驗概率集合，滿足0

（3）T=｛t1，t2，…，tn｝為裝備的測試集，規定測試只有通過、不通過2種情況，且測試結果可靠。

（4）C=｛c1，c2，…，cn｝表示n個測試對應的測試費用的集合，其中cj表示執行測試tj所需的費用。設定測試費用為無量綱的物理量。

（5）D=（dij）（m+1）×n為故障-測試相關矩陣，用來描述故障模式集和測試集的依賴關系。相關性矩陣是裝備測試與診斷的基礎。矩陣行表示故障狀態，列表示測試，矩陣中的元素dij表示測試與故障狀態的相關性，其值為0或1。dij=1表示測試tj可以檢測故障fi，即故障發生時，測試不通過；dij=0表示tj不能夠檢測故障fi，即故障發生時，測試通過，d0j=0，?j。

1.2 故障診斷推理機

按照診斷策略的測試執行順序，每個測試執行后，根據結果推測裝備的故障結論。設裝備故障狀態模糊集為X，用測試tj檢測X有通過（dij=0）和不通過（dij=1）2種輸出，分別記為Xj0和Xj1。推理機是裝備故障狀態邏輯推斷的推理方法。X到Xj0和Xj1過程的推理方法就是推理機。

且

X被測試tj劃分為2個子集Xj0和Xj1。

1.3 最優診斷策略

在故障診斷隔離過程中，會產生相應的測試費用，測試費用期望值的計算公式為

式中：J為測試費用的期望值；Di為診斷樹D中隔離出故障fi的測試序列，|Di|為該序列的長度；cDi［k］為序列Di中的第k個測試的費用；P（fi）為故障fi的先驗概率。

最優診斷策略構建的目的是，當裝備發生故障時，能夠按照給定邏輯和順序選擇測試，快速檢測和準確隔離故障，并且使得測試費用期望值最小，其計算公式為

Dopt表示不模糊的隔離全部故障且平均測試費用最少的診斷策略。

2 單步和多步尋優結合的診斷策略構建方法

2.1 單步尋優搜索方法

單步尋優搜索方法每次只確定一個測試，通過構造啟發式評估函數，每次選擇使啟發式評估函數達到最優的測試，根據測試結果診斷隔離故障，劃分故障模糊子集，并不斷向下拓展。由于單步尋優搜索方法僅考慮當前最優的測試，因此也被稱為貪婪搜索方法。信息熵算法以最大化單位費用信息增益為優選測試的依據并構造啟發式評估函數［4］，是應用最廣泛的貪婪搜索方法，其啟發式評估函數為

式中：IG（X；tj）表示測試tj與故障狀態模糊集X的互信息，即使用測試tj診斷待隔離故障狀態模糊集而得到的信息量。

分辨力啟發式評估函數［11］與式（8）等價：

通過對第1節的分析可知，診斷策略構建與無噪聲編碼之間具有相似性［12］：測試結果對應二元信息；故障狀態集中各故障的測試步驟數對應信源的編碼長度；診斷樹的平均測試步驟數對應平均編碼長度；最優診斷策略對應最小化交叉熵。要使交叉熵最小，則概率較大的元素應具有較小的編碼長度。故在診斷策略構建問題中，應使先驗概率較大故障具有較少的測試費用和測試步驟數。

信息熵算法考慮了故障發生概率、故障-測試相關性和測試費用等因素，但其在選擇測試時，只考慮單步測試所獲取的信息，而沒有考慮所選測試對整體費用和后續測試的影響。因此以信息熵算法構造診斷策略，不能保證先驗概率較大的故障對應較少的測試費用和測試步驟數。

以文獻［2］的相關性矩陣為例，分析信息熵算法的實現過程及特點，其相關性矩陣如表1所示。給定測試費用為｛5，10，15，5，20｝。

表1 相關性矩陣Table 1 Dependency matrix

信息熵算法具體步驟可參考文獻［4］，其生成的診斷策略如圖1所示。

故障f0的先驗概率在故障狀態集中占有較大比例，應該以較少測試步驟和費用對其進行診斷隔離。在圖1中，故障f0對應的測試序列為［t1，t4，t2］，但對表1的相關性矩陣分析可知，使用測試t2，t4即可隔離故障f0，故t1為此測試序列中的多余測試［10］。

圖1 信息熵算法的診斷策略Fig.1 Diagnostic strategy based on greedy algorithm

信息熵算法作為單步診斷策略構建方法，在生成診斷策略時只考慮當前最優的測試。在表1的實例中，t1使單位費用信息增益達到最大值，故信息熵算法選擇t1為第1步最優測試。然而僅得到t1而不考慮后續測試，則會增加f0的測試序列長度與測試費用，從而會相應地增加診斷策略的整體測試費用。

2.2 多步尋優搜索方法

為使診斷策略的整體期望測試費用最小，則先驗概率較大的故障應該具有較少的測試費用和測試步驟數，所以需要研究隔離單個故障的測試序列生成方法，綜合考慮多步測試對整體費用的影響。

2.2.1 隔離單個故障的測試集生成方法

若故障fi能被測試集T隔離，則在以T為列的相關矩陣DT中，故障fi所在的行必須與其他行相異［13］。因此故障可隔離的條件可以表示為

式中：符號Π為“邏輯乘”；符號⊕為“異或”運算；T fi，T fj分別為fi，fj在矩陣DT中所對應的行向量；假設故障模糊集包含m+1個故障狀態。

隔離2個故障的條件是，在相關性矩陣中，2個故障對應的行向量相異。其中，相異元素對應的測試能夠隔離這2個故障。用邏輯“或”表示對應的測試，得到隔離2故障的測試方案，用I（fi，fk）表示為

式中：符號∑為“邏輯加”。例如，I（fi，fk）=t1+t2表示t1或t2可以隔離故障fi和fk。其中，符號“⊕”表示邏輯“或”。稱集合Tik=｛t1，t2｝為隔離故障fi與任意故障fk的隔離測試集：

式（13）得到隔離故障fi與任意故障的測試方案，若將所有的測試方案做累積運算，可得到隔離故障fi的所有測試組合，不妨將I（fi，F）表示隔離fi的測試方案：

把式（14）完全展開成“與或”式，顯然每一個“與”式均能表示隔離fi的測試組合，各測試組合中元素組成的集合稱為隔離故障fi的診斷隔離測試集，由此，可得到故障fi的一組診斷隔離測試集去除其中的真超集，得到故障fi的所有最小診斷隔離測試集。例如，故障集F中有3個 元 素，I（f1，f2）=t1+t2，I（f1，f3）=t1+t3，由 式（14）可 得I（f1，F）=t1+t1·t2+t1·t3，表 示t1，t1與t2，t1與t3均 可 隔 離故障f1。其中，符號“·”表示邏輯“與”。由此，可得到故障f1的診斷隔離測試集為｛t1｝，｛t1，t2｝，｛t1，t3｝。顯然，｛t1｝為故障f1的最小診斷隔離測試集。

診斷隔離測試集具有以下2個性質：

（1）故障fi的診斷隔離測試集為其所有隔離測試集并集的子集：

（2）故障fi的診斷隔離測試集與其每個隔離測試集的交集都不為空集：

2.2.2 測試排序

2.2.1 節僅能確定隔離單個故障的測試集，若要生成測試序列，則需要進一步確定最小診斷隔離測試集中的測試順序。多步尋優搜索方法可以看作單步尋優搜索方法的多次疊加過程，且在最小診斷隔離測試集中不存在多余測試，因此采用信息熵算法對最小診斷隔離測試集中的測試進行排序。

以表1的相關性矩陣為例。｛t1，t2，t3｝是故障f0的一個最小診斷隔離測試集，且初始故障狀態模糊集X=F。由于隔離故障f0的測試集已經確定，則其測試費用也已確定，其在測試排序過程中能夠提供的信息量為0。因此，在測試排序前首先需要更新故障狀態模糊集及故障概率。X′=F-f0，P′（fi）=P（fi）/利用式（8）計算各測試的單位費用信息增益的值為0.093 8為0.097 1，為0.066 5。因此，選擇t2為第1步最優測試。根據測試結果將X劃分為2個子集｛f0，f2，f3｝和｛f1，f4，f5｝。將包含f0的子集賦予X，更新各子集的故障概率，選擇t1為第2步測試，因此得到測試序列為［t2，t1，t3］。

2.2.3 測試序列優選

為獲得最優的診斷策略，達到使測試費用期望值最小的目的，需要在確定待檢測故障的所有最小診斷隔離測試集和相應的測試序列后，以費用最小為原則選出最優的測試序列。

假設存在故障狀態模糊集X和故障fi，且fi∈X，fi的測試序列記為Di。隔離故障fi的期望測試費用記為J（fi）

式中：|Di|為測試序列Di的長度；cDi[k]表示序列Di中第k個測試的費用。

測試序列Di不能隔離故障狀態模糊集中的所有故障，因此在隔離故障fi時，會產生一組故障狀態模糊子集（X1i，X2i，…，Xl）i，由于X（rir=1，…，l）是伴隨診斷隔離故障fi產生的，所以稱其為故障fi的伴生故障集［10］。對每個伴生故障集，使用式（18），（19）更新其故障狀態的概率：

伴生故障集的期望測試費用為

式中：Dri為伴生故障集的測試序列，由于是在隔離故障fi的過程中產生的，故由故障fi的測試序列Di決定；||表示測試序列的長度表示測試序列中第h個測試的費用。

若要生成完整的診斷策略，需進一步隔離伴生故障集中的故障，故障隔離過程會產生相應的測試費用。因此，全面評估整體測試費用，需要對伴生故障集的隔離費用進行估計。霍夫曼編碼［14］被稱為最佳編碼，能夠按照字符出現概率構造平均長度最短的碼字。對故障集，其期望測試步驟的下界值可用霍夫曼編碼的平均字長近似估計。將備選測試集中測試的費用按照由小到大的順序進行排序（0≤c1≤…≤cn），將霍夫曼平均字長與備選測試集中對應測試的費用相結合，可以得到基于霍夫曼編碼的測試費用評估函數［15］。由此，可對伴生故障集的最小故障隔離費用進行估計：

式中：h（Xri）為故障狀態模糊集Xri的最小測試費用估計函數，該函數給出了故障狀態模糊集Xri故障隔離費用的下界；L（*Xri）為故障狀態模糊集Xri的霍夫曼編碼平均字長；為取下整數；L（fj）為fj對應的霍夫曼編碼長度。

用h（X，fi，Di）表示使用測試序列Di隔離故障fi，并構造完整診斷策略的測試費用估計值：

將式（17）～（21）代入式（23）可得

選擇使h（X，fi，Di）達到最小的測試序列為隔離故障fi的最優測試序列。由此，可得多步尋優搜索方法的啟發式函數：

2.3 診斷策略構建的方法優選

要使先驗概率大的故障對應較少的測試費用和測試步驟數，同時考慮診斷樹整體的測試費用，則需要根據故障狀態模糊集中的故障概率分布情況，選擇使用單步或多步尋優搜索方法。由于單步和多步尋優搜索方法均采用自上而下的方式構造診斷樹，故在優選方法時，利用費諾編碼的原理對故障狀態模糊集進行分析。

將故障狀態模糊集中的故障按概率大小進行降序排列（P（f1）≥P（f2）≥…≥P（fz）），在此順序中，選擇一處斷開位置，將故障狀態模糊集劃分為2組，使每組概率和最接近相等。當其中一組只含有單個故障f1時，則優先隔離f1，使用多步尋優搜索方法生成隔離f1的測試序列；否則，使用信息熵算法選擇診斷當前故障狀態集的最優測試。

根據分辨力函數的性質，概率和乘積越大，則兩者越接近。則故障優先隔離條件可表示為

當故障狀態模糊集中故障概率滿足式（26）時，說明fi單獨為一組時，2組的概率和最接近相等，則認為隔離fi的測試費用對整體費用具有較大的影響，使用多步尋優搜索方法優先隔離f1；否則，使用單步尋優搜索方法。

2.4 詳細步驟

步驟1初始化五元組。令X=F，創建一個集合FS存放故障模糊子集。

步驟2使用式（27）更新X中各故障的概率：

步驟3生成X的備選測試集合T′（包含求解節點X的過程中沒有用過的測試）。根據下列步驟，選擇單步或多步尋優搜索方法。

（1）將X的故障按概率降序排列。

（2）優選診斷策略構建方法，當X中故障滿足式（26）時進入步驟4，否則進入步驟5。

步驟4隔離X中概率最大的故障fi并生成其對應的最優測試序列。

（1）根據式（12）～（14）得到故障fi的診斷隔離測試集，去除其中的真超集，得到fi的最小診斷隔離測試集。

（2）利用信息熵算法的啟發式評估函數對最小診斷隔離測試集中的測試進行排序，得到隔離故障fi的測試序列。

（3）根據式（24）計算各測試序列的費用估計值，選擇使h（X，fi，Di）達到最小的測試序列為fi的最優測試序列。使用最優的測試序列隔離故障fi，生成診斷樹的部分圖解，并得到fi的伴生故障集（X1i，若伴生故障集Xri中元素個數大于1，則將Xri加入集合FS。

步驟5使用信息熵算法的啟發式評估函數從備選測試集中選擇當前最優測試，根據測試結果劃分故障子集，若子集中元素大于1，則加入FS。

步驟6重新取X為FS中的元素，重復步驟2～5，直到FS中元素個數小于1。

3 實例驗證

3.1 仿真計算

以表1相關形矩陣為例，說明單步和多步尋優結合的診斷策略構建方法的實現過程，其生成的診斷樹如圖2所示。

X=F，將X中故障按概率大小降序排列（0.7>0.12>0.10>0.05>0.02>0.01）。根據式（26），優選診斷策略構建方法。X中元素滿足0.7×（1-0.7）>0.82×（1-0.82），即將先驗概率最大的故障f0單獨劃為1組時，劃分的2組概率和最為接近，所以首先隔離故障f0，使用多步尋優算法生成隔離f0的測試序列。

根據式（12）～（14）得到f0的最小診斷隔離測試集為｛t2，t4｝，｛t1，t2，t3｝，｛t1，t3，t5｝，｛t1，t4，t5｝，｛t2，t3，t5｝，使用信息熵算法對測試集中的測試進行排序，得到f0的 測 試 序 列 為［t4，t2］，［t2，t1，t3］，［t1，t3，t5］，［t4，t1，t5］，［t2，t3，t5］。

根據式（24）選擇隔離故障f0最優的測試序列。測試序列［t4，t2］使h（X，f0，Di）達到最小值，故選擇［t4，t2］為隔離故障f0的最優測試序列，得到伴生故障集｛f1，f4｝，｛f2，f3，f5｝。

選擇t1為診斷故障模糊子集｛f1，f4｝的最優測試。對模糊子集｛f2，f3，f5｝，使用式（27）更新子集中的故障概率，對故障模糊子集中的故障按概率降序排列（0.5>0.416 7>0.083 3），其中f5滿足式（26），則優先隔離f5。

根據式（12）～（14）得到f5的最小診斷隔離測試集為｛t2｝，｛t1，t3｝，｛t1，t5｝，對集合中的測試進行排序，得到隔離f5的測試序列為［t2］，［t1，t3］，［t1，t5］。其中，［t2］使診斷策略的費用估計值達到最小，故選擇［t2］為隔離故障f5的最優測試序列，并得到伴生故障集｛f2，f3｝，［f5］。

選擇t1為診斷故障模糊子集｛f2，f3｝的最優測試，從而得到完整的故障診斷策略。

通過式（6）計算，得到圖2的測試費用期望值為15.9。圖1所示信息熵算法得到的診斷策略的測試費用期望值為19.3。使用AO*算法及Rollout算法對相關性矩陣進行處理，得到測試期望值費用為15.9。本文方法得到的測試費用與AO*算法及Rollout算法相同。

圖2 本文方法的診斷策略Fig.2 Diagnostic strategy in this paper

3.2 實例分析

為說明方法的有效性，同時對比信息熵算法、Rollout算法與AO*算法的診斷效果，以導彈姿態穩定分系統［16］、艦炮制導彈藥控制系統［17］、衛星電源系統［18］等3個實際的測試性模型及相關性矩陣為例進行分析計算，計算結果如表2所示。

表2 測試費用期望值對比Table 1 Comparison of the expected text cost

由表2可知，在本文所列舉的3個案例中，單步和多步尋優結合的診斷策略構建方法在避免回溯操作的同時，計算結果優于信息熵算法，與Rollout算法及AO*算法的測試費用相同。

4 結束語

在診斷策略構建問題中，要使測試費用的期望值盡可能小，則先驗概率較大的故障應該對應較少的測試步驟和測試費用，所以應根據故障概率情況確定診斷策略構建方法。單步和多步尋優結合的診斷策略構建方法綜合考慮了測試費用、故障概率以及多步測試信息的影響，在避免回溯操作的同時能夠以較低的測試費用對裝備進行故障診斷和隔離，具有一定的理論和實際應用價值。