應(yīng)用自適應(yīng)差分進(jìn)化算法優(yōu)化測(cè)試數(shù)據(jù)研究

李龍澍,翁晴晴

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

1 引 言

軟件測(cè)試是測(cè)試人員對(duì)開發(fā)人員所開發(fā)的軟件進(jìn)行測(cè)試,盡可能多地發(fā)現(xiàn)軟件中存在的錯(cuò)誤,以保證開發(fā)人員所開發(fā)的軟件正確且沒有潛在的缺陷.因此軟件測(cè)試是軟件開發(fā)周期中非常重要的環(huán)節(jié)[1].

遺傳算法作為傳統(tǒng)的用于生成軟件測(cè)試數(shù)據(jù)的算法,其應(yīng)用范圍非常廣泛[2].但傳統(tǒng)的遺傳算法通常表現(xiàn)出收斂速度慢,易陷入局部最優(yōu)等缺陷.近幾年有人提出通過將遺傳算法與蟻群算法或粒子群優(yōu)化算法等智能算法相結(jié)合的方案[3],用以提高算法效率.但是遺傳算法和PSO算法參數(shù)過多,不同的參數(shù)設(shè)置對(duì)最終結(jié)果影響較大,因此在實(shí)際應(yīng)用中,需不斷調(diào)整,加大了算法的使用難度.自適應(yīng)差分進(jìn)化算法[4,5]僅需調(diào)整縮放因子F與交叉概率Cr,且可以自動(dòng)調(diào)節(jié)縮放因子和交叉概率,能夠更加有效地提高收斂速度及防止陷入局部最優(yōu).與其他進(jìn)化算法相比,自適應(yīng)差分進(jìn)化算法相對(duì)簡(jiǎn)單,且能夠快速收斂到最優(yōu)值附近.因此,本文對(duì)自適應(yīng)差分進(jìn)化算法進(jìn)行改進(jìn),并用于測(cè)試數(shù)據(jù)的產(chǎn)生.

Storn和Price[6]首次提出差分進(jìn)化算法,該算法相對(duì)簡(jiǎn)單而且可以直接針對(duì)實(shí)數(shù)進(jìn)行尋優(yōu).目前,差分進(jìn)化算法已廣泛應(yīng)用于解決目標(biāo)優(yōu)化問題,如帶約束的優(yōu)化問題[7],多目標(biāo)優(yōu)化問題[8]和工程設(shè)計(jì)優(yōu)化問題[9]等.但是,差分進(jìn)化算法的控制參數(shù)需要根據(jù)先驗(yàn)知識(shí)提前設(shè)置,不夠靈活.針對(duì)以上問題,不同的適應(yīng)性差分進(jìn)化算法相繼被提出[10-12];其中,Zhang 和 Sanderson[10]提出的自適應(yīng)性的差分進(jìn)化算法(JADE),利用上一代優(yōu)越個(gè)體的縮放因子和交叉概率來更新當(dāng)前每個(gè)個(gè)體的控制參數(shù),很好地防止算法進(jìn)入早熟,并且大大增強(qiáng)了算法的靈活性.但是,JADE的變異策略是從100*p%(p為概率)種群中隨機(jī)選取一個(gè)個(gè)體取代當(dāng)前最優(yōu)個(gè)體,降低了差分進(jìn)化算法的收斂速度.

通過對(duì)差分進(jìn)化算法的研究發(fā)現(xiàn),差分進(jìn)化算法的性能與其變異操作有很大關(guān)聯(lián).本文所提出的基于質(zhì)心的自適應(yīng)差分進(jìn)化算法(Adaptive Differential Evolution based on Center of Mass,CADE)用以生成軟件測(cè)試數(shù)據(jù)的方法,不僅通過擴(kuò)充種群中個(gè)體的多樣性,避免算法進(jìn)入早熟;而且通過加快種群收斂速度的方式,降低了自動(dòng)產(chǎn)生測(cè)試數(shù)據(jù)所需時(shí)間.同時(shí),利用質(zhì)心原理尋找最優(yōu)值的策略,實(shí)現(xiàn)整體上平衡全局與局部的搜索能力.最后,通過仿真實(shí)驗(yàn)表明該方法在收斂速度和搜索精度上均有明顯的優(yōu)勢(shì).

2 基本概念

自適應(yīng)差分進(jìn)化算法是貪婪性遺傳進(jìn)化算法,主要包含種群初始化、變異、交叉及選擇階段;其利用多個(gè)個(gè)體的差分信息作為個(gè)體的擾動(dòng)量,使得算法在跳躍距離和搜索方向上具有自適應(yīng)性.在自適應(yīng)差分進(jìn)化算法中,變異操作對(duì)種群的進(jìn)化方向起著決定性作用[13].自適應(yīng)差分進(jìn)化算法種群的初始化及變異操作如下:

1)種群初始化

在自適應(yīng)差分進(jìn)化算法中,設(shè)t表示進(jìn)化代數(shù),NP表示種群規(guī)模,D表示個(gè)體的維數(shù),Xt表示第t代種群.首先,在問題的決策空間內(nèi)隨機(jī)產(chǎn)生第0代種群:X(0)=x1(0),x2(0),…,xNP(0).其中,xit是第t代種群中第i個(gè)個(gè)體.個(gè)體每一維上的取值可按下式產(chǎn)生:xi,j(0)=Lj+randi,j0,1(Uj-Lj),Lj,Uj第j維的取值范圍,其中1≤i≤NP,1≤j≤D;randi,j0,1為介于0和1之間的一個(gè)均勻分布隨機(jī)數(shù),其中j∈1,2,…,D.

2)變異

在每一代t中,都會(huì)根據(jù)當(dāng)前種群產(chǎn)生變異向量Vit.現(xiàn)有的變異操作有很多種,主要包含如下幾種:

DE/rand/1Vi(t)=xr1(t)+Fi(xr2(t)-xr3(t))

(1)

DE/best/1Vi(t)=xbest(t)+Fi(xr1(t)-xr2(t))

(2)

DE/current-to-pbest/1Vi(t)=xi(t)+Fi(xpbest(t)-xi(t))+Fi(xr1(t)-xr2(t))

(3)

其中:Fi為自適應(yīng)DE中每個(gè)個(gè)體的縮放因子,取值范圍為0,1.xr1t,xr2t和xr3t是從集合1,…,NPi中隨機(jī)選擇的相互不同的個(gè)體,xpbestt為當(dāng)前種群中最優(yōu)個(gè)體.

3 CADE

3.1 差分進(jìn)化算法改進(jìn)

由于變異策略的選擇對(duì)差分進(jìn)化算法的效率有著極大的影響.因而對(duì)差分進(jìn)化算法的改進(jìn)一般都是針對(duì)變異策略的改進(jìn)[14].現(xiàn)在改進(jìn)的方法主要有自適應(yīng)的縮放因子Fi的引入、對(duì)于縮放個(gè)體的選擇標(biāo)準(zhǔn)等,相應(yīng)的實(shí)驗(yàn)效果都表現(xiàn)出較快的收斂速度及較高的收斂精度.

A)由第二節(jié)的變異算子公式我們可以看出,種群中個(gè)體間差分向量的大小受縮放因子Fi取值的影響,縮放因子Fi的取值越小,相應(yīng)的擾動(dòng)也就越小.這就意味著,在差分算法的初始階段,由于個(gè)體間彼此差值較大,擾動(dòng)也較大,算法能夠在較大的范圍內(nèi)進(jìn)行搜索;而在算法的后期,群體間個(gè)體都逐漸向最優(yōu)個(gè)體靠攏,進(jìn)而擾動(dòng)值降低,使得算法得以在較小的范圍內(nèi)進(jìn)行搜索.但是傳統(tǒng)的Fi值都是依據(jù)先驗(yàn)知識(shí)人為設(shè)定且固定不變的,在后期向最優(yōu)值收斂時(shí)效果不是很好,因此研究者通過引入不同的自適應(yīng)方法和自適應(yīng)機(jī)制動(dòng)態(tài)地更新控制參數(shù),來提高算法性能.

B)在差分進(jìn)化算法的變異階段,已有很多對(duì)引入物理學(xué)中質(zhì)心這一概念的研究,如Das等人[15]提出的AnDE算法中就使用質(zhì)心這一概念,并在變異階段將求得的新個(gè)體作為變異值代替當(dāng)前全局最優(yōu)值.在實(shí)驗(yàn)中,算法較傳統(tǒng)的差分進(jìn)化算法表現(xiàn)要好.物理學(xué)中質(zhì)心計(jì)算公式如(4)所示:

(4)

其中,rδ為所求的質(zhì)心(center of mass),mi是第i個(gè)粒子的質(zhì)量,ri是第i個(gè)粒子所對(duì)應(yīng)的具體值.

但是就目前研究來看,已有的方法都是假設(shè)種群中各個(gè)粒子質(zhì)量相同,并未考慮到各個(gè)粒子之間的差異性,所以本文對(duì)質(zhì)心的應(yīng)用做出改進(jìn),在已有的JADE算法的基礎(chǔ)上,提出了一種基于質(zhì)心的變異算子.改進(jìn)后的變異算子為:

Vi(t)=xi(t)+Fi(xwBest(t)-xi(t))+Fi(xr1(t)-xr2(t))

(5)

其中,xit,xr1t和xr2t為隨機(jī)選擇的互不相同的個(gè)體.Fi使用JADE中的方式確定.

3.2 xwbest的選擇標(biāo)準(zhǔn)

A)最佳質(zhì)心個(gè)體BCoI(the Best Center of Individual)

BCoI(t)=(BCoI1,BCoI2,…,BCoIn,…,BCoID)

(6)

其中,BCoIt是一個(gè)D維向量,即我們通過質(zhì)心求解方式得到一個(gè)新的個(gè)體.

在第t代種群中,根據(jù)下式求得BCoI第n維元素的值:

(7)

其中,n表示BCoI(t)中第n維,N表示從第t代種群中隨機(jī)抽取100*p%(p為概率)個(gè)個(gè)體,fit表示對(duì)應(yīng)xi個(gè)體的適應(yīng)度值,fsum表示N個(gè)個(gè)體適應(yīng)度值之和.

由公式(7)求得BCoI的值將個(gè)體適應(yīng)度值考慮在內(nèi),也將種群的進(jìn)化方向考慮在內(nèi).不同個(gè)體適應(yīng)度值不同,因此重要性也各不相同.由此賦予每個(gè)個(gè)體不同的權(quán)重值,偏離最優(yōu)值方向的個(gè)體權(quán)重較小,靠近最優(yōu)值的個(gè)體則權(quán)重較大,因此求得的BCoI更趨于最優(yōu)值.

B)全局最佳質(zhì)心個(gè)體GBCoI(the Global Best Center of Individual)

當(dāng)前種群中求得的BCoIt適應(yīng)度值可能優(yōu)于上一代種群的全局最佳質(zhì)心個(gè)體GBCoI(t-1)適應(yīng)度值,也可能低于其適應(yīng)度值.為保證種群能夠向最優(yōu)值方向進(jìn)化,本文根據(jù)公式(8)選出全局最佳質(zhì)心個(gè)體:

(8)

由公式(8)所得的新個(gè)體GBCoIt適應(yīng)度值可能比當(dāng)前種群的全局最優(yōu)值xbest低,也可能優(yōu)于全局最優(yōu)值xbest,所以本文定義以下規(guī)則選出用于變異的最優(yōu)個(gè)體,即xwbest:

(9)

根據(jù)公式(9)計(jì)算得出的xwbest,不僅彌補(bǔ)了JADE中種群多樣性較小,進(jìn)化方向不穩(wěn)定,后期易陷入局部最優(yōu)的缺陷;同時(shí)又利用了質(zhì)心這一物理學(xué)中的概念,能夠快速收斂到最優(yōu)值附近.由此可見,本文方法不僅增加了種群多樣性,而且加快了收斂速度與收斂精度,使得算法整體性能得到提高.

3.3 改進(jìn)的自適應(yīng)差分進(jìn)化算法

在差分進(jìn)化算法中,基于質(zhì)心的xwbest的選擇不僅增加了種群的多樣性,而且提高了收斂速度和精度.自適應(yīng)控制參數(shù)的引入,能夠動(dòng)態(tài)調(diào)整算法中的各個(gè)參數(shù),減少人為設(shè)置參數(shù)的影響.CADE偽代碼如算法1:

1)第2-5行,利用差分進(jìn)化算法初始化種群;設(shè)置均值μF和μCR初始值為0.5,p為選擇精英種群的概率,c為常量;初始化集合SF和SCR為空集,分別用來存放變異及交叉成功的后代個(gè)體所對(duì)應(yīng)的自適應(yīng)的縮放因子和交叉概率.

2)第7行,自適應(yīng)縮放因子Fi和交叉概率CRi分別由柯西分布和標(biāo)準(zhǔn)正態(tài)分布決定.與正態(tài)分布方式不同的是,通過柯西分布產(chǎn)生的縮放因子Fi不僅保證了Fi取值的多樣性,而且有效避免了當(dāng)縮放因子集中于某一具體值時(shí),使用貪心算法進(jìn)行變異(如DE/best,DE/current-to-best)所產(chǎn)生的過早收斂的現(xiàn)象.

3)第8行,按照本文所提的方法選擇出用來變異操作的個(gè)體xwbest,加快種群收斂速度及收斂精度.

4)第11行,變異變量Vit由改進(jìn)后的變異算子確定;由本文方法得到的后代個(gè)體不僅保證了種群的多樣性而且能夠快速向最優(yōu)值方向進(jìn)化,加快了種群的收斂速度.

算法1.

Line# Procedure of CADE

01 Begin

02 SetμCR=0.5;μF=0.5;p=0.05;c=0.1;

03 Initial populationxi(0)|i=1,2,…,NP;

04 For t= 1 to T

05SCR=?;SF=?;

06 For i = 1 to NP

07 GenerateCRi=randni(μCR,0.1),

Fi=randci(μF,0.1);

08 ChooseXwbestby formulate(9);

09 Randomly choosexr1(t)≠xi(t)from

current populationP;

10 Randomly choosexr2(t)≠xi(t) and

xr1(t)≠xr2(t)from current populationP;

11Vi(t)=xi(t)+Fi(xwbest(t)-xi(t))+Fi(xr1(t)-xr2(t));

12 Generatejrand=randint(1,D);

13 For j = 1 to D

14 Ifj=jrandorrand(0,1)

15ui,j(t)=Vi,j(t);

16 Elseui,j(t)=xi,j(t);

17 End For

18 Iff(xi(t))≤f(ui(t))

19xi(t+1)=ui(t);CRi→SCR;Fi→SF;

20 Elsexi(t+1)=xi(t);

21 End for

22μCR=(1-c)·μCR+c·meanA(SCR);

23μF=(1-c)·μF+c·meanL(SF)

24t=t+1;

25 End

5)第18-20行,屬于差分進(jìn)化算法的選擇階段,此階段根據(jù)貪婪算法,在當(dāng)前個(gè)體xi(t)和經(jīng)過交叉后的個(gè)體ui(t)之間選擇出適應(yīng)度值更好的個(gè)體,并保留到下一代種群中;若中間個(gè)體ui(t)優(yōu)于xi(t),將中間個(gè)體保留到下一代;同時(shí),把自適應(yīng)的縮放因子Fi和交差概率CRi分別存入相應(yīng)的集合SF和SCR中.在進(jìn)化過程中,設(shè)置合理的控制參數(shù)更趨向于產(chǎn)生生存能力較強(qiáng)的后代個(gè)體,此時(shí)我們就需要將本次變異與交叉的概率記錄下來,為下一次的種群進(jìn)化作為參考.

6)第22-23行,利用表達(dá)式μCR=1-c·μCR+c·meanASCR和μF=1-c·μF+c·meanLSF分別對(duì)每代的μCR和μF進(jìn)行更新;meanASCR為算術(shù)平均值,meanLSF為L(zhǎng)ehmer平均值,其meanL(SF)=∑F∈SFF2/∑F∈SFF.通過對(duì)使用Lehmer平均值與算術(shù)平均值獲得的自適應(yīng)的μF進(jìn)行對(duì)比,前者對(duì)變異成功的縮放因子賦予更大的權(quán)重,所得的縮放因子更接近最佳縮放因子;而通過算術(shù)平均值獲得的縮放因子往往比最佳縮放因子要小,將會(huì)使得μF過小進(jìn)而導(dǎo)致種群過早收斂.因此Lehmer平均值更有利于保留影響較大的縮放因子,進(jìn)而提高種群的變異概率.

4 CADE算法應(yīng)用于測(cè)試數(shù)據(jù)的生成

4.1 適應(yīng)度函數(shù)的構(gòu)造

多路徑覆蓋測(cè)試數(shù)據(jù)生成問題數(shù)學(xué)模型的建立與路徑的表示方法密切相關(guān),且被測(cè)程序一般有多條路徑.在結(jié)構(gòu)化程序設(shè)計(jì)中,程序通常由順序、選擇和循環(huán)三種結(jié)構(gòu)組成.其中,選擇和循環(huán)結(jié)構(gòu)決定程序不同分支的走向;對(duì)于循環(huán)結(jié)構(gòu),通過引入Z 路徑覆蓋[16]可將其分解成多個(gè)選擇結(jié)構(gòu).現(xiàn)有的路徑表示方式有:采用程序的語句編號(hào)序列表示路徑、采用分支節(jié)點(diǎn)序列表示路徑和利用赫夫曼編碼表示目標(biāo)路徑等方式.本文借鑒GONG等人[17]的基于路徑相關(guān)性的回歸測(cè)試數(shù)據(jù)進(jìn)化生成論文中的相關(guān)路徑表示方法,對(duì)待測(cè)程序進(jìn)行標(biāo)記.

假設(shè),待測(cè)程序?yàn)镻,對(duì)程序中各個(gè)分支節(jié)點(diǎn)進(jìn)行插樁,并設(shè)置穿越相應(yīng)分支節(jié)點(diǎn)并且值為真記為1,若為假記為-1,不經(jīng)過該分支節(jié)點(diǎn)則記為0.因此可以通過1,-1和0的編碼序列表示程序執(zhí)行的路徑.利用一組輸入數(shù)據(jù)運(yùn)行插樁后的測(cè)試程序,得到分支節(jié)點(diǎn)序列為d1,d2,…,dm的執(zhí)行路徑pti,其中,m為路徑pti的長(zhǎng)度;此外,待測(cè)程序P的目標(biāo)路徑為p1,…,pn,n為目標(biāo)路徑條數(shù).

假設(shè)程序P的輸入域?yàn)镈,輸入數(shù)據(jù)t1,…,tn∈D.將執(zhí)行路徑pti的編碼序列與目標(biāo)路徑pi的編碼序列自左向右進(jìn)行比較,找到二者編碼第一次不相同的編碼位置,并記錄之前相同編碼的個(gè)數(shù),記為pti∩pj,取其與目標(biāo)路徑編碼即目標(biāo)路徑總長(zhǎng)度的比值,得到路徑相似度,記為fit:

(10)

因此,可以把求解測(cè)試數(shù)據(jù)生成問題轉(zhuǎn)化為求取f1(t),f2(t),…,fn(t)的最大值問題,則其適應(yīng)度函數(shù)如下:

max(f1(t),f2(t),…fn(t))s.t.t∈D

(11)

4.2 測(cè)試數(shù)據(jù)生成模型

應(yīng)用CADE算法自動(dòng)生成測(cè)試數(shù)據(jù)的模型如圖1所示.測(cè)試環(huán)境的構(gòu)造是測(cè)試數(shù)據(jù)生成的基礎(chǔ),在該階段我們對(duì)源程序進(jìn)行靜態(tài)分析,利用分支函數(shù)插樁得到的帶編碼的測(cè)試程序流程圖生成目標(biāo)路徑,此方法比傳統(tǒng)的數(shù)據(jù)流程圖更加簡(jiǎn)潔;利用CADE算法生成測(cè)試數(shù)據(jù)是整個(gè)模型的核心部分,該階段根據(jù)測(cè)試環(huán)境構(gòu)造所得的目標(biāo)路徑及測(cè)試數(shù)據(jù)范圍,結(jié)合算法所需參數(shù)的設(shè)置,對(duì)種群進(jìn)行初始化,通過運(yùn)行改進(jìn)后的變異算子更新種群,引導(dǎo)種群向最優(yōu)值方向進(jìn)化;并利用測(cè)試數(shù)據(jù)運(yùn)行插樁后的待測(cè)程序,計(jì)算適應(yīng)度值.

圖1 基于CADE算法的測(cè)試數(shù)據(jù)生成模型Fig.1 Model of test data generation based on the CADE

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

為評(píng)價(jià)本文所提出的CADE算法生成測(cè)試數(shù)據(jù)的性能,選擇2個(gè)基準(zhǔn)程序作為被測(cè)程序進(jìn)行實(shí)驗(yàn).針對(duì)被測(cè)程序,本文主要考察各方法生成測(cè)試數(shù)據(jù)所需的時(shí)間,進(jìn)化代數(shù)等,并做出對(duì)比實(shí)驗(yàn),清楚地表現(xiàn)出各方法之間的差異.所有實(shí)驗(yàn)程序均采用Java語言編寫,并在Eclipse下運(yùn)行,微機(jī)環(huán)境為Windows操作系統(tǒng) Intel(R) Core(TM) i3 CPU 2.0GHz和2GB RAM內(nèi)存.所有試驗(yàn)參數(shù)設(shè)置如下:種群迭代次數(shù)1000,GA交叉概率0.6,GA變異概率0.01,GA算法中的適應(yīng)度函數(shù)來源于文獻(xiàn)[18].另外,為降低實(shí)驗(yàn)中隨機(jī)因素的影響,針對(duì)不同程序的每一種情況都獨(dú)立運(yùn)行50次實(shí)驗(yàn).

5.1 三個(gè)數(shù)排序

三個(gè)數(shù)排序程序[18]有三個(gè)輸入變量,有3個(gè)判斷分支,得到目標(biāo)路徑長(zhǎng)度為3;理論路徑為8條,其中,不可行路徑有1條.為測(cè)試CADE算法的性能,本文分別在不同的搜索范圍及種群規(guī)模下進(jìn)行對(duì)比試驗(yàn).相關(guān)實(shí)驗(yàn)結(jié)果如表1-表3所示:

表1 種群規(guī)模為30,算法運(yùn)行結(jié)果比較
Table 1 NP=30,Comparison of experimental results

數(shù)據(jù)范圍平均迭代次數(shù)平均進(jìn)化時(shí)間GAJADECADEGAJADECADE[0，128]2117120．2790．0370．039[0，512]5425190．6090．1190．103[0，1024]10950292．8140．10．102

從表1-表3中能看出:1)在種群規(guī)模相同的情況下,對(duì)于同一輸入數(shù)據(jù)范圍,CADE算法的迭代次數(shù)明顯小于GA和JADE,即CADE算法收斂性能高于JADE和GA;2)在種群規(guī)模相同的情況下,隨著輸入數(shù)據(jù)范圍的增加,GA與JADE算法迭代次數(shù)相差較大,而CADE算法迭代次數(shù)相差不大,說明本文方法的性能要優(yōu)于GA與JADE算法;3)隨著輸入范圍的增加,CADE算法與遺傳算法的時(shí)間差不斷增大,說明CADE在較大的輸入范圍內(nèi)搜索能力強(qiáng);而相對(duì)GA而言,CADE與JADE算法所需平均進(jìn)化時(shí)間相差不大,且CADE平均迭代次數(shù)低于JADE算法.總體而言,CADE算法在平均迭代次數(shù)及進(jìn)化時(shí)間上更優(yōu).

表2 種群規(guī)模為50,算法運(yùn)行結(jié)果比較
Table 2 NP=50,Comparison of experimental results

數(shù)據(jù)范圍平均迭代次數(shù)平均進(jìn)化時(shí)間GAJADECADEGAJADECADE[0，128]1614100．2750．0410．043[0，512]3523190．5470．0490．043[0，1024]6132230．8490．050．05

表3 種群規(guī)模為100,算法運(yùn)行結(jié)果比較
Table 3 NP=100,Comparison of experimental results

數(shù)據(jù)范圍平均迭代次數(shù)平均進(jìn)化時(shí)間GAJADECADEGAJADECADE[0，128]91080．2950．0510．048[0，512]2017140．4360．070．061[0，1024]3228170．8180．0730．064

5.2 三角形判斷

本文所選的三角形判斷程序[17]共有6個(gè)判斷分支,得到目標(biāo)路徑長(zhǎng)度為6;理論路徑為28條,其中,不可行路徑有9條,所以實(shí)際的目標(biāo)路徑為19條,其中等邊三角形的測(cè)試數(shù)據(jù)最難生成.

圖2和圖3為不同輸入范圍下,四種方法找到最優(yōu)解所需的平均迭代次數(shù);其中,[0,64]表示輸入數(shù)據(jù)的取值范圍.圖2表示種群規(guī)模為50,不同輸入數(shù)據(jù)范圍下各個(gè)方法的平均進(jìn)化代數(shù);圖3種群規(guī)模為100,不同輸入數(shù)據(jù)范圍下各個(gè)方法的平均進(jìn)化代數(shù).從圖2和圖3中可以看到CADE算法的總體性能優(yōu)于其他三種算法,而且隨著數(shù)據(jù)輸入范圍的增大,CADE能夠保證在一定進(jìn)化代數(shù)內(nèi)找到所需測(cè)試數(shù)據(jù),性能趨于穩(wěn)定.

圖4和圖5表示四種算法在種群規(guī)模為50的情況下的平均進(jìn)化代數(shù)與分支覆蓋率間的關(guān)系;其中,圖4的數(shù)據(jù)輸入范圍為 [0,1024],圖5的數(shù)據(jù)輸入范圍為[0,64].從圖4和圖5中可知,在迭代初期四種算法的覆蓋率相差不大,隨著平均進(jìn)化代數(shù)的增加,CADE很快達(dá)到100%的覆蓋率;針對(duì)不同的輸入范圍,在滿足分支覆蓋率為100 %時(shí),CADE算法平均進(jìn)化代數(shù)明顯小于GA、DE和JADE算法,表明本文方法的性能優(yōu)于GA、DE和JADE算法.

6 結(jié) 論

本文在研究測(cè)試數(shù)據(jù)生成問題時(shí),首次將自適應(yīng)差分進(jìn)化算法應(yīng)用于解決測(cè)試數(shù)據(jù)生成問題.本文在已有的自適應(yīng)差分進(jìn)化算法JADE基礎(chǔ)上,借助自動(dòng)調(diào)節(jié)縮放因子的方式,豐富種群的多樣性,防止算法陷入局部最優(yōu);同時(shí),采用基于質(zhì)心原理的策略來選擇用于變異的個(gè)體,能夠快速收斂到最優(yōu)值附近,引導(dǎo)算法向最優(yōu)值方向進(jìn)化,使得算法整體性能得到提高.最后,通過仿真試驗(yàn),表明了本文所提出的算法較好地解決了傳統(tǒng)遺傳算法在搜索最優(yōu)解時(shí)易陷入局部最優(yōu)及搜索精度低等缺陷,且能夠快速生成所需數(shù)據(jù).

圖2 不同數(shù)據(jù)范圍,算法平均進(jìn)化代數(shù)Fig.2 Different data range,the algorithm′s average number of iterations

圖3 不同數(shù)據(jù)范圍,算法平均進(jìn)化代數(shù)Fig.3 Different data range,the algorithm′s average number of iterations

圖4 進(jìn)化代數(shù)與分支覆蓋率的關(guān)系Fig.4 Relationship between the number of iterations and the rate of branch coverage

圖5 進(jìn)化代數(shù)和分支覆蓋率的關(guān)系Fig.5 Relationship between the number of iterations and the rate of branch coverage

[1] Qiu Xiao-kang,Lin Xuan-dong.A path-orientedtoolsupporting fortesting [J].Acta Electronica Sinica,2004,32(12A):231-234.

[2] Deb K,Pratap A,Agarwal S,et al.A fast and elitist multiobjective genetic algorithm:NSGA-II [J].IEEE Transactions on Evolutionary Computation,2002,6(2):182-197.

[3] Koleejan C,Xue B,Zhang M.Code coverage optimization in genetic algorithms and particle swarm optimization for automatic software test data generation[C].2015 IEEE Congress on Evolutionary Computation (CEC),IEEE,2015:1204-1211.

[4] Zhou Y,Li X,Gao L.A differential evolution algorithm with intersect mutation operator [J].Applied Soft Computing,2013,13(1):390-401.

[5] Hui S,Suganthan P N.Ensemble and arithmetic recombination-based speciation differential evolution for multimodal optimization [J].IEEE Transactions on Cybernetics,2016,46(1):64-74.

[6] Storn R,Price K.Differential evolution-a simple and efficient heuristic for global optimization over continuous spaces [J].Journal of Global Optimization,1997,11(4):341-359.

[7] Becerra R L,Coello C A C.Cultured differential evolution for constrained optimization [J].Computer Methods in Applied Mechanics and Engineering,2006,195(33):4303-4322.

[8] Gong W,Cai Z.An improved multi-objective differential evolution based on Pareto-adaptive-dominance and orthogonal design [J].European Journal of Operational Research,2009,198(2):576-601.

[9] Liao T W.Two hybrid differential evolution algorithms for engineering design optimization [J].Applied Soft Computing,2010,10(4):1188-1199.

[10] Zhang J,Sanderson A C.JADE:adaptive differential evolution with optional external archive [J].IEEE Transactions on Evolutionary Computation,2009,13(5):945-958.

[11] Gong W,Cai Z,Ling C X,et al.Enhanced differential evolution with adaptive strategies for numerical optimization[J].IEEE Transactions on Systems,Man,and Cybernetics,Part B (Cybernetics),2011,41(2):397-413.

[12] Yang Z,Tang K,Yao X.Self-adaptive differential evolution with neighborhood search[C].2008 IEEE Congress on Evolutionary Computation (IEEE World Congress on Computational Intelligence),IEEE,2008:1110-1116.

[13] Yi W,Zhou Y,Gao L,et al.An improved adaptive differential evolution algorithm for continuous optimization [J].Expert Systems with Applications,2016,44:1-12.

[14] Epitropakis M G,Tasoulis D K,Pavlidis N G,et al.Enhancing differential evolution utilizing proximity-based mutation operators[J].IEEE Transactions on Evolutionary Computation,2011,15(1):99-119.

[15] Das S,Konar A,Chakraborty U K.Annealed differential evolution[C].2007 IEEE Congress on Evolutionary Computation.IEEE,2007:1926-1933.

[16] Xia Hui,Song Xin,Wang Li.Research of test case auto generating based on Z-path coverage [J].Modern Electronics Technique,2006,29(6):92-94.

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

[18] 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.

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

[1] 邱曉康,李宣東.一個(gè)面向路徑的軟件測(cè)試輔助工具[J].電子學(xué)報(bào),2004,32(12A):231-234.

[16] 夏 輝,宋 昕,王 理.基于 Z 路徑覆蓋的測(cè)試用例自動(dòng)生成技術(shù)研究[J].現(xiàn)代電子技術(shù),2006,29(6):92-94.

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

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