基于混合離散二進制粒子群-遺傳算法的測試配置方法研究

，，

(海軍航空大學 岸防兵學院，山東 煙臺 264001)

0 引言

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

基于以上問題，本文提出了一種混合離散二進制粒子群-遺傳算法(binary particle swarm optimization-genetic algorithm，BPSO-GA)對復雜系統測試性建模過程中測試優化配置問題進行求解。

1 測試優化配置的數學描述與建模

1.1 故障可達性矩陣

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

(1)

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

(2)

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

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

(3)

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

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

(4)

1.2 測試配置方案

系統測試配置方案可用n維向量表示：

VT=[v1,v2,…vn]

(5)

其中:vi=1表示為故障模式fmi配置測試；vi=0表示不為故障模式fmi配置測試。將VT中vi=1的個數記為m，表示為系統配置測試的總數量。其中：系統最優測試配置方案應為最小完備測試集合，即去除該集合中任意一個測試就不再滿足測試性參數指標要求。

1.3 故障-測試相關性矩陣

測試性模型具有圖示形式和矩陣形式兩種表示方法,故障-測試相關性矩陣以測試性圖示模型為基礎進行相關性分析得到, 故障-測試相關性矩陣便是對系統功能單元故障與測試資源相關性的數學描述。根據測試配置方案VT為系統配置測試，構建故障與測試資源的邏輯關系，故障-測試相關性矩陣Dn×m可由下式計算得到：

(6)

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

1.4 測試性參數指標

1.4.1 故障檢測率

故障檢測率描述了系統對故障模式的檢測能力[5]，可根據故障-測試相關性矩陣計算得到：

(7)

式中,LD為矩陣Dn×m中非全零行向量個數。若考慮各故障模式的故障率λ，此時故障檢測率的計算公式為：

(8)

1.4.2 故障隔離率

故障隔離率描述了系統對故障模式的隔離和診斷能力，可根據故障-測試相關性矩陣計算得到：

(9)

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

(10)

1.5 優化模型

1.5.1 優化對象和目標

優化對象即對系統配置測試的方案，因此，優化對象模型可以用式(5)形式表示。測試最優配置方案需滿足以下目標：在使系統達到規定的測試性指標參數的情況下，模型中測試數量最少。因此，優化目標函數可表示為：

minm

(11)

1.5.2 優化約束條件

在本文中，優化目標規定系統需要達到規定的測試性指標這一前提。因此，優化約束條件可表示為：

(12)

式中,系統要求達到的測試性指標分別記作FDR、FIR，在建模時若有充足的先驗信息，在計算γFD、γFI時可以考慮故障率等因素，使模型更接近實際。

2 基于混合離散二進制粒子群-遺傳算法的測試優化配置方法

2.1 遺傳算法基本理論

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

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

個體(Individual)：是指某個解集合中的單個解，一個個體由某種數據結構描述其基本特征信息。本文中的個體即用二進制編碼來表示一個測試配置方案。

適應度函數(Fitness)：是遺傳算法實現優勝劣汰的主要依據，其作用是計算種群中每個個體的環境適應度并進行評估，它決定了染色體的優劣程度。

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

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

GA包含以下要素：

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

(13)

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

2.2 離散二進制粒子群算法基本理論

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

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

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

c2·rand1()·(pgj-xgj)

(14)

xij=xij+vij

(15)

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

對于BPSO中的任一粒子，其每一維的xij和Pbestij都用0或者1表示，而vij則變為粒子位置取1的概率，速度越快則粒子位置取1的概率越高。由于神經網絡中的Sigmoid函數具有相似的特點，所以一般用該函數將粒子速度映射到區間[0,1]內：

(16)

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

(17)

2.3 混合離散二進制粒子群-遺傳算法

由于GA存在搜索速度慢，沒有種群的移動，不能參考歷史信息等缺點[14]。為解決系統的測試優化配置問題，本文將二進制粒子群算法與遺傳算法相結合，提出一種BPSO-GA算法。該算法將遺傳算法和離散二進制粒子群算法相結合，通過綜合兩種算法的優點，使新算法既能保證較快的搜索速度和成功率，又可以擁有良好的信息共享機制，避免陷入局部最優。

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

圖1 BPSO-GA流程圖

BPSO-GA的總體思路是:首先對每一代種群分別計算其中個體對應的適應度函數，并進行遺傳操作。在經過規定代數的迭代后再進行粒子群操作產生新種群，將種群中達到指標要求的個體在數據庫中進行存儲。最后對數據庫中個體進行比較，將數據庫中測試數量最少的個體輸出為最優個體。下面介紹基于BPSO-GA的測試配置問題求解的幾個關鍵步驟：

1)粒子編碼：將第k個粒子的二進制編碼設置為VTk=[v1k,v2k,…vnk]，此時種群中每一個粒子都對應一種測試的配置方案；

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

(18)

3)構造適應度函數：首先計算種群中個體的測試性指標γFD和γFI。由于個體的適應度主要由3個參數決定：測試配置數量m、系統故障檢測率γFD、系統故障檢測率γFI。由于測試數量m越少，測試性指標γFD、γFI越大，個體的適應度越大。因此，本文將適應度函數設置為：

(19)

φ為權值系數。

3 實例驗證

對某裝備渦扇發動機的傳動供電系統建立測試性模型，系統功能框圖如圖2所示。該系統有25個故障模式，根據系統功能框圖和先驗故障傳播關系，建立系統的故障鄰接矩陣f(G)，如表1所示。

表1 傳動供電系統故障鄰接矩陣

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

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

表2 測試配置仿真結果(一)

由表2可知，在所有故障模式均可測的情況下系統的故障檢測率γFD和故障隔離率γFI都為100%。但在實際中由于接口設計、物理結構、成本等問題無法為所有的故障模式都設置測試點，此時的測試性模型的測試性指標雖然都為100%，卻無法落實到系統研發設計當中。

圖2 傳動供電系統功能框圖

仿真算例(二)：計算FDR=0.8，FIR=0.6時的優化仿真結果，如表3所示。

表3 測試優化配置仿真結果(二)

上述結果表明，當系統對故障檢測率和隔離率的要求為FDR≥0.8，FIR≥0.6時。表3中列出了BPSO-GA得出的最優解，以及它們不能夠檢測到的故障模式和不能夠隔離的故障模式。由該測試配置方案可得最少要設置m=13個測試才能滿足該指標。

仿真算例(三)：計算FDR=0.95，FIR=0.9時的優化仿真結果，如表4所示。

表4 測試優化配置仿真結果(三)

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

4 結論

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