基于混合離散二進(jìn)制粒子群-遺傳算法的測(cè)試配置方法研究

，，

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

0 引言

測(cè)試性建模是對(duì)系統(tǒng)中故障-測(cè)試信息與功能信息流向的一種圖示或數(shù)學(xué)描述，選擇一種好的測(cè)試性模型是進(jìn)行測(cè)試性分析與設(shè)計(jì)的前提[1]。一個(gè)好的測(cè)試性模型應(yīng)既能夠體現(xiàn)系統(tǒng)的物理結(jié)構(gòu)組成和功能信息流向,又可以描述系統(tǒng)故障與測(cè)試之間的邏輯關(guān)系和對(duì)測(cè)試資源的占用關(guān)系等。為了提高系統(tǒng)的測(cè)試性指標(biāo)，建模人員在建立系統(tǒng)測(cè)試性模型時(shí)通常會(huì)設(shè)置大量的測(cè)試。目前系統(tǒng)的測(cè)試配置工作基本上都由建模人員憑借經(jīng)驗(yàn)完成，由于大型復(fù)雜系統(tǒng)的故障模式數(shù)量極多，若為每個(gè)故障模式都設(shè)置測(cè)試，對(duì)此測(cè)試性模型進(jìn)行分析必然會(huì)使系統(tǒng)的測(cè)試性指標(biāo)如：故障檢測(cè)率(fault detection rate，F(xiàn)DR)和故障隔離率(fault isolation rate，F(xiàn)IR)等達(dá)到最高[2]。但復(fù)雜的測(cè)試性模型增加了整個(gè)測(cè)試性分析工作的難度，過(guò)多的冗余測(cè)試大幅降低了整個(gè)系統(tǒng)的診斷效率，根據(jù)此模型對(duì)系統(tǒng)進(jìn)行設(shè)計(jì)和開(kāi)發(fā)也會(huì)產(chǎn)生一系列問(wèn)題，如：增加系統(tǒng)的設(shè)計(jì)難度、增加全壽命周期費(fèi)用、提高研發(fā)成本等。因此有必要解決測(cè)試性建模過(guò)程中測(cè)試的優(yōu)化配置問(wèn)題，簡(jiǎn)化測(cè)試性模型，以最簡(jiǎn)約有效的方案最大程度地檢測(cè)并隔離系統(tǒng)中的故障。

基于以上問(wèn)題，本文提出了一種混合離散二進(jìn)制粒子群-遺傳算法(binary particle swarm optimization-genetic algorithm，BPSO-GA)對(duì)復(fù)雜系統(tǒng)測(cè)試性建模過(guò)程中測(cè)試優(yōu)化配置問(wèn)題進(jìn)行求解。

1 測(cè)試優(yōu)化配置的數(shù)學(xué)描述與建模

1.1 故障可達(dá)性矩陣

測(cè)試性建模工作主要是面對(duì)系統(tǒng)的故障空間，然后為故障配置相應(yīng)的測(cè)試。目的是建立系統(tǒng)內(nèi)部各個(gè)功能單元之間的故障傳播關(guān)系和故障與測(cè)試資源的邏輯關(guān)系[3]。根據(jù)系統(tǒng)的組成結(jié)構(gòu)和故障模式、影響及危害性分析(failure mode, effects and criticality analysis，F(xiàn)MECA)可知，系統(tǒng)內(nèi)部的故障模式存在著一定的傳播關(guān)系，故障模式之間的這種傳播關(guān)系可以用故障可達(dá)性矩陣表示。假設(shè)系統(tǒng)故障流圖G=中包含n個(gè)故障模式節(jié)點(diǎn):FM={fm1,fm2,…,fmn}；m條邊:E={|fmi∈FM,fmj∈FM}。有序?qū)?fmi,fmj>表示故障模式節(jié)點(diǎn)fmi到fmj有一條有向邊，則定義n階方陣f(G)=[fij]為系統(tǒng)的故障鄰接矩陣，其中：

(1)

定義故障可達(dá)性矩陣F(G)如下：若故障模式fmi可以引起故障模式fmj發(fā)生，即從fmi到fmj存在一條通路，則n階方陣F(G)=[Fij]稱為系統(tǒng)的故障可達(dá)性矩陣，其中：

(2)

下面給出由故障鄰接矩陣求取故障可達(dá)性矩陣的一般方法[4]：

1)對(duì)故障鄰接矩陣f(G)進(jìn)行如下變換：

(3)

式中,R是表示任意兩故障模式之間通路數(shù)目的矩陣。

2)將矩陣R中的全部非零元素置換為1，為零的元素保持不變，就得到故障可達(dá)性矩陣，其中：

(4)

1.2 測(cè)試配置方案

系統(tǒng)測(cè)試配置方案可用n維向量表示：

VT=[v1,v2,…vn]

(5)

其中:vi=1表示為故障模式fmi配置測(cè)試；vi=0表示不為故障模式fmi配置測(cè)試。將VT中vi=1的個(gè)數(shù)記為m，表示為系統(tǒng)配置測(cè)試的總數(shù)量。其中：系統(tǒng)最優(yōu)測(cè)試配置方案應(yīng)為最小完備測(cè)試集合，即去除該集合中任意一個(gè)測(cè)試就不再滿足測(cè)試性參數(shù)指標(biāo)要求。

1.3 故障-測(cè)試相關(guān)性矩陣

測(cè)試性模型具有圖示形式和矩陣形式兩種表示方法,故障-測(cè)試相關(guān)性矩陣以測(cè)試性圖示模型為基礎(chǔ)進(jìn)行相關(guān)性分析得到, 故障-測(cè)試相關(guān)性矩陣便是對(duì)系統(tǒng)功能單元故障與測(cè)試資源相關(guān)性的數(shù)學(xué)描述。根據(jù)測(cè)試配置方案VT為系統(tǒng)配置測(cè)試，構(gòu)建故障與測(cè)試資源的邏輯關(guān)系，故障-測(cè)試相關(guān)性矩陣Dn×m可由下式計(jì)算得到：

(6)

在建模過(guò)程中，通常為系統(tǒng)作下列假設(shè)：(1)被測(cè)對(duì)象僅有兩種狀態(tài)：正常狀態(tài)和故障狀態(tài)。被測(cè)對(duì)象在正常狀態(tài)下無(wú)故障可以正常工作；反之被測(cè)對(duì)象不能正常工作。(2)當(dāng)被測(cè)對(duì)象處于故障狀態(tài)時(shí)，則假設(shè)僅有一個(gè)組成元件(或部件)發(fā)生了故障。(3)某一組成單元發(fā)生了故障，在信息流動(dòng)方向可達(dá)的各個(gè)測(cè)試點(diǎn)上，測(cè)量的有效性是一樣的。(4)每個(gè)測(cè)試的測(cè)試結(jié)果都是二值且可靠的，各測(cè)試之間相互獨(dú)立。則故障-測(cè)試相關(guān)性矩陣內(nèi)的元素：若故障模式fmi與測(cè)試tj相關(guān)，則dij=1，否則dij=0。

1.4 測(cè)試性參數(shù)指標(biāo)

1.4.1 故障檢測(cè)率

故障檢測(cè)率描述了系統(tǒng)對(duì)故障模式的檢測(cè)能力[5]，可根據(jù)故障-測(cè)試相關(guān)性矩陣計(jì)算得到：

(7)

式中,LD為矩陣Dn×m中非全零行向量個(gè)數(shù)。若考慮各故障模式的故障率λ，此時(shí)故障檢測(cè)率的計(jì)算公式為：

(8)

1.4.2 故障隔離率

故障隔離率描述了系統(tǒng)對(duì)故障模式的隔離和診斷能力，可根據(jù)故障-測(cè)試相關(guān)性矩陣計(jì)算得到：

(9)

式中,LI為矩陣Dn×m中非全零且唯一的行向量的個(gè)數(shù)。若考慮各故障模式的故障率λ，此時(shí)故障隔離率的計(jì)算公式為：

(10)

1.5 優(yōu)化模型

1.5.1 優(yōu)化對(duì)象和目標(biāo)

優(yōu)化對(duì)象即對(duì)系統(tǒng)配置測(cè)試的方案，因此，優(yōu)化對(duì)象模型可以用式(5)形式表示。測(cè)試最優(yōu)配置方案需滿足以下目標(biāo)：在使系統(tǒng)達(dá)到規(guī)定的測(cè)試性指標(biāo)參數(shù)的情況下，模型中測(cè)試數(shù)量最少。因此，優(yōu)化目標(biāo)函數(shù)可表示為：

minm

(11)

1.5.2 優(yōu)化約束條件

在本文中，優(yōu)化目標(biāo)規(guī)定系統(tǒng)需要達(dá)到規(guī)定的測(cè)試性指標(biāo)這一前提。因此，優(yōu)化約束條件可表示為：

(12)

式中,系統(tǒng)要求達(dá)到的測(cè)試性指標(biāo)分別記作FDR、FIR，在建模時(shí)若有充足的先驗(yàn)信息，在計(jì)算γFD、γFI時(shí)可以考慮故障率等因素，使模型更接近實(shí)際。

2 基于混合離散二進(jìn)制粒子群-遺傳算法的測(cè)試優(yōu)化配置方法

2.1 遺傳算法基本理論

20世紀(jì)60年代，Holland受生物進(jìn)化機(jī)制啟發(fā)，提出了一種模擬自然界生物遺傳進(jìn)化的自適應(yīng)概率搜索算法，稱為遺傳算法(Genetic Algorithm，GA)[6-8]。遺傳算法將進(jìn)化理論中“適者生存”這一基本思想引入串結(jié)構(gòu)當(dāng)中，并且在串之間進(jìn)行有規(guī)則的隨機(jī)信息交換。隨著算法的不斷運(yùn)行，好的品質(zhì)被保留下來(lái)并加以結(jié)合，以此來(lái)繁衍出更佳的個(gè)體。新一代個(gè)體中不但包含著上一代個(gè)體的大量信息，而且由于好的特征被不斷地繼承下來(lái)，在總體特征上也不斷勝過(guò)舊的一代，從而使整個(gè)種群向前進(jìn)化發(fā)展。遺傳算法的基本概念包括：

種群(Population)：是指遺傳算法求解過(guò)程中，在解空間中的一個(gè)子集，即初始情況下多個(gè)解的集合。遺傳算法從該初始種群開(kāi)始計(jì)算求解。

個(gè)體(Individual)：是指某個(gè)解集合中的單個(gè)解，一個(gè)個(gè)體由某種數(shù)據(jù)結(jié)構(gòu)描述其基本特征信息。本文中的個(gè)體即用二進(jìn)制編碼來(lái)表示一個(gè)測(cè)試配置方案。

適應(yīng)度函數(shù)(Fitness)：是遺傳算法實(shí)現(xiàn)優(yōu)勝劣汰的主要依據(jù)，其作用是計(jì)算種群中每個(gè)個(gè)體的環(huán)境適應(yīng)度并進(jìn)行評(píng)估，它決定了染色體的優(yōu)劣程度。

染色體(Chromosome)：是將個(gè)體進(jìn)行編碼后得到的編碼串，也可稱為基因型個(gè)體，編碼串中的單個(gè)元素稱為一個(gè)基因。

遺傳操作(Genetic Operator)：遺傳操作包括選擇、交叉、變異3種基本形式，是一種從原始種群產(chǎn)生新種群的操作。

GA包含以下要素：

GA=(P(0),N,l,s,Qr,Qc,Qm,Pr,Pc,Pm,f)

(13)

式中,P(0)為初始種群；N為種群規(guī)模；l為染色體長(zhǎng)度；s為對(duì)個(gè)體的選擇策略；Qr為選擇算子；Qc為交叉算子；Qm為變異算子；Pr為選擇概率；Pc為交叉概率；Pm為變異概率；f為適應(yīng)度函數(shù)。

2.2 離散二進(jìn)制粒子群算法基本理論

Eberhart博士和Kennedy博士于1995年提出了粒子群優(yōu)化算法(Particle Swarm Optimization，PSO)[9-11]。為解決實(shí)際問(wèn)題，二人于1997年又提出了離散二進(jìn)制粒子群優(yōu)化算法(Binary Particle SwarmOptimization，BPSO)[12-13]。粒子群算法僅根據(jù)粒子的速度進(jìn)行搜索，沒(méi)有遺傳算法復(fù)雜的選擇、交叉和變異操作，結(jié)構(gòu)簡(jiǎn)單，運(yùn)行速度較快并且擁有記憶功能，但粒子僅僅將當(dāng)前搜索到的最優(yōu)位置作為共享信息，容易陷入局部最小，從而出現(xiàn)所謂的“早熟收斂”現(xiàn)象。

粒子群中任意一個(gè)粒子的信息都可以用如下信息來(lái)描述：①粒子的當(dāng)前位置Xi=(xi1,xi2,…,xin)；②粒子搜索到的當(dāng)前最優(yōu)解Pi=(pi1,pi2,…,pin)，記作Pbest，稱為個(gè)體極值；③粒子在搜索空間中的飛行速度Vi=(vi1,vi2,…vin)，這里i=1,2,…n。若粒子i的當(dāng)前位置優(yōu)于其歷史最優(yōu)位置，則將粒子i的當(dāng)前位置更新作為歷史最優(yōu)位置。vij和xij的更新公式為：

vij=w·vij+c1·rand1()·(pij-xij)+

c2·rand1()·(pgj-xgj)

(14)

xij=xij+vij

(15)

式中,w為慣性權(quán)重；c1，c2為粒子群學(xué)習(xí)因子；rand1，rand2是兩個(gè)隨機(jī)分布在(0，1)之間的正實(shí)數(shù)。整個(gè)粒子群也存在一個(gè)歷史最優(yōu)位置Pg=(Pg1,Pg2,…,Pgn)，記作Gbest，即粒子群搜索到的最優(yōu)解，稱為全局極值。

對(duì)于BPSO中的任一粒子，其每一維的xij和Pbestij都用0或者1表示，而vij則變?yōu)榱Ｗ游恢萌?的概率，速度越快則粒子位置取1的概率越高。由于神經(jīng)網(wǎng)絡(luò)中的Sigmoid函數(shù)具有相似的特點(diǎn)，所以一般用該函數(shù)將粒子速度映射到區(qū)間[0,1]內(nèi)：

(16)

則粒子位置更新公式可表示為：

(17)

2.3 混合離散二進(jìn)制粒子群-遺傳算法

由于GA存在搜索速度慢，沒(méi)有種群的移動(dòng)，不能參考?xì)v史信息等缺點(diǎn)[14]。為解決系統(tǒng)的測(cè)試優(yōu)化配置問(wèn)題，本文將二進(jìn)制粒子群算法與遺傳算法相結(jié)合，提出一種BPSO-GA算法。該算法將遺傳算法和離散二進(jìn)制粒子群算法相結(jié)合，通過(guò)綜合兩種算法的優(yōu)點(diǎn)，使新算法既能保證較快的搜索速度和成功率，又可以擁有良好的信息共享機(jī)制，避免陷入局部最優(yōu)。

BPSO-GA的流程如圖1所示。

圖1 BPSO-GA流程圖

BPSO-GA的總體思路是:首先對(duì)每一代種群分別計(jì)算其中個(gè)體對(duì)應(yīng)的適應(yīng)度函數(shù)，并進(jìn)行遺傳操作。在經(jīng)過(guò)規(guī)定代數(shù)的迭代后再進(jìn)行粒子群操作產(chǎn)生新種群，將種群中達(dá)到指標(biāo)要求的個(gè)體在數(shù)據(jù)庫(kù)中進(jìn)行存儲(chǔ)。最后對(duì)數(shù)據(jù)庫(kù)中個(gè)體進(jìn)行比較，將數(shù)據(jù)庫(kù)中測(cè)試數(shù)量最少的個(gè)體輸出為最優(yōu)個(gè)體。下面介紹基于BPSO-GA的測(cè)試配置問(wèn)題求解的幾個(gè)關(guān)鍵步驟：

1)粒子編碼：將第k個(gè)粒子的二進(jìn)制編碼設(shè)置為VTk=[v1k,v2k,…vnk]，此時(shí)種群中每一個(gè)粒子都對(duì)應(yīng)一種測(cè)試的配置方案；

2)為防止Sigmoid函數(shù)飽和使算法早熟，本文將粒子最大速度設(shè)置為2，此時(shí)的Sigmoid函數(shù)為：

(18)

3)構(gòu)造適應(yīng)度函數(shù)：首先計(jì)算種群中個(gè)體的測(cè)試性指標(biāo)γFD和γFI。由于個(gè)體的適應(yīng)度主要由3個(gè)參數(shù)決定：測(cè)試配置數(shù)量m、系統(tǒng)故障檢測(cè)率γFD、系統(tǒng)故障檢測(cè)率γFI。由于測(cè)試數(shù)量m越少，測(cè)試性指標(biāo)γFD、γFI越大，個(gè)體的適應(yīng)度越大。因此，本文將適應(yīng)度函數(shù)設(shè)置為：

(19)

φ為權(quán)值系數(shù)。

3 實(shí)例驗(yàn)證

對(duì)某裝備渦扇發(fā)動(dòng)機(jī)的傳動(dòng)供電系統(tǒng)建立測(cè)試性模型，系統(tǒng)功能框圖如圖2所示。該系統(tǒng)有25個(gè)故障模式，根據(jù)系統(tǒng)功能框圖和先驗(yàn)故障傳播關(guān)系，建立系統(tǒng)的故障鄰接矩陣f(G)，如表1所示。

表1 傳動(dòng)供電系統(tǒng)故障鄰接矩陣

根據(jù)公式(3)，(4)可計(jì)算得到系統(tǒng)故障可達(dá)性矩陣F(G)，限于文章篇幅，此處不再贅述。得到故障可達(dá)性矩陣后為混合算法設(shè)置初始參數(shù)：Nmax=100，Popsize=20，Pc=0.8，Pm=0.1，c1=c2=2，w=0.9，vmax=1，φ=1。

仿真算例(一)：考慮為所有故障模式都設(shè)置測(cè)試的情況，仿真結(jié)果如表2所示。

表2 測(cè)試配置仿真結(jié)果(一)

由表2可知，在所有故障模式均可測(cè)的情況下系統(tǒng)的故障檢測(cè)率γFD和故障隔離率γFI都為100%。但在實(shí)際中由于接口設(shè)計(jì)、物理結(jié)構(gòu)、成本等問(wèn)題無(wú)法為所有的故障模式都設(shè)置測(cè)試點(diǎn)，此時(shí)的測(cè)試性模型的測(cè)試性指標(biāo)雖然都為100%，卻無(wú)法落實(shí)到系統(tǒng)研發(fā)設(shè)計(jì)當(dāng)中。

圖2 傳動(dòng)供電系統(tǒng)功能框圖

仿真算例(二)：計(jì)算FDR=0.8，F(xiàn)IR=0.6時(shí)的優(yōu)化仿真結(jié)果，如表3所示。

表3 測(cè)試優(yōu)化配置仿真結(jié)果(二)

上述結(jié)果表明，當(dāng)系統(tǒng)對(duì)故障檢測(cè)率和隔離率的要求為FDR≥0.8，F(xiàn)IR≥0.6時(shí)。表3中列出了BPSO-GA得出的最優(yōu)解，以及它們不能夠檢測(cè)到的故障模式和不能夠隔離的故障模式。由該測(cè)試配置方案可得最少要設(shè)置m=13個(gè)測(cè)試才能滿足該指標(biāo)。

仿真算例(三)：計(jì)算FDR=0.95，F(xiàn)IR=0.9時(shí)的優(yōu)化仿真結(jié)果，如表4所示。

表4 測(cè)試優(yōu)化配置仿真結(jié)果(三)

無(wú)仿真算例(三)中所提測(cè)試性指標(biāo)基本可以達(dá)到武器裝備的測(cè)試性指標(biāo)要求。由表4可知至少需要為模型設(shè)置m=20個(gè)測(cè)試才能滿足所提測(cè)試性指標(biāo)要求；至少需要m=21個(gè)測(cè)試才可以完全檢測(cè)和隔離所有故障模式，這比仿真算例(一)中滿測(cè)試配置方案減少使用了4個(gè)測(cè)試，效率提高了16%，若考慮測(cè)試接口設(shè)計(jì)和測(cè)試費(fèi)用，該測(cè)試配置方案可以大大降低實(shí)際系統(tǒng)的設(shè)計(jì)難度和全壽命周期費(fèi)用。

4 結(jié)論

本文針對(duì)目前測(cè)試性建模工作中尚無(wú)具體方法指導(dǎo)測(cè)試配置這一問(wèn)題，以系統(tǒng)故障空間為基礎(chǔ)，建立了系統(tǒng)的故障傳播模型。然后以測(cè)試性分析的指標(biāo)為約束，以測(cè)試數(shù)量為優(yōu)化目標(biāo)，提出了一種基于混合離散二進(jìn)制粒子群-遺傳算法的測(cè)試優(yōu)化配置方法，并應(yīng)用在某型裝備渦扇發(fā)動(dòng)機(jī)的傳動(dòng)供電系統(tǒng)中。通過(guò)考慮不同的測(cè)試性指標(biāo)要求，得到了不同情況下的最優(yōu)測(cè)試配置方案及對(duì)應(yīng)的測(cè)試性指標(biāo)和無(wú)法檢測(cè)、隔離的故障模式。由測(cè)試配置仿真結(jié)果可知，該算法可以在滿足系統(tǒng)測(cè)試性指標(biāo)要求下給出系統(tǒng)的最優(yōu)測(cè)試配置方案，有效地解決了系統(tǒng)測(cè)試性分析與設(shè)計(jì)方面的問(wèn)題，能夠提高測(cè)試性分析與設(shè)計(jì)效率，降低系統(tǒng)的設(shè)計(jì)難度，對(duì)于指導(dǎo)復(fù)雜系統(tǒng)的測(cè)試性建模工作具有實(shí)際應(yīng)用價(jià)值。