應用自適應差分進化算法優(yōu)化測試數據研究

李龍澍,翁晴晴

(安徽大學 計算機科學與技術學院,合肥 230601)

1 引 言

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

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

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

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

2 基本概念

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

1)種群初始化

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

2)變異

在每一代t中,都會根據當前種群產生變異向量Vit.現有的變異操作有很多種,主要包含如下幾種:

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為自適應DE中每個個體的縮放因子,取值范圍為0,1.xr1t,xr2t和xr3t是從集合1,…,NPi中隨機選擇的相互不同的個體,xpbestt為當前種群中最優(yōu)個體.

3 CADE

3.1 差分進化算法改進

由于變異策略的選擇對差分進化算法的效率有著極大的影響.因而對差分進化算法的改進一般都是針對變異策略的改進[14].現在改進的方法主要有自適應的縮放因子Fi的引入、對于縮放個體的選擇標準等,相應的實驗效果都表現出較快的收斂速度及較高的收斂精度.

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

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

(4)

其中,rδ為所求的質心(center of mass),mi是第i個粒子的質量,ri是第i個粒子所對應的具體值.

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

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

(5)

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

3.2 xwbest的選擇標準

A)最佳質心個體BCoI(the Best Center of Individual)

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

(6)

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

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

(7)

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

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

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

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

(8)

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

(9)

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

3.3 改進的自適應差分進化算法

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

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

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

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

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

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

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

4 CADE算法應用于測試數據的生成

4.1 適應度函數的構造

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

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

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

(10)

因此,可以把求解測試數據生成問題轉化為求取f1(t),f2(t),…,fn(t)的最大值問題,則其適應度函數如下:

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

(11)

4.2 測試數據生成模型

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

圖1 基于CADE算法的測試數據生成模型Fig.1 Model of test data generation based on the CADE

5 實驗分析

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

5.1 三個數排序

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

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

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

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

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

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

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

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

5.2 三角形判斷

本文所選的三角形判斷程序[17]共有6個判斷分支,得到目標路徑長度為6;理論路徑為28條,其中,不可行路徑有9條,所以實際的目標路徑為19條,其中等邊三角形的測試數據最難生成.

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

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

6 結 論

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

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

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

圖4 進化代數與分支覆蓋率的關系Fig.4 Relationship between the number of iterations and the rate of branch coverage

圖5 進化代數和分支覆蓋率的關系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.

附中文參考文獻：

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

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

[17] 吳 川,鞏敦衛(wèi).基于路徑相關性的回歸測試數據進化生成[J].計算機學報,2015,38(11):2247-2261.

[18] 丁 蕊,董紅斌,張 巖,等.基于關鍵點路徑的快速測試用例自動生成方法[J].軟件學報,2016,27(4):814-827.