王麗麗， 王 偉2， 單光興2， 萬 賀

(1.北京交通大學(xué) 機械與電子控制工程學(xué)院，北京 100044； 2.北京航天自動控制研究所，北京 100854)

科技發(fā)展所帶來的電子系統(tǒng)的結(jié)構(gòu)和功能越來越復(fù)雜，信息處理系統(tǒng)復(fù)雜的結(jié)構(gòu)和功能使其故障模式呈現(xiàn)出多樣性的特點，為了提高其維護檢修性能，一般會設(shè)計多個測試，在實際測試中可能只需要執(zhí)行所有測試中的一部分測試就能滿足系統(tǒng)故障檢測率和故障隔離率等測試性指標(biāo)[1]。設(shè)計的測試項需要進行優(yōu)化選擇，即選擇最少的測試項對系統(tǒng)的所有故障進行檢測和隔離。所以，設(shè)計合理高效的信息處理系統(tǒng)測試優(yōu)化選擇的算法是非常有必要的。本文旨在遺傳算法的思想基礎(chǔ)上，采取若干有效措施，對遺傳算法進行改進，使其能夠更好地解決系統(tǒng)的測試優(yōu)化選擇問題，最后通過計算故障檢測率和隔離率來驗證結(jié)果的可靠性。

1 測試優(yōu)化選擇問題數(shù)學(xué)模型

1.1 問題的描述

根據(jù)已經(jīng)建立的信息處理系統(tǒng)多信號流圖模型，計算系統(tǒng)故障-測試相關(guān)矩陣，然后基于系統(tǒng)的相關(guān)矩陣進行測試優(yōu)化選擇問題研究。

首先根據(jù)多信號流圖模型的建立方法和步驟，分析信息處理系統(tǒng)的各模型組成元素，最終得到系統(tǒng)的多信號流圖模型如圖1所示。

圖1 信息處理系統(tǒng)的多信號流圖模型

由圖1，利用圖2介紹的方法，計算相關(guān)矩陣，進而得到系統(tǒng)的故障-測試相關(guān)矩陣如表1所示。

圖2 系統(tǒng)相關(guān)矩陣的計算流程圖

t1t2t3t4t5t6t7t8t9t10t11C1(F)10000000000C2(F)01000000000C3(F)00100000000C4(F)00010000000C5(G)00001000000C6(G)00000100000C7(F)00000010000C8(F)00000001000C9(F)00000000100C10(F)00000000110C11(F)00000001001C12(G)01011111000

表1中行向量表示信息處流系統(tǒng)中可能發(fā)生的故障，C(F)表示功能故障模式，C(G)表示完全故障模式；列向量分別表示針對系統(tǒng)的故障源設(shè)計的測試。本文的目的就是對這些測試項進行優(yōu)化選擇，期望在系統(tǒng)發(fā)生故障時，以最少的測試項對系統(tǒng)故障進行檢測和隔離，使產(chǎn)生的測試代價最小。

1.2 測試性指標(biāo)的計算

系統(tǒng)的測試性能指標(biāo)不僅包括故障檢測率，還包括故障隔離率；基于系統(tǒng)的故障-測試相關(guān)矩陣，具體計算方法如下：

① 一般地，用FDR表示故障檢測率，計算公式為[2]

(1)

式中，M為非0行的總和；N為所有行的總數(shù)。

② 一般地，用FIR表示故障檢測率，計算公式為[2]

(2)

式中，m為相關(guān)矩陣中故障行的總數(shù)；n為所有行的總數(shù)。

2 改進的遺傳算法

針對測試優(yōu)化選擇問題，目前已經(jīng)有很多種方法,包括遺傳算法、BP神經(jīng)網(wǎng)絡(luò)、模擬退火算法，以及對這些算法的融合算法[2]，綜合分析已有的這些算法的特點，結(jié)合信息處理系統(tǒng)，在傳統(tǒng)的遺傳算法的思想基礎(chǔ)上通過編寫C++程序，應(yīng)用改進的遺傳算法選擇出了符合測試指標(biāo)的全局優(yōu)化測試集合。

2.1 傳統(tǒng)的遺傳算法的原理

2.1.1 傳統(tǒng)的遺傳算法的原理

傳統(tǒng)的遺傳算法(Genetic Algorithm，GA)是一種通過模擬自然進化過程搜索最優(yōu)解的方法[3]。其算法流程圖如圖3所示。

圖3 算法流程圖

2.1.2 傳統(tǒng)的遺傳算法的特點

與其他測試選擇算法相比，遺傳算法在求解優(yōu)化問題上有其自身的優(yōu)點和成功應(yīng)用的例子，取得了良好的效果。所選擇遺傳算法的理由主要有以下幾個方面。

① 唯有遺傳算法可進行全局搜索，即可對搜索過程中的多個解同時評價分析，這樣就可一次性處理多個個體，效率明顯提高[4]。

② 群體中個體優(yōu)劣的評判標(biāo)準(zhǔn)僅由適應(yīng)度函數(shù)來決定，不需要外力。

③ 搜索方式采用啟發(fā)式，隨機去搜索，并沒有明確的規(guī)定。

④ 遺傳算法除以上優(yōu)勢之外，其最大的優(yōu)勢還在于：很多復(fù)雜的現(xiàn)象均通過進化機制來實現(xiàn)；在解決復(fù)雜問題的時候，快速性和準(zhǔn)確率都很高。

基于以上所述，選用遺傳算法，并對其進行改進。

2.2 改進的遺傳算法的原理

針對傳統(tǒng)的遺傳算法存在容易陷入局部最優(yōu)解和交叉、變異導(dǎo)致個體失效等問題，對傳統(tǒng)的遺傳算法進行改進。

2.2.1 改進的遺傳算法的原理

初始種群的優(yōu)劣決定遺傳算法的收斂性。對于在其閾值范圍內(nèi)有多個極值的函數(shù)而言，往往會存在隨機生成集中在特定范圍的初始變量，打破了均勻性，從而算法極易陷入局部最優(yōu)解[5]。另外，傳統(tǒng)的遺傳算法在進行交叉時，會對處于劣勢的個體的基因序列進行改變，這種改變提高了進化過程中優(yōu)良個體出現(xiàn)的概率，即會通過交叉出現(xiàn)更優(yōu)的測試集,但同時也會導(dǎo)致基因片段交叉后出現(xiàn)基因編碼相同致使個體失效的情況，導(dǎo)致所選取的整個測試集合在實際應(yīng)用中沒有意義。改進的遺傳算法執(zhí)行過程如圖4所示。

圖4 信息處理系統(tǒng)遺傳算法程序流程圖

2.2.2 具體的改進措施

針對以上提出的關(guān)于傳統(tǒng)的遺傳算法存在容易陷入局部最優(yōu)解和交叉變異導(dǎo)致個體失效等問題，對傳統(tǒng)的遺傳算法的具體的改進措施主要有以下幾點。

(1) 選擇合適的種群規(guī)模。若規(guī)模太小的話，則種群的進化速度會受到影響，這樣就極易導(dǎo)致陷入局部最優(yōu)解的錯誤之中；但是如果規(guī)模太大的話，程序的運算量就會加大，進化速度隨之減慢。為了兼顧以上兩點，最終選取種群規(guī)模為50個，即對包含50個測試集合的群體進行研究，使算法依托于編寫好的C++程序運行，進行多次測試，均能快速高效得到最優(yōu)解[2]。

(2) 初始化時，保證每一個基因都擁有不同的編碼方式，也就是本文在初始化時通過程序的限制，使每個個體的的基因序列不同。因為采用了實數(shù)的編碼方式對個體基因進行編碼，也就是一個個體就是一個測試集合，個體的基因序列就是真實的測試項目，如果個體一旦出現(xiàn)了相同的基因序列，那么就相當(dāng)于測試集合中有了相同的測試項目，這在實際情況中就意味著個體沒有意義，這種情況有可能導(dǎo)致產(chǎn)生局部最優(yōu)解，因此，通過改進遺傳算法，保證每一個基因的編碼均不相同，不但避免了產(chǎn)生局部最優(yōu)解的問題，而且算法的搜索空間也被擴張了，使算法的效率更高、運行時間更短。

(3) 改進的遺傳算法中先用冒泡排序按照個體的適應(yīng)度函數(shù)值進行從大到小排列，然后將最優(yōu)的兩個個體的基因片段交叉替換給最差的兩個個體的等位基因片段；提高了出現(xiàn)更優(yōu)的測試集的可能性[6]。

但是交叉還有一個弊端，就是交叉后可能導(dǎo)致個體基因出現(xiàn)相同的基因編碼機制，從而使個體失效，由前述可知，改進的遺傳算法則會隨機變異，直到交叉后的個體沒有相同編碼機制的基因，從而加速進化。

(4) 其最優(yōu)個體保護機制，該機制的添加有兩方面的作用：一方面，為了使個體不因產(chǎn)生相同基因而失效；另一方面，為了規(guī)避優(yōu)秀的個體因變異變成處于劣勢的個體，通過改進遺傳算法，不讓最優(yōu)個體參與種群的變異[2]。

(5) 設(shè)計特殊的適應(yīng)度函數(shù)。

在傳統(tǒng)的遺傳算法適應(yīng)度函數(shù)中加入故障檢測率、故障隔離率，使得對個體優(yōu)劣程度的評價更加全面可靠，適應(yīng)度函數(shù)為

(3)

式中，Ci為ti的測試代價。

①hi為ti的評估函數(shù)值，計算公式為

(4)

其中，d(ti)為ti中檢測到的故障數(shù)；k(ti)為所有故障的最小可測度[6]。

由綜合故障-測試相關(guān)矩陣及式(3)可以看出，測試的評估函數(shù)值變化趨勢與測試的重要性變化趨勢一致，并且適應(yīng)度函數(shù)與評估函數(shù)是正相關(guān)，從而證明了適應(yīng)度函數(shù)的正確有效性。

②S(Ts)的計算公式為

(5)

式中，D為能檢測到的系統(tǒng)故障檢測率；I為能檢測到的系統(tǒng)障隔離率[7-10]。

3 仿真和驗證

3.1 仿真工具

利用C++語言將改進的遺傳算法集成到軟件中，用于信息處理系統(tǒng)測試優(yōu)化選擇。開發(fā)的軟件界面如圖5所示，該軟件通過人機交互界面實時顯示算法的運算過程和結(jié)果。

圖5 信息處理系統(tǒng)測試性優(yōu)化算法軟件界面

3.2 實驗驗證

3.2.1 改進的遺傳算法有效性驗證

在算法中分別設(shè)定不同的個數(shù)進行運算，統(tǒng)計運行的結(jié)果如表2所示。為了方便統(tǒng)計，將表中的測試按照從t1～t12的順序重新編號。

表2 不同測試項個數(shù)算法運行結(jié)果統(tǒng)計

當(dāng)測試項的個數(shù)確定時，將表2的統(tǒng)計結(jié)果繪制成圖6所示的折線圖會更加直觀。

圖6 不同測試項個數(shù)算法優(yōu)選測試集的測試性指標(biāo)

圖6中，從圖中可以看出，當(dāng)設(shè)定9個或者10個測試項時，盡管故障檢測率達到了100%，但系統(tǒng)無法清晰地對所有故障定位并且隔離，有11個測試項時既實現(xiàn)了測試項個數(shù)最少，又達到了系統(tǒng)測試性指標(biāo)。

從11個測試中選擇全局優(yōu)化測試集為{t1,t2,t3,t4,t5,t6,t7,t8,t9,t10,t11,t12}。軟件運行結(jié)果如圖7所示。

圖7 遺傳算法程序運行結(jié)果

從圖7中可以看出系統(tǒng)的測試性指標(biāo)均為百分之百，符合實際要求，進而說明改進的遺傳算法在測試選擇優(yōu)化問題上的正確性。

算法優(yōu)選出的測試集如表3所示，其中灰色部分是算法優(yōu)選掉的測試項。

表3 遺傳算法選擇的測試集合

對表3做進一步分析，得表3中所有行均無全0行，也就是說實驗過程中不存在沒有檢測到的故障，檢測的覆蓋率為沒有未檢測故障，即檢測的覆蓋率為100%；且同一行之中列與列均不同；也就是說所有故障都能清晰地被隔離，系統(tǒng)的故障隔離率為100%。進一步說明所設(shè)計的遺傳算法在測試選擇優(yōu)化問題上的有效性。

3.2.2 傳統(tǒng)的遺傳算法與改進的遺傳算法比較

在編寫好的C++程序中注釋掉限制每一個基因編碼都不相同機制、個體失效保護機制、最優(yōu)個體保護機制等，得到傳統(tǒng)的遺傳算法思想下測試集合的選擇策略，與改進后的選擇策略形成對比組，依托于測試軟件，分別對這兩種算法進行20次試驗。

表4列出了沒有改進和改進之后測試集合優(yōu)化結(jié)果，利用測試序列中有無重復(fù)的測試項來判斷測試選擇過程是否陷入局部最優(yōu)解和個體失效情況，如果有重復(fù)的測試項目就在表中計為1，無重復(fù)的測試項目就記為0。

從表4中的數(shù)據(jù)可以看出，20次實驗中，沒有改進之前的遺傳算法選擇出的測試集合雖然都滿足測試性能指標(biāo)，但是選擇出的測試序列有20次是失效的，對于實際沒有任何指導(dǎo)意義，是無效的，改進之后的遺傳算法選出來的測試集合不但滿足測試性能指標(biāo)，且沒有重復(fù)的測試項，對實際應(yīng)用有很重要的指導(dǎo)意義。

該實驗進一步說明針對傳統(tǒng)的遺傳算法存在容易陷入局部最優(yōu)解和交叉變異導(dǎo)致個體失效等問題，本文對傳統(tǒng)的遺傳算法的改進是可靠有效的。

表4 傳統(tǒng)的遺傳算法與改進的遺傳算法個體失效的比較

4 結(jié)束語

本文在建立信息處理系統(tǒng)數(shù)學(xué)模型的基礎(chǔ)上，改進了傳統(tǒng)的遺傳算法，使其高效、快速、準(zhǔn)確地得到信息處理系統(tǒng)的全局優(yōu)化測試集，通過計算測試項指標(biāo)和實驗驗證了改進的遺傳算法的有效性和正確性。