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

黃陳輝 吳海濤 阮江濤 錢 程

（上海師范大學(xué)信息與機(jī)電工程學(xué)院 上海 200234）

1 引言

軟件測試自動化是對程序自動生成測試數(shù)據(jù)，近些年越來越引起計(jì)算機(jī)研究員的關(guān)注。智能尋優(yōu)算法［1］能更好、更快地解決復(fù)雜的軟件測試問題，如蟻群算法［2］、模擬退火［3］、遺傳算法［4］等。其中遺傳算法使用最為廣泛，因?yàn)樗梢愿咝幚砣謨?yōu)化、多峰值等問題［5］。

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

2 相關(guān)背景知識

2.1 反向數(shù)字

反向?qū)W習(xí)概念是Tizhoosh. H 于2005 年提出的，并證明它在現(xiàn)有學(xué)習(xí)方法的上的有效性［10］。假設(shè)正在搜索估算x（給定問題的解），那么先應(yīng)該計(jì)算相反的數(shù)字。

定義1（反向數(shù)字）

a，b分別是 [a，b]區(qū)間中的上下限，x是源數(shù)，x~ 是源數(shù)的反向數(shù)字。

基于反向?qū)W習(xí)定義如下：假設(shè)f(x)為適應(yīng)度函數(shù)，g為評價函數(shù)，為x∈[a，b]的反向值，每次迭 代 中 計(jì) 算 的 是f(x) 與的 值 ，當(dāng)時，學(xué)習(xí)繼續(xù)，否則用。

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

2.2 Logistic映射

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

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

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

2.3 遺傳算法

遺傳算法在實(shí)際應(yīng)用中需要目標(biāo)語言的合理子集［13］。因此將遺傳算法形式化表示為

表1 符號的含義

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

3.1 測試用例生成模型

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

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

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

3.2 編碼方式

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

3.3 反向?qū)W習(xí)種群初始化策略

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

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

算法1 基于反向?qū)W習(xí)的種群初始化算法

輸入：均勻隨機(jī)數(shù)

輸出：初始種群p0

step1均勻生成一批隨機(jī)數(shù)，組成最初種群Initial_P；

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

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

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

step5生成初始種群p0，參與遺傳算法進(jìn)化。

3.4 適應(yīng)度函數(shù)的設(shè)計(jì)

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

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

3.5 遺傳操作

1）選擇操作

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

2）混沌交叉

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

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

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

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

（2）混沌序列確定交叉點(diǎn)位置

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

3）混沌變異

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

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

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

3.6 混沌遺傳算法步驟

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

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

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

2）種群初始化模塊：先生成最初種群，利用反向?qū)W習(xí)對個體基因求解反向數(shù)字，新生成的反向個體與最初個體同時求適應(yīng)度函數(shù)值，選擇適應(yīng)度函數(shù)值高的進(jìn)行下一步操作；

3）運(yùn)行插裝后的程序，求解初始種群的適應(yīng)度函數(shù)值；

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

4 實(shí)驗(yàn)分析

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

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

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

4.1 被測程序基本信息

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

表2 被測程序的基本信息

4.2 實(shí)驗(yàn)方法和評價體系

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

對于不同方法均采用以下指標(biāo)進(jìn)行性能比較（每種方法分別獨(dú)立運(yùn)行50次）：

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

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

4.3 實(shí)驗(yàn)結(jié)果

為了驗(yàn)證被測程序目標(biāo)路徑的覆蓋率，運(yùn)用不同方法做對比，實(shí)驗(yàn)結(jié)果如表3。

為了驗(yàn)證被測程序的測試數(shù)據(jù)生成時間，運(yùn)用不同方法做對比，實(shí)驗(yàn)結(jié)果如表4。

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

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

4.4 實(shí)驗(yàn)數(shù)據(jù)分析

根據(jù)實(shí)驗(yàn)結(jié)果，可以逐一回答前文提到的問題Q1、Q2。

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

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

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

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

5 結(jié)語

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