李龍澍,郭紫夢(mèng)

(安徽大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,合肥 230601)

1 引 言

伴隨軟件應(yīng)用領(lǐng)域和軟件規(guī)模不停的擴(kuò)展和增大,軟件的質(zhì)量顯得愈發(fā)重要.軟件測(cè)試是保障軟件質(zhì)量的關(guān)鍵技術(shù)措施,通常從始至終貫穿著全部的軟件研發(fā)流程,軟件測(cè)試的重點(diǎn)就在于測(cè)試用例的編寫(xiě),測(cè)試用例的自動(dòng)化便成為軟件測(cè)試的重中之重[1].路徑覆蓋測(cè)試是指在測(cè)試過(guò)程中,選擇有效且充足的測(cè)試數(shù)據(jù),除去不可能路徑,使得測(cè)試程序中的其余所有路徑都存在至少一條對(duì)應(yīng)的測(cè)試數(shù)據(jù).在現(xiàn)實(shí)測(cè)試中,眾多軟件測(cè)試問(wèn)題都可以轉(zhuǎn)化為路徑覆蓋測(cè)試的數(shù)據(jù)生成問(wèn)題.

S Xanthakis 等人在1992年,初次提出采取遺傳算法進(jìn)化生成路徑覆蓋測(cè)試用例的思想,因此首創(chuàng)了一個(gè)嶄新的研究領(lǐng)域[2].自此后,遺傳算法便廣泛的運(yùn)用在路徑覆蓋測(cè)試研究領(lǐng)域內(nèi),從而出現(xiàn)多量的相關(guān)研究文獻(xiàn).夏春艷等人從穿過(guò)節(jié)點(diǎn)的困難情況出發(fā),用遺傳算法實(shí)現(xiàn)路徑覆蓋測(cè)試[3];丁蕊等人提出關(guān)鍵點(diǎn)路徑表示法,改進(jìn)算法適應(yīng)度函數(shù),以快速生成路徑覆蓋測(cè)試數(shù)據(jù)[4];鞏敦衛(wèi)等人采用Huffman Coding提出一種新的多路徑覆蓋測(cè)試數(shù)據(jù)的進(jìn)化方法[5];張巖等人從種群的搜索空間這一角度入手,提出一種新的路徑覆蓋測(cè)試進(jìn)化技術(shù)[6];隨后,張巖等人在前文的基礎(chǔ)之上,再次提出測(cè)試數(shù)據(jù)具有不同貢獻(xiàn)度的思想,以參數(shù)來(lái)調(diào)節(jié)個(gè)體的適應(yīng)度值[7];Pachauri A等人提出一種擴(kuò)展路徑前綴的策略,使用遺傳算法實(shí)現(xiàn)分支覆蓋[8];Peng Ye-ping 等人從路徑匹配的角度入手,實(shí)現(xiàn)了多條目標(biāo)路徑同時(shí)覆蓋的測(cè)試進(jìn)化方法[9];Jakkrit Kaewyotha等人用循環(huán)結(jié)構(gòu)尋找關(guān)鍵路徑,使用遺傳算法進(jìn)行基本路徑測(cè)試[10];Ghiduk Ahmed S重新定義了遺傳算法中染色體、交叉和變異等概念,用以快速覆蓋路徑[12].這些方法在處理路徑覆蓋測(cè)試這一領(lǐng)域的問(wèn)題時(shí),多是選取遺傳算法,通過(guò)對(duì)算法的適應(yīng)度函數(shù)做些改進(jìn),或者交叉算子,變異算子的重定義及優(yōu)化,以此來(lái)提高算法生成測(cè)試數(shù)據(jù)的效率.但是,鑒于遺傳算法原理上的制約,導(dǎo)致在處理較為復(fù)雜的路徑覆蓋時(shí),會(huì)出現(xiàn)計(jì)算量爆炸增長(zhǎng)的現(xiàn)象[13],從而不能高效的處理路徑覆蓋測(cè)試問(wèn)題.

在 2011 年,學(xué)者潘文超提出一種新的智能算法——果蠅優(yōu)化算法(Fruit Fly Optimization Algorithm,FOA),該算法是從果蠅搜尋食物行為中得出的一種全新的智能優(yōu)化算法[14],具有程序簡(jiǎn)單,尋優(yōu)精度高等特點(diǎn),最突出的優(yōu)點(diǎn)是該算法計(jì)算量小,復(fù)雜度低,在復(fù)雜問(wèn)題下不會(huì)出現(xiàn)計(jì)算量爆炸增長(zhǎng)的現(xiàn)象,已在求解數(shù)學(xué)函數(shù)極值、微調(diào)Z-SCORE模型系數(shù)、廣義回歸神經(jīng)網(wǎng)絡(luò)參數(shù)優(yōu)化與支持向量機(jī)參數(shù)優(yōu)化等多個(gè)領(lǐng)域得到廣泛應(yīng)用.同時(shí)該算法具有不穩(wěn)定性因素,存在著“早熟”現(xiàn)象,針對(duì)這一現(xiàn)象,眾多研究學(xué)者引入混沌策略來(lái)保持種群的多樣性,跳出局部最優(yōu),尋找全局最優(yōu).唐賢倫等人提出多目標(biāo)混沌來(lái)優(yōu)化PSO算法[15];范九倫等人對(duì)Logistic方程做出一種分段處理,使得其具有優(yōu)異的非線性征象[16].Cheng YuHuei提出一種基于正弦的混沌策略,以此來(lái)調(diào)整PSO中的函數(shù)參數(shù)[17];Rezaee Jordehi A利用混沌搜索策略優(yōu)化蝙蝠群算法[18].這些針對(duì)“早熟”現(xiàn)象改進(jìn)的研究,均取得了較好的效果.

在遺傳算法、果蠅優(yōu)化算法的優(yōu)缺點(diǎn)及文獻(xiàn)[16]的啟發(fā)下,本文提出一種基于混沌果蠅優(yōu)化算法(C-FOA)的路徑覆蓋測(cè)試用例生成方法:通過(guò)對(duì)算法進(jìn)行建模及設(shè)計(jì)味道濃度判定函數(shù)(適應(yīng)度函數(shù)),使之運(yùn)用于路徑覆蓋測(cè)試領(lǐng)域;同時(shí)對(duì)果蠅優(yōu)化算法每次迭代中的最優(yōu)個(gè)體加入混沌操作,使其跳出局部最優(yōu),快速地覆蓋目標(biāo)路徑.最后,經(jīng)過(guò)仿真實(shí)驗(yàn),分析考驗(yàn)了本文方法的有效性.

2 混沌果蠅優(yōu)化算法

2.1 標(biāo)準(zhǔn)果蠅優(yōu)化算法(FOA)

果蠅優(yōu)化算法,其原始想法來(lái)源于果蠅在找尋食物時(shí)的飛行行為.果蠅這一物種具有天然良好的感官知覺(jué),在找尋食物時(shí),首先會(huì)利用優(yōu)異的嗅覺(jué)能力搜尋食物的氣味,根據(jù)氣味調(diào)整飛行的方向,同時(shí)在距離食物位置較近時(shí),再次利用敏感的視覺(jué)能力,兩者相結(jié)合以此來(lái)找到食物.根據(jù)這一行為特性,FOA算法基本思路如下[13]:

1)設(shè)置果蠅種群數(shù)目為 NP,最大迭代次數(shù)為 Maxgen,并任意給出果蠅種群二維開(kāi)始位置為 X_axis,Y_axis.

2)給予果蠅個(gè)體運(yùn)動(dòng)的隨機(jī)方向與間隔,random value為運(yùn)動(dòng)的間隔.

Xi=X_axis+RandomValueYi=Y_axis+RandomValue

(1)

3)求出果蠅個(gè)體與原點(diǎn)的間隔Dist、味道濃度判定值S和味道濃度Smell.

(2)

4)得到該種群中Smell值最大的果蠅個(gè)體,記為當(dāng)前最優(yōu)果蠅個(gè)體.

[bestSmellbestIndex]=max(Smell)

(3)

5)判斷當(dāng)前最優(yōu)個(gè)體濃度值bestSmell是否高于上一次迭代的最優(yōu)味道濃度值,若是,執(zhí)行(6);若否,執(zhí)行(7).

6)保存下來(lái)當(dāng)前最優(yōu)個(gè)體的味道濃度值與其二維坐標(biāo)X、Y,其他果蠅個(gè)體則操縱方向飛往最優(yōu)位置.

Smellbest=bestSmellX_axis=X(bestIndex)Y_axis=Y(bestIndex)

(4)

7)判斷是否滿足結(jié)束條件,若是,則結(jié)束;反之,執(zhí)行2).

2.2 混沌果蠅優(yōu)化算法(C-FOA)

果蠅優(yōu)化算法的不足之處在于其穩(wěn)定性差,易出現(xiàn)“早熟”現(xiàn)象,從而導(dǎo)致收斂速率減緩,收斂精度降低,甚至于不能獲取全局最優(yōu)值.混沌是天然的一種普遍的非線性征象.表面上是紊亂無(wú)序的混沌變量,實(shí)際卻蘊(yùn)含著一種深層的內(nèi)在聯(lián)系,眾多學(xué)者利用這種深層聯(lián)系進(jìn)化搜索來(lái)達(dá)到相應(yīng)效果[19].在FOA中融入混沌策略,提升算法脫離局部最優(yōu)的能力,從而使得算法收斂的速率和精度得以提高.

本文使用Logistic映射的混沌方法.Logistic映射是探究混沌等繁雜體系行徑的一個(gè)典型模型.按照如下方程進(jìn)行反復(fù)迭代:

Z(t+1)=μZ(t)(1-Z(t))

(5)

式(5)中μ為控制參量,當(dāng)μ=4,0≤Z0≤1,Logistic 處于絕對(duì)混沌狀態(tài).對(duì)于任何指定的Z0∈[0,1],均可迭代出唯一明確的混沌序列Z1,Z2,Z3,….

基于混沌策略的果蠅優(yōu)化算法的基礎(chǔ)思想為:每次迭代過(guò)程中,對(duì)整個(gè)果蠅群體搜尋到的最優(yōu)個(gè)體A進(jìn)行混沌擾動(dòng)操作,將混沌序列中的最優(yōu)個(gè)體A*保留,以A和A*各自為中心的隨機(jī)搜索方向和距離范圍內(nèi)產(chǎn)生一半種群個(gè)體,并搜索到當(dāng)前迭代過(guò)程中的最優(yōu)值,繼續(xù)進(jìn)行混沌操作.融入混沌策略的進(jìn)化算法可在迭代中不斷產(chǎn)生局部最優(yōu)點(diǎn)運(yùn)動(dòng)距離外的混沌個(gè)體,協(xié)助相應(yīng)算法跳出局部極值點(diǎn),以此更快的搜尋到全局最優(yōu)值.

3 基于混沌果蠅的路徑覆蓋測(cè)試用例生成方法

3.1 路徑覆蓋測(cè)試問(wèn)題描述

本小節(jié)通過(guò)一個(gè)實(shí)例來(lái)描述如何通過(guò)路徑覆蓋來(lái)達(dá)到測(cè)試的目的.首先,為了得到測(cè)試數(shù)據(jù)在程序中的運(yùn)行走向,需要對(duì)程序加入插樁.如圖1所示,是一個(gè)插樁后的三角形分類程序,輸入一組數(shù)據(jù)(a,b,c),運(yùn)行該程序得到標(biāo)識(shí)變量序列,通過(guò)與目標(biāo)路徑對(duì)應(yīng)的標(biāo)識(shí)變量序列對(duì)比,來(lái)判斷是否覆蓋目標(biāo)路徑.本文中使用的三角形程序借鑒了文獻(xiàn)[20]中的三角形程序,并對(duì)其稍加改動(dòng),此程序包含2個(gè)多分支選擇關(guān)系,以及4個(gè)選擇并列關(guān)系,剔除不可行路徑后,共有19條可行路徑,將分別作為需要覆蓋的目標(biāo)路徑.

3.2 C-FOA算法的路徑覆蓋測(cè)試

在路徑覆蓋測(cè)試中,利用果蠅優(yōu)化算法的收斂性迭代出最優(yōu)個(gè)體來(lái)達(dá)到測(cè)試目標(biāo).將每個(gè)果蠅個(gè)體作為一條測(cè)試數(shù)據(jù),設(shè)F0=(t1,t2,…,tm)表示路徑覆蓋測(cè)試中的目標(biāo)路徑標(biāo)識(shí)序列,于是該問(wèn)題就轉(zhuǎn)化為尋找最優(yōu)向量(x1,x2,…,xm)覆蓋目標(biāo)路徑標(biāo)識(shí)序列,具體如下:

1)編碼

C-FOA算法采用整數(shù)編碼方式,每個(gè)整數(shù)代表相應(yīng)果蠅個(gè)體在該維度上的分量位置,其范圍為[min,max],其中min為該維度上的最小值,max為該維度上的最大值.

圖1 三角形分類插樁程序
Fig.1 Instrumentation program of triangular classification

2)果蠅個(gè)體

果蠅個(gè)體Gi(x1,x2,…,xj,…,xm),其中xj為整數(shù),表示第i個(gè)果蠅個(gè)體在第j維度上的分量位置,N個(gè)果蠅個(gè)體構(gòu)成果蠅種群,記為G={G1,G2,…,Gn}.

3)混沌果蠅個(gè)體

4)味道濃度函數(shù)

味道濃度函數(shù)代表著果蠅個(gè)體的效用,用Fitness表示,以此用來(lái)區(qū)分不同果蠅個(gè)體間的優(yōu)劣情況,進(jìn)而挑選出最優(yōu)的那一個(gè)個(gè)體.本文的味道濃度函數(shù)依據(jù)路徑覆蓋測(cè)試適應(yīng)度函數(shù)的設(shè)計(jì),分為層接近度(approach_level)和分支距離(branch_distance)兩部分相結(jié)合.

假設(shè)果蠅個(gè)體Gi穿越的路徑標(biāo)識(shí)序列為F(Gi),目標(biāo)測(cè)試路徑標(biāo)識(shí)序列為F0.Gi的層接近度為approach_level(Gi),計(jì)算方法為:統(tǒng)計(jì)F(Gi)與F0相同標(biāo)識(shí)變量的個(gè)數(shù),用其除以目標(biāo)測(cè)試路徑標(biāo)識(shí)序列F0的標(biāo)識(shí)變量總數(shù)來(lái)計(jì)算,故層接近度值與個(gè)體的優(yōu)異程度成正比;分支距離為branch_distance(Gi),計(jì)算方法與Tracey方法相同[21].同時(shí)為防止分支距離過(guò)大,從而使層接近度失去引導(dǎo)作用,將其采取1.001-branch_distance(Gi)做出標(biāo)準(zhǔn)化操作,故分支距離值與個(gè)體的優(yōu)異程度成正比.

于是,個(gè)體Gi的味道濃度Fitness(Gi)可表示為:

Fitness(Gi)=approach_level(Gi)+1.001-branch_distance(Gi)

(6)

由式(6)可得,個(gè)體Gi的味道濃度Fitness(Gi)與個(gè)體的優(yōu)異程度成正比.

3.3 算法步驟

假設(shè)需要覆蓋的目標(biāo)路徑為F0,C-FOA算法具體流程如下:

輸入:群體數(shù)量為 N,最大迭代次數(shù)為 Maxgen,混沌次數(shù)為K,并隨機(jī)果蠅群體m維開(kāi)始位置X1_axis,X2_axis,…,Xm_axis

輸出:目標(biāo)測(cè)試數(shù)據(jù)x1,x2,…,xm

Step1.給予果蠅個(gè)體Gi的隨機(jī)方向與間隔,xi=Xi_axis+randomvalue,(i=1,2,…,m);

Step2.運(yùn)行插樁后的程序;

Step3.根據(jù)公式(6)計(jì)算每只果蠅的味道濃度值,并找出其中濃度最高的;

Step4.判斷當(dāng)前最優(yōu)個(gè)體的濃度值是否高于上一次迭代的值,若是,保存最優(yōu)個(gè)體GBest(x1,x2,…,xm),若否,繼續(xù)下一步;

Step5.判斷是否覆蓋目標(biāo)路徑F0,或達(dá)到最大迭代次數(shù),若是,跳轉(zhuǎn)Step 8,若否,繼續(xù)下一步;

Step7.給予個(gè)體GBest*和GBest的隨機(jī)方向與間隔,且分別對(duì)GBest*和GBest給予一半種群數(shù)目的個(gè)體,跳轉(zhuǎn)Step 2;

Step8.終止種群的進(jìn)化,保存并輸出相應(yīng)的測(cè)試結(jié)果.

C-FOA算法過(guò)程對(duì)應(yīng)的流程圖如圖2所示.

圖2 算法流程圖Fig.2 Algorithm flowchart

為了防止混沌策略太過(guò)干擾最優(yōu)值的尋找,同時(shí)也為了保持FOA計(jì)算量小的優(yōu)勢(shì),根據(jù)情況對(duì)混沌次數(shù)做出了恰當(dāng)?shù)恼{(diào)整,即每?jī)蓚€(gè)周期添加一次混沌干擾.即使算法在未添加混沌的周期內(nèi)出現(xiàn)“早熟”征兆,隨后的混沌干擾便會(huì)迅速的使算法脫離局部極值.

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

為了確定本文方法的實(shí)際可操作性及有效性,選擇 3 個(gè)基準(zhǔn)程序進(jìn)行考驗(yàn).將本文方法(C-FOA)與同類方法(即GA方法、ACO方法、FOA方法、及文獻(xiàn)[11]中改進(jìn)的GA方法)在同樣的被測(cè)程序上實(shí)驗(yàn).每組實(shí)驗(yàn)結(jié)果都將與同類方法的結(jié)果進(jìn)行比較分析.

為了降低隨機(jī)性的誤差,5種方法的選擇依據(jù)均是使用分支距離和層接近度相結(jié)合作為適應(yīng)度函數(shù)(即味道濃度函數(shù)),并且均選取相同的參數(shù)設(shè)置進(jìn)化生成測(cè)試數(shù)據(jù).同時(shí),以生成覆蓋目標(biāo)路徑的測(cè)試數(shù)據(jù)或達(dá)到最大迭代次數(shù)作為算法運(yùn)行的終止條件,針對(duì)不同程序每種情況獨(dú)立運(yùn)行 20 次后取其平均值.與其對(duì)比,可以更好地驗(yàn)證本文方法生成測(cè)試數(shù)據(jù)的效率.

共進(jìn)行了兩組實(shí)驗(yàn),第一組為在不同迭代次數(shù)下的覆蓋率;第二組為找到覆蓋目標(biāo)路徑測(cè)試數(shù)據(jù)的評(píng)價(jià)次數(shù)與運(yùn)行時(shí)間.實(shí)驗(yàn)條件:Windows 7 操作系統(tǒng),MyEclipse 10仿真環(huán)境,計(jì)算機(jī)主頻 2.80GHz,內(nèi)存4GB.

4.1 基準(zhǔn)程序

表1 被測(cè)程序的基本信息
Table 1 Basic information of tested programs

程序分支結(jié)構(gòu)三個(gè)數(shù)排序3個(gè)選擇并列關(guān)系三角形分類2個(gè)多分支選擇結(jié)構(gòu)，4個(gè)選擇并列關(guān)系冒泡程序 2層循環(huán)嵌套，內(nèi)層嵌套含有1個(gè)選擇結(jié)構(gòu)輸入分量個(gè)數(shù)目標(biāo)路徑數(shù)代碼行數(shù)插樁節(jié)點(diǎn)數(shù)37183319276434246

4.2 對(duì)比實(shí)驗(yàn)

實(shí)驗(yàn)1.不同迭代次數(shù)下的覆蓋率

程序輸入變量取值范圍為 0-1023 之間的整數(shù),種群大小為 50.對(duì)三個(gè)基準(zhǔn)程序,分別在限定迭代次數(shù)為1、50、100、150、200的條件下,對(duì)于所有目標(biāo)路徑進(jìn)行覆蓋測(cè)試,得到相應(yīng)的覆蓋率,如圖3-圖5.

圖3 三個(gè)數(shù)排序覆蓋率Fig.3 Coverage of ranking of three numbers

由圖3-圖5可得:

1)從遺傳算法、蟻群算法和果蠅優(yōu)化算法的對(duì)比可以看出,在相同環(huán)境下,FOA的覆蓋率在多數(shù)情況下是高于GA和ACO的,說(shuō)明FOA方法應(yīng)用在路徑覆蓋測(cè)試領(lǐng)域內(nèi)是可行的.

圖4 三角形分類覆蓋率Fig.4 Coverage of triangular classification

2)在三個(gè)基準(zhǔn)程序中,本文方法的覆蓋率明顯高于另外四種方法,特別是,在未達(dá)到完全覆蓋時(shí),本文方法具有更高的覆蓋率;在均能達(dá)到完全覆蓋時(shí),本文方法具有更快的覆蓋速度.綜合以上,本文方法生成測(cè)試數(shù)據(jù)的效率高于同類方法.

圖5 冒泡排序覆蓋率Fig.5 Coverage of bubble sort

實(shí)驗(yàn)2.覆蓋目標(biāo)路徑下的評(píng)價(jià)次數(shù)與運(yùn)行時(shí)間

程序輸入變量取值范圍為 0-127 之間的整數(shù),種群大小為 50.對(duì)三個(gè)基準(zhǔn)程序進(jìn)行所有目標(biāo)路徑的覆蓋測(cè)試,得到相應(yīng)的評(píng)價(jià)次數(shù)與運(yùn)行時(shí)間.若評(píng)價(jià)次數(shù)超過(guò)1000,即認(rèn)為該路徑的測(cè)試數(shù)據(jù)尋找失敗.具體結(jié)果如表2.

表2 覆蓋全部目標(biāo)路徑下的評(píng)價(jià)次數(shù)與運(yùn)行時(shí)間
Table 2 Evaluation times and runtime with all the target paths covered

測(cè)試函數(shù)GAACO評(píng)價(jià)次數(shù)運(yùn)行時(shí)間(S)覆蓋率(%)評(píng)價(jià)次數(shù)運(yùn)行時(shí)間(S)覆蓋率(%)三個(gè)數(shù)排序29．330．99510021．670．898100三角形分類495．6516．45694．74195．829．313100冒泡排序 246．439．399100149．146．298100測(cè)試函數(shù)FOA文獻(xiàn)[11]的GA評(píng)價(jià)次數(shù)運(yùn)行時(shí)間(S)覆蓋率(%)評(píng)價(jià)次數(shù)運(yùn)行時(shí)間(S)覆蓋率(%)三個(gè)數(shù)排序21．480．72710011．630．725100三角形分類187．846．37910076．104．744100冒泡排序 133．174．52210097．126．054100測(cè)試函數(shù)C?FOA評(píng)價(jià)次數(shù)運(yùn)行時(shí)間(S)覆蓋率(%)三個(gè)數(shù)排序9．750．659100三角形分類54．263．682100冒泡排序 92．533．142100

由表2可以得到:

1)從評(píng)價(jià)次數(shù)來(lái)看,在5種方法中,本文方法以最少的評(píng)價(jià)次數(shù)獲取了所有的測(cè)試數(shù)據(jù).如在三角形分類程序中,本文方法的評(píng)價(jià)次數(shù)為54.26,遺傳算法的評(píng)價(jià)次數(shù)為495.65,且未能全部覆蓋,蟻群算法的評(píng)價(jià)次數(shù)為195.82,果蠅算法的評(píng)價(jià)次數(shù)為187.84,文獻(xiàn)[11]中遺傳算法的評(píng)價(jià)次數(shù)為76.10.以上數(shù)據(jù)說(shuō)明本文方法的性能優(yōu)于同類方法;

2)從運(yùn)行時(shí)間來(lái)看,本文方法的運(yùn)行時(shí)間明顯少于另外4種方法.特別是,隨著程序的復(fù)雜度增加,本文方法的優(yōu)勢(shì)更加明顯,這是因?yàn)?本文方法具有計(jì)算量小,復(fù)雜度低等優(yōu)勢(shì),再次證明本文方法生成測(cè)試用例的效能優(yōu)于同類方法;

3)從覆蓋成功率來(lái)看,隨著目標(biāo)路徑的增多以及路徑復(fù)雜程度的增加,本文方法的評(píng)價(jià)次數(shù)和運(yùn)行時(shí)間也有所增加.但是本文方法仍能有效生成測(cè)試數(shù)據(jù).而且生成測(cè)試數(shù)據(jù)的成功率均可達(dá)到 100%,說(shuō)明本文方法具有有效性.

通過(guò)以上的兩組實(shí)驗(yàn),本文方法充分考驗(yàn)了 FOA 算法應(yīng)用在路徑覆蓋測(cè)試用例進(jìn)化生成領(lǐng)域內(nèi)的可行性,并且考證了本文方法生成路徑覆蓋測(cè)試數(shù)據(jù)的有效性,提升了獲取測(cè)試用例的效率.

5 結(jié) 論

鑒于果蠅優(yōu)化算法和遺傳算法等智能算法同屬于一類算法,同時(shí)果蠅優(yōu)化算法具有計(jì)算量小,復(fù)雜度低,尋優(yōu)精度高等優(yōu)點(diǎn),本文把果蠅優(yōu)化算法應(yīng)用到路徑覆蓋測(cè)試領(lǐng)域內(nèi),并針對(duì)果蠅優(yōu)化算法穩(wěn)定性差的缺點(diǎn),對(duì)迭代過(guò)程中的最優(yōu)個(gè)體加入混沌策略,在保留優(yōu)秀個(gè)體的同時(shí),增加種群多樣性,優(yōu)化全局搜索能力,加快算法收斂速度,有效提高了生成測(cè)試數(shù)據(jù)的效率.實(shí)驗(yàn)結(jié)果表明,本文方法與同類方法相比生成測(cè)試數(shù)據(jù)的效率更高.

[1] Dong Yue-hua,Dai Yu-qian.Automatic software test data generation based on DPPSO[J].Journal of Chinese Computer Systems,2015,36(9):2015-2020.

[2] Xanthakis S,Ellis C,Skourlas C,et al.Application of genetic algorithms to software testing[C].Perry D,Jeffery R,Notkin D,eds.Proceedings of the 5th International Conference on Software Engineering and its Applications.Los Alamitos:IEEE,1992:625-636.

[3] Xia Chun-yan,Zhang Yan,Song Li.Evolutionary generation of test data for paths coverage based on node probability[J].Journal of Software,2016,27(4):802-813.

[4] Ding Rui,Dong Hong-Bin,Zhang Yan,et al.Fast automatic generation method for software testing data based on key-point path[J].Journal of Software,2016,27(4):814-827.

[5] Gong Dun-wei,Zhang Yan.Novel evolutionary generation approach to test data for multiple paths coverage[J].Acta Electronica Sinica,2010,38(6):1299-1304.

[6] Zhang Yan,Gong Dun-wei.Evolutionary generation of test data for path coverage based on automatic reduction of search space[J].Acta Electronica Sinica,2012,40(5):1011-1016.

[7] Zhang Yan,Gong Dun-wei.Evolutionary generation of test data for paths coverage based on scarce data capturing[J].Chinese Journal of Computers,2013,36(12):2429-2440.

[8] Pachauri A,Srivasatava G.Towards a parallel approach for test data generation for branch coverage with genetic algorithm using the extended path prefix strategy[C].International Conference on Computing for Sustainable Global Development.IEEE,2015:1786-1792.

[9] Peng Ye-ping,Zeng Bi.Software test data generation for multiple paths based on genetic algorithms[J].Applied Mechanics & Materials,2012,263-266:1969-1973.

[10] Jakkrit Kaewyotha,Wararat Songpan.Finding the critical path with loop structure for a basis path testing using genetic algorithm[M].Recent Advances in Information and Communication Technology 2015,Springer International Publishing,2015:41-52.

[11] You Feng,Zhao Rui-lian,Lv Shan-shan.Output domain based automatic test case generation[J].Journal of Computer Research and Development,2016(3):541-549.

[12] Ghiduk Ahmed S.Automatic generation of basis test paths using variable length genetic algorithm[J].Information Processing Letters,2014,114(6):304-316.

[13] Zhang Wei-xiang,Wei Bo,Du Hui-sen.Test case prioritization method based on genetic algorithm [J].Journal of Chinese Computer Systems,2015,36(9):1998-2002.

[14] Fan Wen-chao.Fruit fly optimization algorithm-a new evolutionary computation approach[M].Taiwan:Tsang Hai Publishing,2011.

[15] Tang Xian-lun,Zhou Wei,Zhang Heng,et al.Robot soccer defensive strategy based on multi-objective chaotic PSO[J].Journal of System Simulation,2014,26(1):51-61.

[16] Fan Jiu-lun,Zhang Xue-feng.Piecewise logistic chaotic map and its performance analysis [J].Acta Electronica Sinica,2009,37(4):720-725.

[17] Cheng Yu-huei.Evaluation of sine-based chaotic strategy for adapting inertia weight of particle swarm optimization[J].Lecture Notes in Engineering & Computer Science,2015,1(1):36-40.

[18] Rezaee Jordehi A.Chaotic bat swarm optimisation(CBSO)[J].Applied Soft Computing,2015,26(C):523-530.

[19] Chuang Li-yeh,Tsai Sheng-wei,Yang Cheng-hong.Improved binary particle swarm optimization using catfish effect for feature selection[J].Expert Systems with Applications,2011,38(10):12699-12707.

[20] Wu Chuan,Gong Dun-wei.Evolutionary generation of Test data for regression testing based on path correlation [J].Chinese Journal of Computers,2015(11):2247-2261.

[21] Zhang Yan.Theories and methods of evolutionary generation of test data for path coverage[D].Beijing:China University of Mining and Technology,2012.

附中文參考文獻(xiàn)：

[1] 董躍華,戴玉倩.一種改進(jìn)PSO的軟件測(cè)試數(shù)據(jù)自動(dòng)生成算法[J].小型微型計(jì)算機(jī)系統(tǒng),2015,36(9):2015-2020.

[3] 夏春艷,張 巖,宋 麗.基于節(jié)點(diǎn)概率的路徑覆蓋測(cè)試數(shù)據(jù)進(jìn)化生成[J].軟件學(xué)報(bào),2016,27(4):802-813.

[4] 丁 蕊,董紅斌,張 巖,等.基于關(guān)鍵點(diǎn)路徑的快速測(cè)試用例自動(dòng)生成方法[J].軟件學(xué)報(bào),2016,27(4):814-827.

[5] 鞏敦衛(wèi),張 巖.一種新的多路徑覆蓋測(cè)試數(shù)據(jù)進(jìn)化生成方法[J].電子學(xué)報(bào),2010,38(6):1299-1304.

[6] 張 巖,鞏敦衛(wèi).基于搜索空間自動(dòng)縮減的路徑覆蓋測(cè)試數(shù)據(jù)進(jìn)化生成[J].電子學(xué)報(bào),2012,40(5):1011-1016.

[7] 張 巖,鞏敦衛(wèi).基于稀有數(shù)據(jù)撲捉的路徑覆蓋測(cè)試數(shù)據(jù)進(jìn)化生成方法[J].計(jì)算機(jī)學(xué)報(bào),2013,36(12):2429-2440.

[11] 尤 楓,趙瑞蓮,呂珊珊.基于輸出域的測(cè)試用例自動(dòng)生成方法研究[J].計(jì)算機(jī)研究與發(fā)展,2016(3):541-549.

[13] 張衛(wèi)祥,魏 波,杜會(huì)森.一種基于遺傳算法的測(cè)試用例優(yōu)先排序方法[J].小型微型計(jì)算機(jī)系統(tǒng),2015,36(9):1998-2002.

[14] 潘文超.果蠅最佳化演算法—最新演化式計(jì)算技術(shù)[M].臺(tái)灣:滄海書(shū)局,2011.

[15] 唐賢倫,周 維,張 衡,等.一種基于多目標(biāo)混沌 PSO 的機(jī)器人足球防守策略[J].系統(tǒng)仿真學(xué)報(bào),2014,26(1):51-61.

[16] 范九倫,張雪鋒.分段Logistic混沌映射及其性能分析[J].電子學(xué)報(bào),2009,37(4):720-725.

[20] 吳 川,鞏敦衛(wèi).基于路徑相關(guān)性的回歸測(cè)試數(shù)據(jù)進(jìn)化生成[J].計(jì)算機(jī)學(xué)報(bào),2015(11):2247-2261.

[21] 張 巖.路徑覆蓋測(cè)試數(shù)據(jù)進(jìn)化生成理論與方法[D].北京：中國(guó)礦業(yè)大學(xué),2012.