基于混沌遺傳算法的測試用例自動生成研究*

黃陳輝 吳海濤 阮江濤 錢 程

（上海師范大學信息與機電工程學院 上海 200234）

1 引言

軟件測試自動化是對程序自動生成測試數據，近些年越來越引起計算機研究員的關注。智能尋優算法［1］能更好、更快地解決復雜的軟件測試問題，如蟻群算法［2］、模擬退火［3］、遺傳算法［4］等。其中遺傳算法使用最為廣泛，因為它可以高效處理全局優化、多峰值等問題［5］。

遺傳算法解決測試用例自動生成問題是學者們爭先研究的熱點。例如鄭超群等提出改進的交叉、變異算子，增加種群多樣性來避免過早收斂［6］，但改進效果不明顯；丁蕊等［7］使用啟發式搜索來提高測試用例生成效率，但算法并行性沒有充分利用，性能改進不明顯；高雪笛等［8］改進算法適應度函數設計，提高算法收斂速度，但仍不能很好解決大規模計算量的問題，使算法迭代后期種群失去多樣性。同時他們忽略了遺傳算法對初始種群有一定依賴性，隨機生成方式已限制了尋找最優解過程［9］。針對上述方法不足，本文設計了以下改進策略：1）反向學習機制初始化種群，使得初始種群更靠近最優解；2）改進適應度函數設計方式；3）使用混沌序列優化遺傳算子的交叉、變異操作，提高算法的全局尋優能力。

2 相關背景知識

2.1 反向數字

反向學習概念是Tizhoosh. H 于2005 年提出的，并證明它在現有學習方法的上的有效性［10］。假設正在搜索估算x（給定問題的解），那么先應該計算相反的數字。

定義1（反向數字）

a，b分別是 [a，b]區間中的上下限，x是源數，x~ 是源數的反向數字。

基于反向學習定義如下：假設f(x)為適應度函數，g為評價函數，為x∈[a，b]的反向值，每次迭 代 中 計 算 的 是f(x) 與的 值 ，當時，學習繼續，否則用。

考慮反向個體，選中更靠近的作為種群最初個體，那就是每個個體都離最優解更近一步。

2.2 Logistic映射

混沌的遍歷性可以根據自己規律遍歷非重復的所有狀態［11～12］這一特性可以用來避免陷入局部最小解。本文使用logistic映射生成混沌序列。Logistic混沌映射概述如下。

Logistic 映射是一個一維映射，卻具有混沌模型所擁有特征和性質。方程如式（2）所示：

式中μ為控制參數，且0 ≤μ≤ 4，0 ≤x≤ 1。該模型能準確表現出生物群體數的波動與時代變化的關系。若n表示進化代數，那么xn表示第n代的出生數，xn+1表示第n+1 代的出生數。μ∈（3.56994，4］，映射處于混沌狀態。映射不變集為區間（0，1）。本文使用參數值為μ=4。

2.3 遺傳算法

遺傳算法在實際應用中需要目標語言的合理子集［13］。因此將遺傳算法形式化表示為

表1 符號的含義

3 基于混沌遺傳算法生成測試用例

3.1 測試用例生成模型

測試用例集表示為測試用例ti集合T。給定|T|=n，有T={t1，t2，…，tn}。其方法模型如下：

圖1 混沌遺傳算法的測試用例自動生成方法模型

首先分析被測程序，生成T的結構和屬性說明。其次，插入變量動態跟蹤T的行為，具體操作：程序分支子關鍵點（即分支節點的兩個互為兄弟的后置關鍵點）插裝變量，賦初值1，當執行經過該分支節點，值賦值為0。測試數據執行路徑101010，101001，100110，100101，011010，011001，010110，010101。測試反饋信息是構造適應度函數的重要依據，目標路徑剔除不可行路徑和隨機法很容易生成測試數據的路徑。最后，用正確表示的測試數據運行插裝后程序，利用混沌遺傳算法遺傳操作測試數據，使得可以生成針對目標路徑的測試用例。

3.2 編碼方式

本文采用二進制編碼級聯法，三角形分類程序參數類型為數值型。設被測程序三個輸入取值范圍為［0，63］，那么二進制表示參數有6位，即6個基因，分別為 10010，010010，111000，二進制級聯編碼后就是10010010010111000，它們形成的整體稱為個體，即該問題的染色體。

3.3 反向學習種群初始化策略

求解測試用例自動生成問題中，需使用反向學習的策略來初始化隨機生成的最初種群。需求解個體基因的反向基因，具體表述如下：設程序輸入范圍為［0，2n-1］，那么有

式（6）生成個體基因反向數字，生成新個體（反向個體）。方法步驟如下：

算法1 基于反向學習的種群初始化算法

輸入：均勻隨機數

輸出：初始種群p0

step1均勻生成一批隨機數，組成最初種群Initial_P；

step2對Initial_P每個個體基因利用公式（6），取反向基因，生成新個體，即反向個體；

step3 將step2 生成的反向個體組成反向種群Initial_P'；

step4 從最初種群Initial_P 和反向種群Initial_P'中依次取個體，計算適應度函數值，得到適應度函數值，再組合適應度更高的個體，將其放進最終初始種群的對應位置中；

step5生成初始種群p0，參與遺傳算法進化。

3.4 適應度函數的設計

測試數據生成可以描述如下：對于給定程序P和P的路徑，認為D是P的輸入空間，當x(x∈D)作為輸入數據時，程序執行期間將會導致路徑u被覆蓋。適應度函數的形式化表示：

其中，u(x)表示個體x覆蓋的路徑；ui為待覆蓋的第i條路徑；b(ui，u(x))表示兩條路徑的層接近度，其值為從第1 個分岔點開始ui與u(x)的不同分支語句的個數；|ui|是目標路徑ui中包含的分支點的數目；m(ui)是路徑ui測試數據集中測試數據的個數，越易覆蓋的路徑會有越大的測試數據集，將會導致是適應度函數越低。

3.5 遺傳操作

1）選擇操作

本文采用輪盤賭個體選擇方式復制符合要求的個體到新種群，值越高被選擇概率就越大。

2）混沌交叉

傳統遺傳算法容易陷入早熟，收斂到局部最優，同時上述適應度函數設計使測試數據易匯集在已生成測試數據的路徑，需要改進交叉方式，提高遺傳算法搜索范圍。具體操作如下：

（1）首先控制交叉操作的頻率

任取一個初值x0，如果p小于x0的情況下，可以進行交叉；反之，則不交叉。即：

式中pc是預先選定的值，將交叉概率設置為0.9，使得種群中可以較充分交叉。

（2）混沌序列確定交叉點位置

設有L 位長染色體，在（0，1）區間上隨機取一個數xn為初值，產生（0，1）區間混沌序列xn+1。公式q=(int)xn+1*L把序列映射至染色體基因位空間，使交叉發生在此位置，形成新子代，僅更換部分點基因，改動較小，這樣可避免在產生子代過程中種群發生尋優抖振問題。

3）混沌變異

同上所述，變異操作的進行也可以由產生的混沌序列來控制。理論基礎同上，不做贅述。

對個體進行混沌交叉，混沌變異操作，首先，兩兩隨機組合種群內的各個體，在此基礎上生成的每對組合，由系統隨機生成一個（0，1）之間的隨機數，由交叉概率決定是否交叉，若交叉，則采用經線性映射的混沌序列xn+1，所對應的位置進行交叉操作，否則，看下一對。

混沌不重復遍歷特定范圍內的所有狀態用來避免陷入局部最優。它對初值敏感可以保證即使兩個最佳解是非常接近的，但仍然是兩個完全不同的染色體，因此種群可以保持多樣性。

3.6 混沌遺傳算法步驟

綜上所述，本文提出的生成混沌遺傳算法測試用例自動生成的流程和算法流程圖如圖2。

圖2 基于混沌遺傳算法測試用例自動生成流程

1）初始化參數：隨機生成最初種群，初始種群規模，交叉和變異概率，最大迭代次數；

2）種群初始化模塊：先生成最初種群，利用反向學習對個體基因求解反向數字，新生成的反向個體與最初個體同時求適應度函數值，選擇適應度函數值高的進行下一步操作；

3）運行插裝后的程序，求解初始種群的適應度函數值；

4）遺傳操作：通過輪盤賭選擇策略選擇進入下一代的種群，同時通過混沌序列決定遺傳算法的交叉、變異操作，首先控制交叉（變異）操作的頻率，決定交叉（變異）與否，如果交叉（變異），再根據隨機生成的混沌序列來選擇需要進行交叉或者變異的位置。

4 實驗分析

本文選擇了6 個不同規模程序作為被測程序，來評價提出的方法的性能，同時與其他方法對比，并進行結果分析，所有方法均采用Matlab 軟件環境，實驗回答了以下兩個問題：

Q1：與其他方法做對比，本文提出的方法是否能夠達到更高的路徑覆蓋率？

Q2：與其他方法做對比，本文提出的方法是否具有較少的時間消耗？

4.1 被測程序基本信息

實驗分別采用三角形分類實驗程序，3 個數排序，interserve，totino，spice，schedule2 為被測程序，本文選取4 個工業測試程序，它們被大量應用于測試用例的生成中［15］。

表2 被測程序的基本信息

4.2 實驗方法和評價體系

本文方法（記為ICGA），通過與標準遺傳算法（SGA），改進后的遺傳算法（IGA）作對比，來分析改進后的算法性能。選擇操作為輪盤賭。遺傳操作中的交叉方式為為單點交叉，概率為0.9；變異方式為單點變異，概率為0.1。所有方法的種群規模都為50，最大迭代數為1000。

對于不同方法均采用以下指標進行性能比較（每種方法分別獨立運行50次）：

1）路徑覆蓋率（cov），表示為測試數據覆蓋的路徑數與所有路徑數的比值。

2）測試數據生成時間（t），是指生成測試數據所需要的時間。

4.3 實驗結果

為了驗證被測程序目標路徑的覆蓋率，運用不同方法做對比，實驗結果如表3。

為了驗證被測程序的測試數據生成時間，運用不同方法做對比，實驗結果如表4。

表3 不同方法對被測的程序路徑覆蓋率

表4 不同方法對被測程序程序的測試數據生成時間（s）

4.4 實驗數據分析

根據實驗結果，可以逐一回答前文提到的問題Q1、Q2。

Q1：表 3 可以看出，在 3 個數排序，interserve，totino，spice，schedule2 中達到了最大路徑覆蓋率，就等于說本文的方法模型適合于測試數據自動生成。IGA 在三角形分類程序有輕微優勢，說明對某些應用程序優先選擇易覆蓋路徑，將進一步提升方法性能。

圖3 不同方法對被測的程序路徑覆蓋率

圖4 不同方法對被測程序程序的測試數據生成時間（s）

Q2：結合表3、表4 本文方法對于程序3 個數排序，interserve，totino，spice，schedule2，達到最高覆蓋率同時，時間總是最少的，對于三角形分類程序雖然覆蓋率略低于SGA 和IGA，但本文方法生成測試用例時間少于前兩者。隨著程序規模擴大，本文方法實用性更強。

5 結語

本文改進了種群初始化策略、遺傳算法交叉、變異操作和適應度函數的設計，提高了算法的全局尋優能力。實驗驗證本文方法在測試用例自動生成方面優于其他方法。隨著軟件測試的免疫能力越強，越需要增加其他覆蓋要求，這也是值得進一步研究的問題。