基于禁忌搜索算法的故障診斷策略優(yōu)化

張 睿， 叢 華， 劉遠(yuǎn)宏， 馮輔周

(1. 陸軍裝甲兵學(xué)院車輛工程系， 北京 100072； 2. 武警工程大學(xué)裝備管理與保障學(xué)院， 陜西 西安 710086)

制定合理的故障診斷策略是武器裝備測試性設(shè)計(jì)的重要內(nèi)容之一。故障診斷策略是指綜合考慮規(guī)定約束、目標(biāo)和有關(guān)影響因素而確定的用于隔離產(chǎn)品故障的測試步驟或順序[1]。合理的測試步驟或順序不僅可提升故障診斷效率，而且可降低裝備維修保障的成本。診斷策略優(yōu)化是一種典型的NP-Complete問題，傳統(tǒng)的優(yōu)化方法有貪婪搜索[2]、AO*搜索[2]、Rollout信息啟發(fā)式[3-4]和基于啟發(fā)式算法[5-6]。其中：貪婪搜索算法只利用了單步信息進(jìn)行啟發(fā)式搜索，得到的策略是局部最優(yōu)解，優(yōu)化效果較差；Rollout信息啟發(fā)式算法將貪婪搜索作為基準(zhǔn)策略進(jìn)行迭代搜索，獲得的是近似全局最優(yōu)解；AO*搜索算法是進(jìn)行全局最優(yōu)搜索，但搜索過程中擴(kuò)展節(jié)點(diǎn)和存儲(chǔ)路徑較多，造成計(jì)算時(shí)間較長，對(duì)于復(fù)雜系統(tǒng)并不適用；基于啟發(fā)式算法使用的多為現(xiàn)代啟發(fā)式優(yōu)化算法，優(yōu)化效果較好，但收斂性不足，容易陷入局部最優(yōu)。

禁忌搜索算法是一種全局逐步尋優(yōu)的算法，其利用禁忌記憶表和藐視準(zhǔn)則跳出局部最優(yōu)，在全局范圍內(nèi)逐步逼近全局最優(yōu)解，通過設(shè)置禁忌記憶表對(duì)某些局部最優(yōu)解進(jìn)行禁忌，具有“容錯(cuò)”的特點(diǎn)，跳出局部最優(yōu)解的能力較強(qiáng)，可以避免在搜索過程中陷入局部最優(yōu)解[7-8]，已被用于解決多種NP-Complete問題。筆者借鑒禁忌搜索算法解決NP-Complete問題的思路，利用其中模擬人記憶方式的思想，在診斷策略優(yōu)化設(shè)計(jì)過程中通過構(gòu)造優(yōu)化目標(biāo)函數(shù)、設(shè)置禁忌表與確定禁忌長度，進(jìn)行全局范圍尋優(yōu)，以解決傳統(tǒng)方法優(yōu)化性能較差等問題。

1 故障診斷策略優(yōu)化問題描述

1.1 基本信息

1) 狀態(tài)集合F。假設(shè)系統(tǒng)內(nèi)有m個(gè)故障狀態(tài)，并與無故障狀態(tài)f0共同組成了系統(tǒng)的狀態(tài)集合F={f0,f1,…,fm}。

3) 系統(tǒng)內(nèi)測試集合T。假設(shè)系統(tǒng)內(nèi)有n個(gè)測試點(diǎn)t1,t2,…,tn，T={t1,t2,…,tn}，各個(gè)測試均為二值測試，即只有“通過”和“不通過”2種測試結(jié)果。

4) 測試費(fèi)用集合C。C={c1,c2,…,cn},表示執(zhí)行某一測試時(shí)所花費(fèi)的費(fèi)用，不隨測試順序的改變而改變。

5) 故障-測試相關(guān)性矩陣D。它是進(jìn)行診斷決策優(yōu)化的基礎(chǔ)，能夠表示故障與測試之間的相關(guān)關(guān)系。矩陣中元素dij=1時(shí)，表示故障fi發(fā)生時(shí)能夠被測試點(diǎn)tj檢測。無故障狀態(tài)f0用零向量表示。

1.2 診斷策略的優(yōu)化目標(biāo)

PATTIPATI等[9]將診斷策略優(yōu)化目標(biāo)進(jìn)行了簡化，提出平均測試費(fèi)用最低的優(yōu)化目標(biāo)，省略了不確定風(fēng)險(xiǎn)及影響因素，著重考慮測試費(fèi)用這一影響因素，以便能夠?qū)y試順序進(jìn)行定量化評(píng)判。如果生成的測試順序?qū)?yīng)的測試費(fèi)用越少，則說明該測試順序越優(yōu)，因此將診斷策略優(yōu)化目標(biāo)確定為

(1)

式中：q為隔離第i個(gè)故障狀態(tài)所需要的測試數(shù)目。

2 優(yōu)化方法設(shè)計(jì)與實(shí)現(xiàn)

2.1 編碼

對(duì)可選測試集中各測點(diǎn)進(jìn)行編碼，生成對(duì)應(yīng)的n維測試順序向量，n為可選測試集中測點(diǎn)個(gè)數(shù)。向量中每個(gè)元素為一個(gè)決策變量，取值為0～1，變量取值越大，表明該變量對(duì)應(yīng)的測試點(diǎn)的執(zhí)行順序越靠前。以圖1中4維測試順序向量為例進(jìn)行說明。

(1)算法針對(duì)的是多站多外輻射源場景，對(duì)于單站多外輻射源場景和多站單外輻射源場景同樣適用，具有較高的通用性.

圖1中：各個(gè)測點(diǎn)在測試順序向量中的決策變量取值為{0.1,0.2,0.3,0.5}，根據(jù)各變量值的大小進(jìn)行排序,獲得各個(gè)測點(diǎn)的執(zhí)行順序?yàn)閠4→t3→t2→t1。

2.2 適應(yīng)度函數(shù)

測試順序向量代表不同的測試執(zhí)行順序Tk，執(zhí)行每個(gè)測試后會(huì)根據(jù)故障-測試相關(guān)性矩陣對(duì)故障模糊集進(jìn)行隔離，最終隔離到每一個(gè)獨(dú)立的故障狀態(tài)。在隔離過程中，生成的隔離矩陣

I能夠表示隔離故障狀態(tài)時(shí)所執(zhí)行的測試，當(dāng)I中元素αij=1時(shí)，表示隔離第i個(gè)故障狀態(tài)時(shí)執(zhí)行了第j個(gè)測試。不同的測試順序向量對(duì)應(yīng)不同的隔離矩陣，根據(jù)隔離矩陣和式(1)，構(gòu)建適應(yīng)度函數(shù)為

f(Tk)=P×I×CT，

(2)

式中：P=[p0p1…pm],為故障狀態(tài)的先驗(yàn)概率向量；C=[c1c2…cn],為測試執(zhí)行費(fèi)用向量。

例:4階D矩陣為

根據(jù)圖1中的測試順序?qū)m應(yīng)度計(jì)算進(jìn)行說明。各個(gè)故障狀態(tài)的先驗(yàn)概率向量P=[0.8600.0560.0430.041],測試執(zhí)行成本向量C=[10.520.5]。

按照?qǐng)D1所示的測試執(zhí)行順序進(jìn)行故障隔離，則隔離矩陣

根據(jù)式(2)計(jì)算該測試執(zhí)行順序的適應(yīng)度，為

f(T)=[0.8600.0560.0430.041]×

2.3 禁忌記憶表

禁忌記憶表將每代搜索過程中所生成的本代最優(yōu)解的變化方式進(jìn)行記憶，并在今后一段時(shí)間內(nèi)不能被作為產(chǎn)生新解的方式，從而避免重復(fù)搜索，達(dá)到跳出局部最優(yōu)解的目的。禁忌記憶表是一個(gè)n階矩陣，與解決問題的維數(shù)n相同，每個(gè)元素的位置用于存放對(duì)應(yīng)禁忌解的禁忌迭代次數(shù)。禁忌迭代次數(shù)由禁忌長度來確定，解禁時(shí)根據(jù)“先入先出”的原則，對(duì)表中的禁忌解逐一進(jìn)行解禁。王凌[10]經(jīng)過大量禁忌長度對(duì)優(yōu)化效果的影響試驗(yàn)得出結(jié)論：當(dāng)禁忌長度為解決問題維數(shù)的2倍時(shí)，既能保證全局尋優(yōu)能力，又有較好的求解效率。因此，本文選取禁忌長度為解決問題維數(shù)的2倍。

2.4 藐視準(zhǔn)則

運(yùn)用藐視準(zhǔn)則可以避免錯(cuò)過全局最優(yōu)解的情況。藐視準(zhǔn)則是將候選解中的最優(yōu)個(gè)體與先前的最優(yōu)個(gè)體進(jìn)行比較，如果該個(gè)體優(yōu)于先前的最優(yōu)解個(gè)體，且產(chǎn)生該解的移動(dòng)方式為禁忌對(duì)象，則無視禁忌長度，對(duì)該個(gè)體進(jìn)行解禁，并將該解作為下一代的初始最優(yōu)解。

2.5 基于禁忌搜索算法的診斷策略優(yōu)化流程

圖2為基于禁忌搜索算法的診斷策略優(yōu)化流程，具體步驟如下：

1) 初始化禁忌搜索算法中各項(xiàng)參數(shù)，包括候選解大小、禁忌長度及最大迭代次數(shù)；

2) 根據(jù)可選測試集對(duì)每個(gè)測試進(jìn)行編碼，隨機(jī)生成初代最優(yōu)解；

3) 根據(jù)最優(yōu)解，隨機(jī)將某2個(gè)測試順序進(jìn)行對(duì)調(diào)，生成候選解集，并計(jì)算出每個(gè)候選解個(gè)體的適應(yīng)度，從中選取最優(yōu)的個(gè)體作為最優(yōu)解；

4) 將生成最優(yōu)解的測試對(duì)調(diào)方式存儲(chǔ)到禁忌記憶表中，根據(jù)禁忌長度對(duì)該對(duì)調(diào)方式進(jìn)行解禁；

5) 依據(jù)藐視準(zhǔn)則，將本代最優(yōu)解與歷代最優(yōu)解進(jìn)行比較，并判斷該方式是否存在于禁忌記憶表，如果本代最優(yōu)解優(yōu)于歷代最優(yōu)解,且又存在于禁忌記憶表中，則對(duì)該對(duì)調(diào)方式進(jìn)行解禁；

6) 判斷當(dāng)前迭代數(shù)是否達(dá)到最大迭代次數(shù)，若達(dá)到，則停止搜索，輸出最優(yōu)解，否則重復(fù)步驟3)-5)。

3 案例分析

3.1 方法驗(yàn)證

對(duì)文獻(xiàn)[9]中的實(shí)例進(jìn)行優(yōu)化。通過與傳統(tǒng)的信息啟發(fā)式方法優(yōu)化結(jié)果進(jìn)行對(duì)比，驗(yàn)證基于禁忌搜索算法故障診斷策略優(yōu)化方法的有效性。該實(shí)例系統(tǒng)具有6個(gè)系統(tǒng)狀態(tài)，其中包括5個(gè)故障狀態(tài)和1個(gè)正常狀態(tài)。系統(tǒng)內(nèi)測試數(shù)目為5，則算法中的個(gè)體維度為5, 并假設(shè)所有測試費(fèi)用均為1。根據(jù)文獻(xiàn)[10]選取各個(gè)參數(shù)的準(zhǔn)則，候選解大小一般不大于所求解問題個(gè)體維度平方的1/2，禁忌長度一般選定為所求解問題個(gè)體維度的2倍，相關(guān)參數(shù)設(shè)置如表1所示。

表1 禁忌搜索算法相關(guān)參數(shù)

采用基于禁忌搜索算法和傳統(tǒng)的信息啟發(fā)式方法優(yōu)化得到的測試執(zhí)行順序分別如圖3、4所示，執(zhí)行費(fèi)用分別為2.234和2.827?？梢钥闯觯号c采用傳統(tǒng)的信息啟發(fā)式方法相比，采用基于禁忌搜索算法得到的測試執(zhí)行順序所需花費(fèi)的費(fèi)用少，測試執(zhí)行成本降低了20.9%。

圖5為采用上述2種方法得到的歷代最優(yōu)個(gè)體的適應(yīng)度變化曲線?？梢钥闯觯航伤阉魉惴ㄔ诘?5代左右開始收斂，收斂速度比基于信息啟發(fā)式方法快，跳出局部最優(yōu)解的能力更強(qiáng)。

上述對(duì)比結(jié)果表明：基于禁忌搜索算法的故障診斷決策優(yōu)化方法的全局優(yōu)化能力更強(qiáng)，不易陷入局部最優(yōu)解，所得的優(yōu)化結(jié)果更優(yōu)。

3.2 實(shí)例應(yīng)用

將該方法用于某型裝備液壓操縱系統(tǒng)的診斷策略優(yōu)化。該系統(tǒng)由主泵、精度濾油器、主定壓閥、換擋緩沖閥、減壓閥、變速轉(zhuǎn)閥、2個(gè)離合器和3個(gè)制動(dòng)器組成，由于該系統(tǒng)要求將故障定位到部件級(jí)，因此取組成部件故障為各個(gè)故障狀態(tài)，系統(tǒng)內(nèi)有11個(gè)組成部件，則部件故障狀態(tài)劃分為f1，f2，…，f11，部件故障狀態(tài)包含可能發(fā)生的故障，部件故障對(duì)應(yīng)關(guān)系如表2所示。

表2 部件故障對(duì)應(yīng)關(guān)系

系統(tǒng)內(nèi)共有8個(gè)可選測試，每個(gè)測試的執(zhí)行費(fèi)用均為1。經(jīng)查詢文獻(xiàn)[11]，得到各個(gè)零部件的故障狀態(tài)的先驗(yàn)概率向量P=10-2×[0.109 0.099 2.154 1.182 1.575 5.295 0.925 3 0.925 3 0.578 5 0.578 5 0.578 5]，正常狀態(tài)下工作的先驗(yàn)概率為0.87。該液壓操縱系統(tǒng)的故障-測試相關(guān)性矩陣

禁忌搜索算法中各項(xiàng)參數(shù)均由測試數(shù)目決定，該裝備系統(tǒng)中測試數(shù)目為8，禁忌搜索算法的相關(guān)參數(shù)如表3所示。優(yōu)化后的測試執(zhí)行順序以診斷樹的形式來表現(xiàn)，如圖6所示，所花費(fèi)用為3.9431。該優(yōu)化結(jié)果不僅減少了故障診斷成本，且能為維修人員提供故障診斷與排除指導(dǎo)意見，解決以何種順序排除故障的問題，避免盲目排除，最終達(dá)到提高維修保障及決策效率的目的。

表3 禁忌搜索算法相關(guān)參數(shù)

4 結(jié)論

針對(duì)故障診斷策略傳統(tǒng)優(yōu)化方法存在全局優(yōu)化能力較差的問題，筆者提出了基于禁忌搜索算法的故障診斷策略優(yōu)化方法，通過優(yōu)化效果與適應(yīng)度對(duì)比試驗(yàn)，證明該方法具有較強(qiáng)的跳出局部最優(yōu)能力，收斂性好，可有效降低故障診斷的測試成本，具有一定的工程應(yīng)用價(jià)值。