劉 音

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

1 引言

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

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

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

2.1 遺傳算法原理

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

算法具體過(guò)程如圖1所示。

圖1 遺傳方法流程圖

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

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

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

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

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

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

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

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

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

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

(1)

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

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

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

Φ={xx′-x≤R}

(2)

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

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

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

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

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

2.4 遺傳模塊設(shè)計(jì)

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

1)算子選取

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

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

(3)

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

2)交叉與變異

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

(4)

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

3)保存精英方式

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

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

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

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

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

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

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

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

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

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

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

(5)

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

T=t1+t2+t3+…+tn

(6)

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

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

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

表1 測(cè)試用例的檢測(cè)軟件錯(cuò)誤狀況

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

該軟件的錯(cuò)誤級(jí)別以及類型量化值如表2所示。

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

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

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

圖3 沒(méi)有排序測(cè)試的用例序列APFD

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

圖4 排序之后的測(cè)試用例序列的APFD

測(cè)試用例沒(méi)有排序與排序之后的錯(cuò)誤檢測(cè)，如圖5所示。

圖5 測(cè)試用例沒(méi)有排序與排序后的錯(cuò)誤檢測(cè)情況圖像

通過(guò)以上實(shí)驗(yàn)分析能夠看出：

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

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

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

5 結(jié)束語(yǔ)

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

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

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

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