基于改進(jìn)遺傳算法的回歸測試用例優(yōu)先級排序

劉 音

(北京交通大學(xué)海濱學(xué)院，河北 黃驊 061199)

1 引言

各種程序系統(tǒng)飛速發(fā)展，而其中的回歸測試是修改舊代碼后，重新測試以確保修改沒有引入新的錯誤或者是致使其它代碼出現(xiàn)錯誤[1]。此過程是軟件生命周期內(nèi)的一個重要組成部分，在整個軟件的測試過程內(nèi)，占有比較大的工作量比重，在進(jìn)行軟件開發(fā)的各個階段都要完成多次回歸測試。在以快速迭代的開發(fā)之中，新版本的連續(xù)發(fā)布致使回歸測試非常頻繁，在終端的編程方法內(nèi)，更是要求每天都采用若干次的回歸測試[2]。所以，為了在給定的進(jìn)度以及預(yù)算下，最大程度上執(zhí)行效率和有效的回歸測試，要利用測試用例進(jìn)行維護(hù)，且選擇一定策略對應(yīng)回歸測試包[3]。但是，現(xiàn)階段傳統(tǒng)方法在進(jìn)行回歸測試用例優(yōu)先級排序時，測試效果較差，且執(zhí)行效率低，不能夠滿足實(shí)際要求，所以該項技術(shù)一直是國內(nèi)外研究學(xué)者的重要挑戰(zhàn)。

為此本文提出一種基于改進(jìn)遺傳算法的回歸測試用例優(yōu)先級排序方法，該方法是在傳統(tǒng)的遺傳算法上引入禁忌算法，通過禁忌方法的記憶能力強(qiáng)優(yōu)點(diǎn)，在可控范圍內(nèi)擇優(yōu)選取，淘汰劣質(zhì)個體，同時基于改進(jìn)遺傳算法具有較強(qiáng)的搜索能力，能夠有效甄別優(yōu)質(zhì)活劣質(zhì)個體，然后將擇優(yōu)選取的個體代替劣質(zhì)個體。在回歸測試用例優(yōu)先級排序中，考慮時間和測試成本因素，通常將多元化目標(biāo)函數(shù)運(yùn)用到用例優(yōu)先的排序結(jié)果評價中，通過時間以及覆蓋的角度進(jìn)行考察，利用有效執(zhí)行時間以及平均分支覆蓋率兩個目標(biāo)來函數(shù)評價，該方法執(zhí)行時間短，平均分支的覆蓋率大，所以該序列優(yōu)良。

2 改進(jìn)遺傳算法分析

2.1 遺傳算法原理

通過自然選擇與遺傳理論作為基本條件，結(jié)合群體中染色體任意信息交換機(jī)制和生物進(jìn)化過程內(nèi)適者生存規(guī)則，誕生的搜索方法[4]。

算法具體過程如圖1所示。

圖1 遺傳方法流程圖

2.2 改進(jìn)的遺傳方法

在該方法內(nèi)交配是隨機(jī)的，不過該隨機(jī)化雜交方法主要是在初始階段的尋優(yōu)方面，需要保持多樣化狀態(tài)，但是在后期的進(jìn)化方面，大量的個體集中在某一極點(diǎn)上，很容易導(dǎo)致近親繁衍，致使個體的差異性出現(xiàn)類似的情況，通常獲取最佳的局部解所產(chǎn)生的測試用例不能夠達(dá)到滿意的覆蓋率。

所以，若使用其它方法來對該情況完成改進(jìn)。因此本文加入禁忌搜索，利用該方法的較強(qiáng)記憶能力，在規(guī)定范圍內(nèi)用優(yōu)質(zhì)個體替代劣質(zhì)個體，完成個體最優(yōu)轉(zhuǎn)化。遺傳方法就有了禁忌方法局部的超強(qiáng)搜索能力，增強(qiáng)了生成最佳解的概率，具體流程如下所示[5]：

步驟一：初始化的參數(shù)；種群Pop、禁忌表的長度L、種群大小PopSize。

步驟二：選擇操作種群內(nèi)的個體。

步驟三：利用自適應(yīng)的變異和自適應(yīng)交叉來操作種群內(nèi)的個體。

步驟四：大范圍轉(zhuǎn)移VB已經(jīng)淘汰的個體，且利用生成的新個體來替代被淘汰的個體。

步驟五：生成新一代種群，然后轉(zhuǎn)移到步驟二中。

2.3 禁忌搜索的模塊設(shè)計

兩個個體之間的相似度利用S代表，具體公式如下

(1)

式(1)中，ai表示禁忌搜索中最優(yōu)點(diǎn)值，aj表示禁忌搜索中參考值。以任意一點(diǎn)當(dāng)成中心球體，然后以球體內(nèi)非中心點(diǎn)的任意一點(diǎn)稱其鄰居[6]。

將禁忌搜索方法加入遺傳方法內(nèi)，使那些利用禁忌檢測的個體，被稱之為新個體進(jìn)行接收，同時導(dǎo)致那些有效的基因缺失，不過適應(yīng)度低于父代個體，就會被禁忌掉。此外，導(dǎo)致那些有效的基因、不過適應(yīng)度低的個體，具有更多機(jī)會參加變異與交叉，以此來避免或者是延緩收斂的情況，

1)選擇方式與鄰域解集合的大小，對算法的參數(shù)性能有很大的影響，目前解領(lǐng)域內(nèi)將會做最佳選擇，如果選擇過大，那么計算量也比較大，反之，如果選擇過少，那么出現(xiàn)優(yōu)質(zhì)解概率，則會變小。因此生成領(lǐng)域的方式，主要是以目前解x來作為中心，然后在利用R來作為半徑，生成鄰域，具體公式為：

Φ={xx′-x≤R}

(2)

式(2)中：x′代表目前解x任意產(chǎn)生的離散化鄰域解。

2)在進(jìn)行遺傳方法的進(jìn)化過程內(nèi)，每代完成變異或者較差以后[8]，將低于γ的水平個體進(jìn)行淘汰，把這些淘汰個體設(shè)置成ai{ai，a2，…，an}，采用禁忌搜索方法完成替代搜索，然后在其鄰域附近搜素，其步驟如下所示：

步驟一：對一個解Φnow=ai以及禁忌表進(jìn)行數(shù)據(jù)預(yù)處理。

步驟二：在β內(nèi)選擇最優(yōu)的個體Best，且f(Best)>(fΦnow)同時S>ε時，Φnow=Best，Best加入禁忌表L，反之，如果Best?L，Φnow=Best，要修改禁忌表L。

步驟三：如果滿足條件，則終止搜索，反之，需要轉(zhuǎn)移至步驟二中。

2.4 遺傳模塊設(shè)計

具體的改進(jìn)遺傳方法3個基本算子，加入精英保留形式，改進(jìn)算子具體方法如下所示[9]：

1)算子選取

對適者生存規(guī)則進(jìn)行選擇操作，保證種群內(nèi)個體的分布。采用每一個個體的適應(yīng)值對群體內(nèi)最差的個體適應(yīng)度值相減，將此值作為選擇個體的標(biāo)準(zhǔn)。

該方法要優(yōu)于傳統(tǒng)輪盤賭的方式，致使最佳個體被選擇之后，顯著增加變異和交叉的概率，這樣最差的個體，會失去遺傳機(jī)會，以及整體的收斂速度也會快速增加，具體的概率計算選取方式如下

(3)

式(3)中：fi代表被選擇的個體適應(yīng)度，fworst代表最差個體的適應(yīng)度。

2)交叉與變異

遺傳算法交叉率以及變異率是固定不變的，主要是作為隨機(jī)性的搜索，存在特定的盲目性，很有可能導(dǎo)致存在比較高的適應(yīng)度個體遭到損壞，因此，需要對損壞的個體進(jìn)行修復(fù)，利用自適應(yīng)算子，調(diào)整個體動態(tài)，檢查變異的交叉概率是否有效，將以存在的缺陷克服。此具有指導(dǎo)性的進(jìn)化，存在全局最優(yōu)解與效率以及更好的魯棒性，具體的交叉率Pc、變異率Pm，公式如下所示

(4)

式(4)中：fmax代表群體內(nèi)的最大適應(yīng)度，favg代表所有群體的平均適應(yīng)度，f′代表需要交叉的個體內(nèi)較大適應(yīng)度，fc1代表需要變異個體適應(yīng)度值。

3)保存精英方式

把種群內(nèi)最佳個體，復(fù)制到下一代的種群內(nèi)，成為下一代種群的新個體[10]。

3 回歸測試用例優(yōu)先級排序

3.1 回歸多目標(biāo)測試用例優(yōu)先排序模型構(gòu)建

在進(jìn)行回歸多目標(biāo)測試用例優(yōu)先排序過程內(nèi)，時間和測試成本的存在，通常利用多元素目標(biāo)函數(shù)，測試用例有先的排序結(jié)果好壞進(jìn)行評價，在測試用例優(yōu)先的排序問題內(nèi)，其通常狀況中，在評價指標(biāo)眾多的情況下，要求能達(dá)到單一目標(biāo)的最優(yōu)解是很困難的，這就要求求解問題的非支配解，具體兩個優(yōu)化目標(biāo)的非主導(dǎo)解，回歸多目標(biāo)測試用例優(yōu)先排序模型構(gòu)建具體如下所示：

1)如果測試用例的優(yōu)先排序是排列目標(biāo)函數(shù)f1、f2以上的值都越大越好，則在f1(T1)>f1(T2)且f2(T2)>f2(T1)時，亦或者f1(T1)

2)決定一個測試用例集合中所有測試用例的編號組成了一個全排列，然后在這個測試的用例序列中，用例的上位部分，主要是根據(jù)這個全排列形成上面的第一個測試用例段。在測試用例結(jié)束時，將所有的測試用例按順序組成測試用例段，使其達(dá)到最大適應(yīng)值。

不同測試情況用例覆蓋不同語句的情況測試用例的序列A-B-C-D相應(yīng)APSC值如圖2所示：

圖2 測試用例的序列A-B-C-D相應(yīng)APSC值

圖2是測試用例A、B、C、D對于程序內(nèi)的APSC值對應(yīng)情況，測試用例A、B、C、D是在執(zhí)行期間以A-B-C-D為執(zhí)行順序的，隨著測試用例逐個執(zhí)行，它所覆蓋的語句的數(shù)目也在不斷增加，測試使用例C執(zhí)行結(jié)束后，語句的覆蓋率可能會達(dá)到100%，當(dāng)測試用例D執(zhí)行的時，語句的覆蓋量不會在增加了，在這種情況下，測試用例A、B、C按順序形成的有序測試用例，稱為上位測試用例段，由此完成回歸多目標(biāo)測試用例優(yōu)先排序模型構(gòu)建。

3.2 多目標(biāo)回歸測試用例的優(yōu)先排序評價標(biāo)準(zhǔn)

從時間和覆蓋角度出發(fā)，將有效執(zhí)行時間和平均分支覆蓋率這兩個指標(biāo)作為評價函數(shù)，主要用于衡量一個測試用例的優(yōu)先次序好壞，用C表示平均分支的覆蓋率，具體一個測試用例的優(yōu)先排序序列平均分支覆蓋率公式如下所示

(5)

上式(5)中：n代表測試用例個數(shù)，m代表被測程序內(nèi)的分支個數(shù)，cm表示首要覆蓋程序中的第i個分支測試用例在該測試用例優(yōu)先順序，有效時間利用T代表，一個測試用例的優(yōu)先排序序列有效執(zhí)行時間，利用以下公式表示

T=t1+t2+t3+…+tn

(6)

式(6)中：tn表示執(zhí)行測試用例的優(yōu)先次序中的第i個測試用例所花的時間，由此證明這個序列具有一定層次，其原因是一個測試用例序的優(yōu)先順序C越大，T順序越小[12]。

4 實(shí)驗分析

為證明本文方法的有效性，首先選擇某一個文件的傳輸軟件Ti(i=1，2，3，4，5，6，7，8，9，10)來進(jìn)行分析和實(shí)驗，該軟件的要求，需要設(shè)計10個測試用例Fi(i=1，2，3，4，5，6，7，8，9，10)。在進(jìn)行第一次測試發(fā)現(xiàn)，該軟件內(nèi)的測試用例檢測錯誤如表1所示。

表1 測試用例的檢測軟件錯誤狀況

表1中的CT是代表用例的執(zhí)行時間。

該軟件的錯誤級別以及類型量化值如表2所示。

表2 軟件內(nèi)錯誤等級以及類型的量化值

表2中，fd代表錯誤等級所相應(yīng)的量化值，fs代表錯誤類型所對應(yīng)的量化值。

通過以上表1和表2內(nèi)的錯誤類型以及等級的量化值。在進(jìn)行回歸測試的時，第一次測試所執(zhí)行的是沒有排序測試的用例，而第二次是通過本文方法進(jìn)行排序測試用例之后在執(zhí)行的，利用算法TRG，獲得回歸測試用例的優(yōu)先排序集{T5，T9，T8，T4，T6，T2，T1，T10，T3}，沒有排序測試的例集APFD如圖3所示。

圖3 沒有排序測試的用例序列APFD

排序之后的測試用例集APFD，如圖4所示。

圖4 排序之后的測試用例序列的APFD

測試用例沒有排序與排序之后的錯誤檢測，如圖5所示。

圖5 測試用例沒有排序與排序后的錯誤檢測情況圖像

通過以上實(shí)驗分析能夠看出：

1)沒有排序的測試用例集APFD數(shù)值是0.68，而排序之后的測試用例集APFD數(shù)值是0.84。其排序之后的測試用例值大于沒有排列測試用例的值，以此可以說明，排序之后的測試用例錯誤檢測速度要遠(yuǎn)快于沒有排序測試的用例檢測錯誤速度。

2)通過以上測試用例的沒有排序與排序之后的錯誤檢測圖像能夠看出，排序之后的回歸測試用例在執(zhí)行40%用例時，就能夠檢測出軟件內(nèi)所有所有錯誤。而沒有排序回歸的測試用例，在執(zhí)行70%用例才達(dá)到相同測試效果。

以此可以證明，本文方法具有很好的測試有效性，且測試效率較高。

5 結(jié)束語

1)對于一個軟件開發(fā)項目來說，項目的測試組在進(jìn)行測試過程內(nèi)，會把開發(fā)的測試用例保存至測試用例庫內(nèi)，且對其進(jìn)行維護(hù)與管理。采用正確的回歸測試來對回歸測試效率以及有效性進(jìn)行選擇，回歸測試要用到人力、經(jīng)費(fèi)以及時間來進(jìn)行管理、實(shí)施與計劃。

2)本文方法在傳統(tǒng)的遺傳算法上，加入的禁忌算法進(jìn)行改進(jìn)，使其具有禁忌方法的局部超強(qiáng)搜索能力優(yōu)點(diǎn)。

3)在利用多個目標(biāo)函數(shù)對回歸測試用例優(yōu)先級排序評價，經(jīng)過時間以及覆蓋的角度考察，執(zhí)行時間較短，平均分支較大，說明該序列優(yōu)良。

4)本文方法的測試效果較好，執(zhí)行效率高。