劉 音

（北京交通大學(xué)海濱學(xué)院 河北·滄州 061199）

0 引言

軟件測試的主要目的是通過執(zhí)行測試用例檢測出所有隱藏的錯誤，是軟件質(zhì)量保證的重要手段。測試用例（Test Case）是由一組測試輸入、執(zhí)行條件及預(yù)期結(jié)果組成的，是用于衡量軟件是否存在錯誤的主要依據(jù)，它的數(shù)量和質(zhì)量直接決定了測試效率和成本。隨著軟件規(guī)模不斷擴大，測試用例集規(guī)模也會越來越大，其中的冗余測試用例也會隨之增多，測試成本也就隨著增大。為了有效降低測試成本，有必要對測試用例集進(jìn)行優(yōu)化，即在保證原檢測錯誤能力的基礎(chǔ)上，尋找原始用例集的一個子集，使其覆蓋所有測試需求，且保證運行成本最小。

遺傳算法（Genetic Algorithm,GA）是將生物進(jìn)化過程中適者生存規(guī)則與種群內(nèi)部染色體的信息隨機交換機制相結(jié)合的高效全局尋優(yōu)搜索算法。作為一種全局搜索方法廣泛應(yīng)用在測試用例優(yōu)化領(lǐng)域中，有著獨特的優(yōu)勢和高效性。

1 改進(jìn)遺傳算子

遺傳算法是由進(jìn)化論和遺傳學(xué)演化而來的一種直接搜索優(yōu)化方法。它將所有可能解看成是種群的一個個體，依據(jù)適者生存、優(yōu)勝劣汰的進(jìn)化原則，進(jìn)行選擇、交叉和變異操作，最終得出問題最優(yōu)解。但遺傳算法中存在以下問題：

（1）早熟現(xiàn)象，即過早陷入局部最優(yōu)解，而很難走向全局最優(yōu)。

（2）在選擇操作過程中，適應(yīng)度高的個體作為父代，可能導(dǎo)致遺傳基因趨于一致，也就是存在很多相似的個體，減少了種群的多樣性。

鑒于以上問題，本文對選擇算子、交叉算子和變異算子進(jìn)行了改進(jìn)，進(jìn)而形成了一種新的改進(jìn)的遺傳算法（Improved Genetic Algorithm,IGA），并用改進(jìn)的遺傳算法實現(xiàn)測試用例集縮減。

1.1 改進(jìn)選擇算子

選擇算子作用就是依據(jù)個體適應(yīng)度值，從父代種群中選擇若干個體遺傳到下一代。輪盤賭法通過隨機性，保證了下一代種群的多樣性，但同時會使降低高適應(yīng)度個體選中概率難以收到最優(yōu)解。改進(jìn)的選擇算子是將排序與輪盤賭相結(jié)合的方法，增加了優(yōu)良個體的選擇概率，具體操作過程如下：

（1）種群中的個體按其適應(yīng)度的高低降序排列。

（2）對排好序的個體按5%、90%和5%分成三份，并用前5%的個體代替后5%的個體。

（3）計算個體適應(yīng)度 F(Ti)，i=(1,2,……，M)，M 為種群規(guī)模。

（4）計算選擇概率：個體適應(yīng)度值除以總適應(yīng)度值，如公式（1）所示。其中，P(Ti)為個體選擇概率，F(xiàn)(Ti)為個體適應(yīng)度。

（5）計算個體累積概率，如公式（2）所示，其中Qi表示個體累積概率。

（6）產(chǎn)生一個隨機數(shù)r，r在[0,1]范圍內(nèi)。

（7）若r

（8）重復(fù)7、8步驟M次。

1.2 改進(jìn)交叉算子

交叉操作就是兩個配對的個體按照某種方式交換某位基因或者某些位基因，從而產(chǎn)生新個體的過程。交叉類型有：單點交叉、兩點交叉、多點交叉和均勻交叉等，本文采用單點交叉，實現(xiàn)過程是在交叉點的位置相互交換兩個配對個體的部分染色體。

交叉概率用于判斷兩個個體是否需要交叉，在遺傳進(jìn)化過程中，為保留優(yōu)良個體應(yīng)盡量降低其交叉概率，為優(yōu)化劣質(zhì)個體應(yīng)盡量增加其交叉概率。本文提出了新的計算動態(tài)交叉概率方法，如公式（3）所示。

其中，f'表示兩個預(yù)交叉?zhèn)€體的高適應(yīng)度值，fmax為所有個體中的最大適應(yīng)度值，fmin為所有個體中的最小適應(yīng)度值，M1是適應(yīng)度值大于等于平均適應(yīng)度值的個體總數(shù)，M2是適應(yīng)度值小于平均適應(yīng)度值的個體總數(shù)，favg是平均適應(yīng)度值，Pc1和Pc2是兩個初始交叉概率、分別設(shè)置為：Pc1=0.5，Pc2=0.9。這樣就能保證進(jìn)化初期，有較大的交叉概率，保證種群多樣性，并且適應(yīng)度小的個體交叉概率更大；而在進(jìn)化后期，交叉概率相對較小，加快算法收斂。

圖1：用例集縮減規(guī)模

1.3 改進(jìn)變異算子

變異操作是模仿個體進(jìn)化過程中染色體的某個基因值發(fā)生突變過程，例如：采用二進(jìn)制編碼方式的個體，變異操作就是1變0或0變1。在變異操作中起關(guān)鍵作用的是變異概率，如果變異率較小，容易出現(xiàn)早熟現(xiàn)象，如果過大，會出現(xiàn)隨機搜索現(xiàn)象。本文提出了新的變異概率計算方法，如公式4所示。

Pm1和Pm2是初始變異率，Pm1=0.001，Pm2=0.005，fmax和fmin與公式8相同，f表示個體適應(yīng)度。適應(yīng)度小的個體變異率大，可以改良基因；適應(yīng)度大的個體變異率小，優(yōu)良基因可以遺傳給下一代。

2 IGA實現(xiàn)測試用例優(yōu)化

利用改進(jìn)遺傳算子解決測試用例優(yōu)化問題時，首先根據(jù)測試用例與測試需求之間的覆蓋關(guān)系，形成初始個體集合，然后通過選擇、交叉和變異操作，求出測試用例集縮減問題的最優(yōu)解。

2.1 測試用例優(yōu)化

測試用例優(yōu)化又稱為測試用例約簡，是M.J.Harrold等人在1993年提出的。早期，在測試用例縮減過程中并沒有考慮測試用例的運行代價，導(dǎo)致執(zhí)行縮減后測試用例集代價并不能降低到最小。縮減過程中不僅要考慮測試需求覆蓋度，還要考慮測試用例執(zhí)行代價，測試用例集約簡的定義：給出一組測試需求集R={r1,r2,r3,…,rm}，一組與測試需求相關(guān)的測試用例集T={t1,t2,t3,…,tn}，每個測試用例ti都有相應(yīng)的測試代價ci（ci>0），測試用例縮減問題就是求T的一個真子集T’，滿足：T’的運行代價最小，并且T’能覆蓋R。測試用例縮減結(jié)果就是滿足表1中的每行至少被一列覆蓋，且使“1”個數(shù)最少。

2.2 基因編碼

基因編碼就是把問題空間的數(shù)據(jù)轉(zhuǎn)化成遺傳空間的由基因組成的個體，常用編碼方法有：二進(jìn)制編碼、浮點編碼和符號編碼。二進(jìn)制編碼就是由符號0和1所組成的二值符號集，編碼、解碼操作簡單易行，交叉、變異等遺傳操作便于實現(xiàn)，故本文采用這種方法進(jìn)行基因編碼。根據(jù)測試需求和測試用例對應(yīng)關(guān)系構(gòu)建一個m×n矩陣：

圖2：算法運行時間

R表示測試需求集，T表示測試用例集，m表示矩陣的行數(shù)、由測試需求的個數(shù)決定，n表示矩陣的列數(shù)、由測試用例個數(shù)決定。gij表示用例tj和需求ri之間的覆蓋關(guān)系，如果gij=1表示tj覆蓋ri，反之gij=0表示tj沒有覆蓋ri。矩陣中的每一行表示了一個需求被所有用例的覆蓋情況，把每一行看成一個個體，采用二進(jìn)制基因編碼如公式（6）所示。

2.3 適應(yīng)度函數(shù)

適應(yīng)度是用來判斷種群中個體優(yōu)劣程度的指標(biāo)，并作為遺傳操作的依據(jù)。一般地，適應(yīng)度值越大，表明相應(yīng)的個體越優(yōu)，它的基因被復(fù)制到下一代的概率就越大，個體適應(yīng)度函數(shù)表示如公式（7）所示。

Cov(Tj)是用例集Tj的測試覆蓋度，計算方法如公式（8）所示。

Cost(Tj)是用例集Tj的運行代價，計算方法如公式（9）所示，用測試時間執(zhí)行時間粗略表示其運行代價。Cost(ti)表示執(zhí)行ti測試其覆蓋需求所用時間。

當(dāng)個體的適應(yīng)度達(dá)到給定的閾值或者個體的適應(yīng)度不在上升或者迭代次數(shù)達(dá)到閾值，終止計算。本文采用迭代次數(shù)達(dá)到閾值作為終止條件，最大迭代次數(shù)為150。不滿足收斂條件時，重復(fù)遺傳操作，直到收斂到最優(yōu)解。最后，根據(jù)測試用例與需求的覆蓋關(guān)系進(jìn)行解碼，獲得縮減后的測試用例集。

3 實驗結(jié)果與分析

為驗證改進(jìn)遺傳算法性能，在MATLAB仿真實驗的環(huán)境下，完成了測試用例優(yōu)化系統(tǒng)的設(shè)計與實現(xiàn)。以BBS論壇模擬程序為測試對象，從縮減測試用例規(guī)模和測試用例執(zhí)行時間這兩方面對遺傳算法和改進(jìn)遺傳算法進(jìn)行對比。

首先，從縮減測試用例規(guī)模上對比GA和IGA，實驗結(jié)果如圖1所示。每條曲線表示原始測試用例數(shù)量與縮減后測試用例數(shù)量之間的對應(yīng)關(guān)系。從結(jié)果可以看出，IGA縮減測試用例后規(guī)模明顯小于GA，且縮減規(guī)模更穩(wěn)定。然后，對比GA和IGA縮減后的測試用例集運行代價（時間），實驗結(jié)果如圖2所示。從結(jié)果可以看出，IGA縮減后的運行時間比GA的運行時間更低。

4 結(jié)束語

針對遺傳算法容易陷入局部最優(yōu)解問題，本文從選擇算子、交叉算子和變異算子三方面進(jìn)行改進(jìn)，得到了一種改進(jìn)遺傳算法，并將其應(yīng)用在解決測試用例集縮減問題。通過仿真實驗得出：

（1）改進(jìn)遺傳算法的收斂性優(yōu)于遺傳算法，可以更好的縮減測試用例規(guī)模。

（2）改進(jìn)遺傳算法縮減測試用例能更好的降低運行代價。

（3）應(yīng)用改進(jìn)遺傳算法縮減測試用例后得到的用例集與原測試用例集相同的錯誤檢測能力。

改進(jìn)遺傳算法可以有效降低測試用例冗余度，減小了測試用例規(guī)模，縮短了測試時間，并且保證了縮減后的測試用例有著原測試用例集的檢錯能力。但也存在問題，如：采用單點交叉，隨機基因重組不能保證大概率地生成優(yōu)于父代的個體。在未來工作中，筆者將繼續(xù)致力于測試用例集約簡的研究。