基于遺傳算法的MOTCP方法

晏慧，康茜，雷建云

(中南民族大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，武漢 430074)

軟件測(cè)試是保障軟件質(zhì)量的重要手段,是構(gòu)建高可信軟件的關(guān)鍵環(huán)節(jié).軟件測(cè)試占軟件開發(fā)總成本的比例一般達(dá)到50% 以上[1].為了修復(fù)軟件中未發(fā)現(xiàn)的問題或者滿足客戶提出的新的需求，常常需要對(duì)軟件不斷地修改，軟件迭代過程中容易引入新的缺陷，導(dǎo)致軟件質(zhì)量受到影響.回歸測(cè)試可有效解決此類問題，避免軟件演化帶來的副面影響.最簡(jiǎn)單的辦法是將所有測(cè)試用例重新執(zhí)行一遍，但存在如下問題：

(1)如果項(xiàng)目復(fù)雜，測(cè)試用例集龐大，執(zhí)行所有代碼代價(jià)較大，會(huì)導(dǎo)致超出項(xiàng)目預(yù)算或者延長(zhǎng)軟件開發(fā)周期.例如ROTHERMEL等人在某一合作企業(yè)內(nèi)，在測(cè)試一個(gè)包含約20000行代碼的軟件產(chǎn)品時(shí)發(fā)現(xiàn)，運(yùn)行所有測(cè)試用例所需時(shí)間長(zhǎng)達(dá)49 d[2].

(2)對(duì)部分代碼修改會(huì)影響到被測(cè)模塊的原有外部接口或內(nèi)在語(yǔ)義，并導(dǎo)致部分測(cè)試用例失效[1].

這使得研究如何提升回歸測(cè)試的效率變得有意義.常見的測(cè)試用例維護(hù)技術(shù)有：失效測(cè)試用例的識(shí)別和修復(fù)、測(cè)試用例選擇、測(cè)試用例優(yōu)先排序(test case prioritization, TCP)、測(cè)試用例縮減和測(cè)試用例擴(kuò)充[3].

測(cè)試用例優(yōu)先排序策略是將所有測(cè)試用例按照一定約束進(jìn)行處理并排序，從而在進(jìn)行回歸測(cè)試時(shí)，能使用較少的測(cè)試用例檢測(cè)出較多軟件缺陷的算法.李征等人通過將TCP問題多項(xiàng)式時(shí)間規(guī)約為背包問題, 證實(shí)該問題是一個(gè)NP難問題[4].同時(shí)他引入元啟發(fā)式算法(如蟻群算法、遺傳算法等)求解TCP問題.但遺傳算法在求解TCP問題時(shí)容易出現(xiàn)收斂過慢，過早陷入局部最優(yōu)而導(dǎo)致系統(tǒng)停滯[5].

排序目標(biāo)的選擇上通常認(rèn)為覆蓋越多代碼模塊的測(cè)試用例越有可能發(fā)現(xiàn)更多的軟件缺陷，運(yùn)行時(shí)間越短的測(cè)試用例運(yùn)行效率越高.傳統(tǒng)的測(cè)試用例排序技術(shù)的排序影響因子是代碼覆蓋率或有效運(yùn)行時(shí)間.目前絕大部分的研究都是基于單目標(biāo)解決TCP問題，但依舊存在這樣的困惑：覆蓋率高或者運(yùn)行時(shí)間短的測(cè)試用例并不能檢測(cè)出缺陷.

本文針對(duì)上述問題，將具有良好群體搜索特征的遺傳算法引入多目標(biāo)測(cè)試用例優(yōu)先級(jí)排序技術(shù)[6](multi-objective test case prioritization,MOTCP)中，并采用多個(gè)約束目標(biāo)指導(dǎo)其排序生成.該方法在執(zhí)行前對(duì)所有測(cè)試用例運(yùn)用聚類判定進(jìn)行分類，首先進(jìn)行一次約簡(jiǎn)，縮短算法執(zhí)行時(shí)盲目收縮的時(shí)間，然后選取平均缺陷檢測(cè)率和單個(gè)測(cè)試用例平均運(yùn)行時(shí)間為評(píng)價(jià)指標(biāo)，采用輪盤賭選擇算子，選擇適應(yīng)度較高的種群.為避免這種隨機(jī)采樣算法遺失優(yōu)秀種群個(gè)體，采用精英保留策略保留每次種群中最優(yōu)秀的10%直接復(fù)制到下一代.

1 測(cè)試用例集約簡(jiǎn)

算法開始時(shí)對(duì)所有的測(cè)試用例進(jìn)行簡(jiǎn)單的約簡(jiǎn)工作，這樣可以有效提高算法運(yùn)行效率，減少迭代次數(shù)，避免盲目搜索而導(dǎo)致的收斂速度慢問題.基于同一聚類測(cè)試用例可能是冗余的測(cè)試用例[7]的判定，本文將可以覆蓋同一測(cè)試需求的測(cè)試用例劃分為同一聚類，因?yàn)楦采w相同需求的測(cè)試用例較大可能檢測(cè)出相同的缺陷.基于此，同一聚類的測(cè)試用例只保留一份用以代表此聚類.比如存在3個(gè)測(cè)試用例集R、M、K和一個(gè)測(cè)試需求集Q，表示為R={R1,R2,…,Rn}、M={M1,M2,…,Mm}、K={K1,K2,…,Kk}、Q={Q1,Q2,…,Qq}.n、m、k分別表示其對(duì)應(yīng)的測(cè)試用例集的個(gè)數(shù)，q表示測(cè)試需求的個(gè)數(shù)，則存在以下3種情況：

(1)當(dāng)R中的測(cè)試用例能完全覆蓋Q中的測(cè)試需求，K中的測(cè)試用例也能覆蓋Q中全部測(cè)試需求時(shí)，則將R和K視為同一聚類，刪除任意一個(gè)測(cè)試用例集；

(2)當(dāng)R中的測(cè)試用例能完全覆蓋Q中的測(cè)試需求，K中的測(cè)試用例只能覆蓋Q中部分測(cè)試需求時(shí)，則將R和K視為同一聚類，刪除K測(cè)試用例集；

(3)當(dāng)R和M兩個(gè)測(cè)試用例集能完全覆蓋Q中的測(cè)試需求，K中的測(cè)試用例只能覆蓋部分Q中的測(cè)試需求時(shí),則將K與R和M視為同一聚類，刪除K測(cè)試用例集.

2 多目標(biāo)評(píng)價(jià)指標(biāo)

本文采用平均缺陷檢測(cè)率和有效執(zhí)行時(shí)間為測(cè)試用例個(gè)體適應(yīng)度評(píng)價(jià)函數(shù)，當(dāng)平均缺陷檢測(cè)率越大、有效執(zhí)行時(shí)間越小時(shí)，算法結(jié)果最優(yōu).

平均缺陷檢測(cè)率(average percentage of failure detection, APFD)的公式[8]如下：

其中：測(cè)試用例集為T，n代表測(cè)試用例總數(shù)，m為缺陷個(gè)數(shù)，TFi代表首個(gè)可以檢查到缺陷i的測(cè)試用例在這次測(cè)試用例集中的位置.

3 基于遺傳算法的MOTCP方法

MOTCP是在TCP基礎(chǔ)上出現(xiàn)的一種新的排序方式，相對(duì)于傳統(tǒng)TCP技術(shù)主要區(qū)別體現(xiàn)在以下兩個(gè)方面：一是在優(yōu)化目標(biāo)的個(gè)數(shù)選取上采用兩個(gè)及兩個(gè)以上的目標(biāo)，二是在排序算法上采用加權(quán)法或者帕累托最優(yōu)[9].相比于傳統(tǒng)的基于單目標(biāo)的遺傳算法，它很好地解決了結(jié)果片面性這個(gè)問題.MOTCP問題[10]描述如下：

遺傳算法是仿生物學(xué)算法，屬于進(jìn)化算法.它模仿自然生物進(jìn)化過程，通過多次迭代來尋找最優(yōu)解.一般的迭代算法很容易陷入局部最優(yōu)解，遺傳算法通過交叉運(yùn)算和變異運(yùn)算能較好地避免早熟.

基于遺傳算法在MOTCP問題上的應(yīng)用，其步驟如下：

(1)約簡(jiǎn)：對(duì)原始測(cè)試用例集進(jìn)行約簡(jiǎn)，刪除冗余測(cè)試用例，產(chǎn)生新的測(cè)試用例集；

(2)隨機(jī)產(chǎn)生初始群體F(0)，產(chǎn)生候選最優(yōu)非劣解P(F(0))；

(3)判斷算法是否滿足測(cè)試目標(biāo)條件.若滿足測(cè)試目標(biāo)條件，則執(zhí)行步驟(9)，若不滿足，則執(zhí)行步驟(4)；

(4)判斷算法是否達(dá)到最大迭代次數(shù).若達(dá)到最大迭代次數(shù)，則執(zhí)行步驟(9)，若沒有達(dá)到，則執(zhí)行步驟(5)；

(5)計(jì)算種群個(gè)體適應(yīng)度函數(shù)值；

(6)根據(jù)適應(yīng)度選擇產(chǎn)生子代種群；

(7)對(duì)子代種群進(jìn)行單點(diǎn)交叉/基本位變異運(yùn)算，從而產(chǎn)生新的種群F(t)和新的最優(yōu)非劣解P(F(t))；

(8)將P(F(0))與P(F(t))進(jìn)行支配關(guān)系比較，若P(F(t))完全支配P(F(0))中的個(gè)體，則將P(F(t))替換P(F(0))，否則不更新P(F(0)).然后執(zhí)行步驟(3)；

(9)算法結(jié)束，輸出最后結(jié)果.

3.1 選擇算子

遺傳算法中的選擇操作就是通過某種方式從父代中選擇出個(gè)體并遺傳下來.常用的選擇算子有輪盤賭選擇、隨機(jī)競(jìng)爭(zhēng)選擇、最佳保留選擇、無回訪隨機(jī)選擇等.本文采用最佳保留選擇算子，首先采用輪盤賭的方式，即每個(gè)個(gè)體進(jìn)入下一代的概率等于它的適應(yīng)度值和整個(gè)種群中的個(gè)體適應(yīng)度值之和的比例，然后將當(dāng)前適應(yīng)度最高的個(gè)體結(jié)構(gòu)完整地復(fù)制到下一代群體中，本文選擇將前10%的優(yōu)秀個(gè)體復(fù)制到下一代.

3.2 交叉變異運(yùn)算設(shè)計(jì)

遺傳算法中包含多種交叉運(yùn)算，比如單點(diǎn)交叉運(yùn)算、多點(diǎn)交叉運(yùn)算和循環(huán)交叉運(yùn)算等，交叉概率取值一般在0.4-0.9[11-12].同樣變異運(yùn)算包含基本位變異、均勻變異和邊界變異等，變異概率取值一般在0.001-0.1[11].本文采用單點(diǎn)交叉運(yùn)算和均勻變異進(jìn)行種群更新操作.

單點(diǎn)交叉運(yùn)算首先設(shè)置交叉概率，如果rand(1)產(chǎn)生的隨機(jī)數(shù)小于設(shè)置的交叉概率，則進(jìn)行交叉運(yùn)算，否則不進(jìn)行交叉運(yùn)算.假設(shè)存在父母?jìng)€(gè)體Q1和Q2需要進(jìn)行單點(diǎn)交叉運(yùn)算，首先隨機(jī)產(chǎn)生交叉點(diǎn)m，將Q1與Q2中m點(diǎn)位前的基因(不變)保留下來，m點(diǎn)位后的基因進(jìn)行一一對(duì)應(yīng)的交換.

均勻變異運(yùn)算首先設(shè)置變異概率，對(duì)每個(gè)種群的每個(gè)個(gè)體按變異概率進(jìn)行變異，若個(gè)體隨機(jī)概率小于變異概率，則隨機(jī)產(chǎn)生新的有效個(gè)體替換該個(gè)體.

3.3 更新最優(yōu)非劣解

求兩個(gè)目標(biāo)函數(shù)的最優(yōu)解，采用Pareto直接法[13-14]對(duì)其進(jìn)行更新，將候選最優(yōu)非劣解與新產(chǎn)生的解進(jìn)行支配關(guān)系比較，若候選最優(yōu)非劣解被新的解所支配，則采用新的解作為候選最優(yōu)解[15].為更直觀地表示，考慮存在5個(gè)測(cè)試用例以及8個(gè)缺陷，其覆蓋缺陷數(shù)以及執(zhí)行時(shí)間如表1和表2所示.

表1 覆蓋的缺陷數(shù)

表2 測(cè)試用例執(zhí)行時(shí)間

假設(shè)A-B-C-D為其候選最優(yōu)非劣解T1，則當(dāng)測(cè)試用例按照A-B-C-D的順序依次運(yùn)行時(shí)，其APFD取值為50%，其EET的取值為0.026 s.此時(shí)生成新的測(cè)試用例集F-B-C-D稱為T2，依次執(zhí)行，其APFD取值為59%，其EET取值為0.022 s，通過T1與T2的兩個(gè)目標(biāo)值進(jìn)行支配關(guān)系比較，顯然T1被T2支配，于是用T2替換掉T1.

4 仿真實(shí)驗(yàn)以及結(jié)果分析

實(shí)驗(yàn)從以下兩個(gè)方向驗(yàn)證本文提出方法的有效性：(1)本文提出的算法是否可以縮短測(cè)試執(zhí)行時(shí)間;(2)將遺傳算法引入MOTCP問題是否能提高缺陷檢測(cè)效率.

4.1 實(shí)驗(yàn)環(huán)境設(shè)計(jì)

本實(shí)驗(yàn)選用開源項(xiàng)目CDT進(jìn)行實(shí)驗(yàn).CDT是完全用Java實(shí)現(xiàn)的開源項(xiàng)目，作為Eclipse的平臺(tái)的插件，它提供對(duì)C/C++語(yǔ)言的開發(fā)支持.CDT包括CDT Core、CDT Feature Eclipse在內(nèi)的9個(gè)插件.CDT Core Test可實(shí)現(xiàn)對(duì)CDT Core插件的測(cè)試，CDT Core每個(gè)模塊及其子模塊均可單獨(dú)執(zhí)行其測(cè)試用例(總共包含12361個(gè)測(cè)試用例).本次實(shí)驗(yàn)選用CDT Core中的Model模塊及其320個(gè)測(cè)試用例進(jìn)行實(shí)驗(yàn).實(shí)驗(yàn)環(huán)境選用Visual Studio 2015，在Win10操作系統(tǒng)下運(yùn)行.算法參數(shù)設(shè)定參照現(xiàn)有研究設(shè)置.雜交概率設(shè)置為0.8，變異概率設(shè)置為0.15，種群大小為30，最大迭代次數(shù)為500.

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

將本文算法與傳統(tǒng)的遺傳算法(無約簡(jiǎn)、單目標(biāo))和多目標(biāo)優(yōu)先級(jí)排序方法進(jìn)行比較，獨(dú)立重復(fù)運(yùn)行30次，需求覆蓋率達(dá)到100%時(shí)或者達(dá)到最大迭代次數(shù)時(shí)停止運(yùn)行.然后以平均語(yǔ)句覆蓋率、平均EET、APFD平均值以及單個(gè)缺陷所需的平均測(cè)試用例數(shù)作為評(píng)價(jià)指標(biāo)，對(duì)比分析各算法的優(yōu)劣.將每個(gè)評(píng)價(jià)指標(biāo)的對(duì)比結(jié)果以條狀圖呈現(xiàn)如圖1和圖2所示，可以更加直觀地對(duì)比其優(yōu)劣.

圖1 平均語(yǔ)句覆蓋率和APFD平均值實(shí)驗(yàn)對(duì)比

圖2 平均EET值和單個(gè)缺陷測(cè)試(檢測(cè))所需平均測(cè)試用例數(shù)實(shí)驗(yàn)對(duì)比

由圖1和圖2可以清楚地看到:本文算法在這4個(gè)評(píng)價(jià)目標(biāo)上均優(yōu)于其他兩種方法，以平均EET值最為明顯，相較于單目標(biāo)遺傳算法減少了19.077 s，相較于多目標(biāo)優(yōu)化方法減少了6.659 s，這說明本文算法發(fā)揮了作用，對(duì)測(cè)試用例進(jìn)行聚類約簡(jiǎn)的操作在不影響測(cè)試需求的前提下減少了參與遺傳算法測(cè)試用例的總數(shù)，在多目標(biāo)指導(dǎo)種群更新的同時(shí)采用精英保留策略則減少了找到最優(yōu)解的迭代時(shí)間.平均語(yǔ)句覆蓋率的提升不明顯，首先因?yàn)檫x用模塊規(guī)模不大，其次覆蓋率不可能達(dá)到100%，所以當(dāng)達(dá)到循環(huán)次數(shù)時(shí)，其基本測(cè)試用例的語(yǔ)句覆蓋率已經(jīng)接近瓶頸，所以覆蓋率提升不大.而APFD的平均值的增加，單個(gè)缺陷檢測(cè)所需的平均測(cè)試用例數(shù)的減少說明了本文提出的算法相對(duì)于其他兩種方法達(dá)到了使用較少的測(cè)試用例找到較多的軟件缺陷的目的，有效地提高了軟件缺陷檢測(cè)的效率，達(dá)到提升回歸測(cè)試效率的效果.

5 總結(jié)

本文提出了一種基于遺傳算法的多目標(biāo)測(cè)試用例排序方法.測(cè)試開始前對(duì)所有測(cè)試用例進(jìn)行約簡(jiǎn)，采用多目標(biāo)評(píng)價(jià)算法指導(dǎo)種群的迭代更新，通過Pareto直接比較法得到最優(yōu)非劣解，從而提高缺陷檢測(cè)效率，減少了測(cè)試用例運(yùn)行時(shí)間，實(shí)驗(yàn)證明本文提出的算法在提升回歸測(cè)試效率和缺陷檢測(cè)上有優(yōu)勢(shì).