基于改進的遺傳算法系統測試選擇問題研究

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

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

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

1 測試優化選擇問題數學模型

1.1 問題的描述

根據已經建立的信息處理系統多信號流圖模型，計算系統故障-測試相關矩陣，然后基于系統的相關矩陣進行測試優化選擇問題研究。

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

圖1 信息處理系統的多信號流圖模型

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

圖2 系統相關矩陣的計算流程圖

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中行向量表示信息處流系統中可能發生的故障，C(F)表示功能故障模式，C(G)表示完全故障模式；列向量分別表示針對系統的故障源設計的測試。本文的目的就是對這些測試項進行優化選擇，期望在系統發生故障時，以最少的測試項對系統故障進行檢測和隔離，使產生的測試代價最小。

1.2 測試性指標的計算

系統的測試性能指標不僅包括故障檢測率，還包括故障隔離率；基于系統的故障-測試相關矩陣，具體計算方法如下：

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

(1)

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

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

(2)

式中，m為相關矩陣中故障行的總數；n為所有行的總數。

2 改進的遺傳算法

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

2.1 傳統的遺傳算法的原理

2.1.1 傳統的遺傳算法的原理

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

圖3 算法流程圖

2.1.2 傳統的遺傳算法的特點

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

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

② 群體中個體優劣的評判標準僅由適應度函數來決定，不需要外力。

③ 搜索方式采用啟發式，隨機去搜索，并沒有明確的規定。

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

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

2.2 改進的遺傳算法的原理

針對傳統的遺傳算法存在容易陷入局部最優解和交叉、變異導致個體失效等問題，對傳統的遺傳算法進行改進。

2.2.1 改進的遺傳算法的原理

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

圖4 信息處理系統遺傳算法程序流程圖

2.2.2 具體的改進措施

針對以上提出的關于傳統的遺傳算法存在容易陷入局部最優解和交叉變異導致個體失效等問題，對傳統的遺傳算法的具體的改進措施主要有以下幾點。

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

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

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

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

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

(5) 設計特殊的適應度函數。

在傳統的遺傳算法適應度函數中加入故障檢測率、故障隔離率，使得對個體優劣程度的評價更加全面可靠，適應度函數為

(3)

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

①hi為ti的評估函數值，計算公式為

(4)

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

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

②S(Ts)的計算公式為

(5)

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

3 仿真和驗證

3.1 仿真工具

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

圖5 信息處理系統測試性優化算法軟件界面

3.2 實驗驗證

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

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

表2 不同測試項個數算法運行結果統計

當測試項的個數確定時，將表2的統計結果繪制成圖6所示的折線圖會更加直觀。

圖6 不同測試項個數算法優選測試集的測試性指標

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

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

圖7 遺傳算法程序運行結果

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

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

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

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

3.2.2 傳統的遺傳算法與改進的遺傳算法比較

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

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

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

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

表4 傳統的遺傳算法與改進的遺傳算法個體失效的比較

4 結束語

本文在建立信息處理系統數學模型的基礎上，改進了傳統的遺傳算法，使其高效、快速、準確地得到信息處理系統的全局優化測試集，通過計算測試項指標和實驗驗證了改進的遺傳算法的有效性和正確性。