基于NSGA-3與改進(jìn)貝葉斯網(wǎng)絡(luò)模型的測(cè)試優(yōu)化選擇方法

韓露, 史賢俊, 翟禹堯

(海軍航空大學(xué) 岸防兵學(xué)院, 山東 煙臺(tái) 264000)

測(cè)試性是描述系統(tǒng)健康狀態(tài)可監(jiān)控和可測(cè)試難易程度的一種設(shè)計(jì)特性。針對(duì)裝備的電子設(shè)備開展測(cè)試性設(shè)計(jì),可提高裝備的故障檢測(cè)與隔離能力,減少重大事故的發(fā)生。在測(cè)試性設(shè)計(jì)過程中,確立裝備測(cè)試性模型后,需要針對(duì)模型進(jìn)行測(cè)試優(yōu)化選擇,其目的是得到最佳的測(cè)試組合。測(cè)試優(yōu)化選擇需要綜合考慮很多因素，如故障檢測(cè)率、隔離率、虛警率、漏檢率、測(cè)試成本等,從而以最低的成本滿足測(cè)試性需求。

測(cè)試優(yōu)化選擇是一種基于測(cè)試性模型的多目標(biāo)優(yōu)化問題。現(xiàn)階段大多學(xué)者的研究是基于相關(guān)性模型,這種模型又可依據(jù)是否考慮到不確定信息劃分為2種,第一種模型不考慮不確定信息,即認(rèn)為故障、測(cè)試間的關(guān)系是確定的;另外一種考慮到不確定信息,認(rèn)為故障測(cè)試間的關(guān)系是不確定的,測(cè)試是不可靠的。針對(duì)第一種相關(guān)性模型,雷華軍等建立了測(cè)試優(yōu)化選擇的數(shù)學(xué)模型[1],同時(shí)提出了一種改進(jìn)的量子進(jìn)化算法解決問題,算法收斂速度快,不會(huì)陷入局部極值;吳新鋒等提出了改進(jìn)二進(jìn)制粒子群遺傳算法,用粒子群進(jìn)化代替了代間復(fù)制,提高了算法搜索效率[2];蘇永定等構(gòu)造了衡量測(cè)試集優(yōu)劣程度的啟發(fā)式函數(shù),結(jié)合遺傳算法提出了一種用于測(cè)試選擇的遺傳搜索算法[3];宋森森首次應(yīng)用引力算法求解測(cè)試優(yōu)化選擇問題,并對(duì)其進(jìn)行了改進(jìn)[4]。針對(duì)第二種相關(guān)性模型,張貞對(duì)5種優(yōu)化算法進(jìn)行了分析,指出了分組編碼遺傳算法更適合解決電子系統(tǒng)測(cè)試選擇問題[5];葉曉慧等綜合了許多故障因素,提出一種動(dòng)態(tài)貪婪算法求解問題,適合于大型復(fù)雜系統(tǒng)的測(cè)試性設(shè)計(jì)[6];張士剛針對(duì)NP問題,提出采用遺傳算法與拉格朗日松弛算法進(jìn)行求解[7];當(dāng)前基于貝葉斯網(wǎng)絡(luò)模型的測(cè)試優(yōu)化選擇研究較少,其中陳希祥提出了一種解決方案,其在貝葉斯網(wǎng)絡(luò)模型基礎(chǔ)上獲取故障-測(cè)試相關(guān)性矩陣,后利用混合二進(jìn)制粒子群-遺傳算法求解問題[8],本質(zhì)上該優(yōu)化算法依舊基于相關(guān)性模型,貝葉斯網(wǎng)絡(luò)的作用主要為計(jì)算含有不確定信息的故障-測(cè)試矩陣。

目前針對(duì)測(cè)試優(yōu)化選擇的方法具有2個(gè)明顯的特征:①大都基于相關(guān)性模型開展工作;②將多個(gè)優(yōu)化目標(biāo)糅合成一個(gè)單目標(biāo)進(jìn)行研究,這些都帶來了一定的局限性。相關(guān)性模型簡(jiǎn)單但處理不確定信息能力差,且不具備學(xué)習(xí)能力,后期模型更新困難,而貝葉斯網(wǎng)絡(luò)模型不存在以上問題;其次單目標(biāo)優(yōu)化算法顯然也無法得到多目標(biāo)優(yōu)化問題的最優(yōu)解。

據(jù)此,本文引入了改進(jìn)貝葉斯網(wǎng)絡(luò)模型,模型建模難度降低,結(jié)構(gòu)接近實(shí)際物理結(jié)構(gòu),方便進(jìn)行測(cè)試優(yōu)化設(shè)計(jì)。并提出基于改進(jìn)貝葉斯網(wǎng)絡(luò)模型與NSGA-3的測(cè)試優(yōu)化選擇方法,通過NSGA-3的種群概念來確立貝葉斯網(wǎng)絡(luò)的結(jié)構(gòu),通過貝葉斯方法進(jìn)行參數(shù)學(xué)習(xí),確立條件概率表(conditional probability table,CPT)信息,進(jìn)而利用模型計(jì)算測(cè)試性評(píng)價(jià)指標(biāo)。應(yīng)用該方法可得到一組非支配解(Pareto最優(yōu)解),解決測(cè)試性設(shè)計(jì)過程中測(cè)試優(yōu)化選擇問題。

1 改進(jìn)的貝葉斯網(wǎng)絡(luò)測(cè)試性模型

1.1 貝葉斯網(wǎng)絡(luò)測(cè)試性模型

貝葉斯網(wǎng)絡(luò)是一種帶有概率注釋的有向無環(huán)圖,可以表示變量間的相互關(guān)系與聯(lián)合概率分布,可以據(jù)此特性建立貝葉斯網(wǎng)絡(luò)測(cè)試性模型來描述故障變量與測(cè)試變量間的關(guān)系,模型示意圖如圖1所示,模型主要由以下元素構(gòu)成:

故障有限集:F={f1,f2,…,fm};

可用測(cè)試的有限集:T={t1,t2,…,tn};

故障-測(cè)試相關(guān)關(guān)系P:條件概率表(CPT);

有向無環(huán)圖:GDA={F,T,P,E},其中E為連接線,表示變量間具有相關(guān)關(guān)系;

圖1 貝葉斯網(wǎng)絡(luò)測(cè)試性模型

圖中f1,t1的CPT信息如表1和表2所示。

表1 f1節(jié)點(diǎn)的條件概率表

表2 t1節(jié)點(diǎn)的條件概率表

貝葉斯網(wǎng)絡(luò)模型在不確定信息表達(dá)、概率推理、先驗(yàn)信息利用、模型自學(xué)習(xí)更新等方面具有優(yōu)勢(shì),但在測(cè)試性建模過程中較少被采用,究其原因主要是直接表示故障、測(cè)試相關(guān)關(guān)系,結(jié)構(gòu)復(fù)雜,計(jì)算量大,對(duì)數(shù)據(jù)量要求高;模型結(jié)構(gòu)偏離實(shí)際物理系統(tǒng),模型類似于黑箱,難以基于模型開展針對(duì)性的測(cè)試優(yōu)化設(shè)計(jì),且由于結(jié)構(gòu)偏離,部分指標(biāo)計(jì)算困難,如誤診率,對(duì)數(shù)據(jù)利用率相對(duì)不高。

1.2 改進(jìn)的貝葉斯網(wǎng)絡(luò)模型

根據(jù)前面對(duì)貝葉斯網(wǎng)絡(luò)模型的分析,為改善模型性能,提出了改進(jìn)的貝葉斯網(wǎng)絡(luò)模型。該模型融入了多信號(hào)流圖模型的信號(hào)思想,以信號(hào)節(jié)點(diǎn)替代測(cè)試節(jié)點(diǎn),原有的故障、測(cè)試相關(guān)關(guān)系轉(zhuǎn)變?yōu)楣收稀⑿盘?hào)相關(guān)關(guān)系。連接線連接各信號(hào)節(jié)點(diǎn),模型以此方式表征信號(hào)傳遞。某型裝備的多信號(hào)流圖模型如圖2所示,該裝備的改進(jìn)貝葉斯網(wǎng)絡(luò)如圖3所示。

圖2 多信號(hào)流圖模型示意圖

圖3 改進(jìn)的貝葉斯網(wǎng)絡(luò)模型

改進(jìn)的貝葉斯網(wǎng)絡(luò)模型由以下元素構(gòu)成:

故障有限集:F={f1,f2,…,fm};

故障-測(cè)試相關(guān)關(guān)系P:條件概率表(CPT);

有向無環(huán)圖:GDA={F,S,P,E},其中E為連接線。

1.3 確立模型結(jié)構(gòu)

1) 捋清故障源,確立每個(gè)故障源所含有的故障信號(hào),將故障源與信號(hào)關(guān)聯(lián)起來;

2) 確定故障信號(hào)傳遞路徑,即不同故障源所含有的故障信號(hào)間的聯(lián)系,將同一路徑上的信號(hào)關(guān)聯(lián)起來;

3) 將故障源作為故障節(jié)點(diǎn),故障信號(hào)作為信號(hào)節(jié)點(diǎn),關(guān)聯(lián)關(guān)系用連接線E建立,由此貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)初步確立;

4) 獲取測(cè)試選擇方案,此時(shí)信號(hào)節(jié)點(diǎn)分為2種:①節(jié)點(diǎn)處布置有測(cè)試;②節(jié)點(diǎn)處未布置測(cè)試;

5) 由前至后,將未布置測(cè)試的信號(hào)節(jié)點(diǎn)刪除,將其父節(jié)點(diǎn)依信號(hào)傳遞路徑,連接到下一個(gè)信號(hào)節(jié)點(diǎn),其中信號(hào)傳遞路徑也是故障傳遞路徑;

6) 全部未布置測(cè)試的信號(hào)節(jié)點(diǎn)刪除后,貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)確立,某型裝備的結(jié)構(gòu)確立過程如圖4所示。

圖4 某型裝備的模型結(jié)構(gòu)確立過程

1.4 確立模型參數(shù)

改進(jìn)的貝葉斯網(wǎng)絡(luò)模型的結(jié)構(gòu)根據(jù)測(cè)試選擇而確定,模型結(jié)構(gòu)確定后,進(jìn)行貝葉斯網(wǎng)絡(luò)參數(shù)學(xué)習(xí),即利用給定的故障樣本數(shù)據(jù)去學(xué)習(xí)網(wǎng)絡(luò)的概率分布,最終得到節(jié)點(diǎn)的CPT信息,進(jìn)而建立完整模型,后續(xù)可利用該模型計(jì)算測(cè)試性指標(biāo)。

1.4.1 故障、測(cè)試樣本數(shù)據(jù)

1) 裝備正常運(yùn)行過程中,監(jiān)測(cè)測(cè)點(diǎn)位置的信號(hào),在多數(shù)情況下,信號(hào)隨機(jī)誤差服從正態(tài)分布;

2) 根據(jù)測(cè)點(diǎn)處待選測(cè)試的性能,確定測(cè)試閾值。后進(jìn)行故障注入實(shí)驗(yàn),故障在測(cè)點(diǎn)處以信號(hào)的形式反映,超出閾值,則該測(cè)點(diǎn)處的備選測(cè)試檢測(cè)到故障。將故障、信號(hào)信息記錄到樣本數(shù)據(jù)中,遍歷所有可選測(cè)試,得到一條樣本數(shù)據(jù)。

3) 重復(fù)上述過程,得到故障、測(cè)試樣本數(shù)據(jù)集。樣本數(shù)據(jù)集中還含有部分無故障狀態(tài)下的信號(hào)信息,獲取方式同步驟1)、2)。

信號(hào)隨機(jī)誤差分布與測(cè)試閾值的關(guān)系如圖5所示,數(shù)據(jù)集如表3所示。

表3 故障、測(cè)試樣本集

圖5 信號(hào)分布與測(cè)試閾值關(guān)系圖

1.4.2 參數(shù)學(xué)習(xí)

采用貝葉斯方法進(jìn)行參數(shù)學(xué)習(xí),該方法可以有效綜合先驗(yàn)知識(shí)與樣本數(shù)據(jù)來更新參數(shù)。方法簡(jiǎn)述如下。

(1)

(i=1,2,…,n;j=1,2,…,qi;k=1,2,…,ri)

給定樣本集D=(D1,D2,…,Dm),D的一個(gè)元素Di表示樣本的一個(gè)觀測(cè)值,為一個(gè)案例。貝葉斯網(wǎng)絡(luò)參數(shù)學(xué)習(xí)實(shí)質(zhì)為給定樣本D,計(jì)算后驗(yàn)分布p(θs|D,Sh)。

(2)

p(θij|Sh)服從先驗(yàn)Dirichlet分布Dir(θij|αij1,αij2,…αijri),得到后驗(yàn)分布

(3)

參數(shù)向量θs計(jì)算完畢,利用θs對(duì)案例進(jìn)行預(yù)測(cè),如預(yù)測(cè)案例DN+1

(4)

信號(hào)節(jié)點(diǎn)通過上述參數(shù)學(xué)習(xí)得到CPT信息;而故障節(jié)點(diǎn)CPT信息是在完成參數(shù)學(xué)習(xí)后,通過先驗(yàn)知識(shí)直接給出。究其原因?yàn)榻M件故障率相對(duì)于正常狀態(tài)來說是極低的,而考慮到學(xué)習(xí)效率,樣本數(shù)據(jù)是主要由故障狀態(tài)下的數(shù)據(jù)組成的,參數(shù)學(xué)習(xí)得到的故障節(jié)點(diǎn)故障率是極度偏高的,因此需要在完成參數(shù)學(xué)習(xí)后,再通過先驗(yàn)信息給出節(jié)點(diǎn)CPT來進(jìn)行替換。

1.5 測(cè)試性指標(biāo)計(jì)算

(5)

系統(tǒng)對(duì)故障fj的故障檢測(cè)率為FDRj

(6)

系統(tǒng)的故障檢測(cè)率FDR

(7)

系統(tǒng)的故障隔離率FIR

(8)

故障虛警率FAR

(9)

由于改進(jìn)貝葉斯網(wǎng)絡(luò)模型的信號(hào)節(jié)點(diǎn),可以據(jù)此計(jì)算系統(tǒng)的故障誤診率

FMR=

(10)

測(cè)試成本C

(11)

式中:C(ti)表示執(zhí)行測(cè)試ti的成本;Tc表示被選中的測(cè)試集合。

2 NSGA-3優(yōu)化算法

從測(cè)試性指標(biāo)方面看,測(cè)試優(yōu)化選擇問題是一種多目標(biāo)優(yōu)化問題,需要確定使得多項(xiàng)測(cè)試性指標(biāo)達(dá)到綜合最優(yōu)的一種方案。NSGA-3算法[9-11]是一種多目標(biāo)優(yōu)化算法,由于其解決了NSGA-2存在的收斂性與多樣性不理想的問題,可以更好地解決這種多目標(biāo)優(yōu)化問題。

2.1 Pareto最優(yōu)解

NSGA-3算法最后得到的解是Pareto最優(yōu)解。以最小化問題為例,該解集定義如下:

對(duì)于任意2個(gè)決策變量xa,xb∈xf,xf為可行解集合:

1) ?i={1,2,…,k}:fi(xa)≤fi(xb)

2) ?i={1,2,…,k}:fi(xa)

當(dāng)且僅當(dāng)滿足以上2個(gè)條件時(shí),稱xa支配xb。在決策空間中,存在一個(gè)決策向量集X,X不被任何決策向量支配,則X稱為Pareto最優(yōu)解。

2.2 參考點(diǎn)及相關(guān)概念

NSGA-3引入了參考點(diǎn)來更好地執(zhí)行精英保留策略,使得解在目標(biāo)空間內(nèi)更加均勻,其概念及計(jì)算方法如下:

利用邊界交叉構(gòu)造權(quán)重的方法在超平面上均勻地產(chǎn)生C個(gè)點(diǎn),這些點(diǎn)就是參考點(diǎn)。設(shè)置方法如圖6所示。NSGA-3算法通過個(gè)體關(guān)聯(lián)參考點(diǎn)的方法來衡量目標(biāo)空間的均勻程度。

圖6 參考點(diǎn)示意圖

參考點(diǎn)是建立在超平面上的,超平面計(jì)算方法簡(jiǎn)述如下:

1) 標(biāo)準(zhǔn)化:首先選取當(dāng)前種群中每一維目標(biāo)函數(shù)的最小值,計(jì)算出理想點(diǎn),以理想點(diǎn)為原點(diǎn),以目標(biāo)函數(shù)為坐標(biāo)軸,根據(jù)(12)式將個(gè)體標(biāo)準(zhǔn)化;

3) 依據(jù)這些極值點(diǎn)構(gòu)建超平面,超平面與坐標(biāo)軸的交點(diǎn)即為截距ai,超平面如圖7所示。

圖7 超平面示意圖

(12)

(13)

個(gè)體關(guān)聯(lián)參考點(diǎn)的方法如下:

1) 構(gòu)建參考點(diǎn)向量,即坐標(biāo)系中參考點(diǎn)到原點(diǎn)的連線;

2) 對(duì)種群中每個(gè)個(gè)體遍歷參考向量,找到距離個(gè)體最近的參考點(diǎn),記下關(guān)聯(lián)信息與距離,個(gè)體與參考點(diǎn)完成關(guān)聯(lián),關(guān)聯(lián)描述如圖8所示。

圖8 個(gè)體關(guān)聯(lián)參考點(diǎn)示意圖

2.3 NSGA-3算法實(shí)施步驟

1) 確定種群規(guī)模N,初始化種群;

2) 確立理想點(diǎn),對(duì)所有個(gè)體的目標(biāo)值進(jìn)行歸一化,計(jì)算出極值點(diǎn),構(gòu)建超平面,確定參考點(diǎn);

3) 對(duì)種群進(jìn)行非支配排序;

4) 用遺傳算子對(duì)種群進(jìn)行操作,得到規(guī)模為N的子種群;

圖9 NSGA-3算法流程圖

5) 合并2個(gè)種群,得到規(guī)模為2N的種群,并進(jìn)行快速非支配排序,確定非支配層級(jí);

6) 按照非支配層級(jí)由小到大的順序依次將個(gè)體加入下一代種群中,直至種群規(guī)模為N,此時(shí)的非支配層級(jí)為L;

7) 由于多數(shù)情況下L層的個(gè)體無法全部加入 中,需要在L層中選擇一部分個(gè)體放入。首先將1～L層個(gè)體關(guān)聯(lián)到參考點(diǎn),然后尋找到關(guān)聯(lián)1～L-1層個(gè)體最少的參考點(diǎn),最后從L層中選擇一個(gè)關(guān)聯(lián)到該參考點(diǎn)的個(gè)體加入,重復(fù)執(zhí)行該步驟,直至種群 規(guī)模為N,此時(shí)用種群 替換種群;

8) 重復(fù)步驟4)～8),直至完成規(guī)定代數(shù),最終得到Pareto最優(yōu)解,解碼解集可得測(cè)試方案。

3 實(shí)例分析

以導(dǎo)彈上的機(jī)載雷達(dá)某組件為例,該組件的結(jié)構(gòu)示意圖如圖10所示,初步建立的改進(jìn)貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)如圖11所示。

圖10 組件的結(jié)構(gòu)示意圖

圖11 雷達(dá)組件的改進(jìn)貝葉斯網(wǎng)絡(luò)模型

該組件的故障信息及部分故障、測(cè)試樣本集如表4、表5所示,測(cè)試成本如表6所示。

表4 故障信息表

表5 故障、測(cè)試樣本表

表6 測(cè)試成本表

系統(tǒng)測(cè)試性設(shè)計(jì)要求:故障檢測(cè)率不低于95%,模糊度為1的故障隔離率不低于70%;測(cè)試優(yōu)化選擇選定4個(gè)目標(biāo)函數(shù):系統(tǒng)的虛警率A(x),系統(tǒng)的誤診率M(x),測(cè)試成本C(x),測(cè)點(diǎn)數(shù)量D(x),要求4個(gè)目標(biāo)函數(shù)達(dá)到綜合最小。針對(duì)該實(shí)例,測(cè)試優(yōu)化選擇問題的數(shù)學(xué)模型如(14)式所示。

(14)

NSGA-3算法參數(shù)如表7所示,貝葉斯網(wǎng)絡(luò)參數(shù)學(xué)習(xí)樣本數(shù)量設(shè)置為2 000組。

表7 參數(shù)設(shè)置

執(zhí)行算法后,得到非支配等級(jí)最高的Pareto解集如表8所示,同時(shí)記錄該解集對(duì)應(yīng)的測(cè)試性指標(biāo)于表8中。

表8 Pareto解集及其對(duì)應(yīng)的測(cè)試性指標(biāo)

測(cè)試組合中1表示該測(cè)試被選擇,0表示測(cè)試未被選擇。側(cè)重于不同需求,可從表8中選擇不同的解作為測(cè)試優(yōu)化選擇方案,側(cè)重于不同需求的測(cè)試組合如表9所示,研發(fā)人員可根據(jù)需求選取不同的測(cè)試選擇方案。

表9 測(cè)試優(yōu)化選擇方案

4 結(jié) 論

本文闡述了改進(jìn)貝葉斯網(wǎng)絡(luò)模型,該模型將信號(hào)概念引入貝葉斯網(wǎng)絡(luò)中,降低了貝葉斯網(wǎng)絡(luò)的建模難度,也使得模型結(jié)構(gòu)趨近于實(shí)際物理結(jié)構(gòu)。同時(shí),模型可發(fā)揮貝葉斯網(wǎng)絡(luò)對(duì)不確定信息的表達(dá)和處理能力,測(cè)試性指標(biāo)計(jì)算準(zhǔn)確。模型在結(jié)構(gòu)與指標(biāo)計(jì)算方面都更有利于研究人員進(jìn)行測(cè)試優(yōu)化設(shè)計(jì)工作。本文改變了之前將多目標(biāo)問題轉(zhuǎn)化為單目標(biāo)問題的做法,直接在改進(jìn)貝葉斯網(wǎng)絡(luò)模型的基礎(chǔ)上,利用NSGA-3多目標(biāo)優(yōu)化算法計(jì)算測(cè)試選擇方案,在案例中可以看到,算法得到的Pareto最優(yōu)解給出了面向不同需求的測(cè)試選擇方案。給出的方案也驗(yàn)證了本文方法的有效性與可用性。