應用混沌果蠅算法的路徑覆蓋測試用例優化技術研究

李龍澍,郭紫夢

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

1 引 言

伴隨軟件應用領域和軟件規模不停的擴展和增大,軟件的質量顯得愈發重要.軟件測試是保障軟件質量的關鍵技術措施,通常從始至終貫穿著全部的軟件研發流程,軟件測試的重點就在于測試用例的編寫,測試用例的自動化便成為軟件測試的重中之重[1].路徑覆蓋測試是指在測試過程中,選擇有效且充足的測試數據,除去不可能路徑,使得測試程序中的其余所有路徑都存在至少一條對應的測試數據.在現實測試中,眾多軟件測試問題都可以轉化為路徑覆蓋測試的數據生成問題.

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

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

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

2 混沌果蠅優化算法

2.1 標準果蠅優化算法(FOA)

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

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

2)給予果蠅個體運動的隨機方向與間隔,random value為運動的間隔.

Xi=X_axis+RandomValueYi=Y_axis+RandomValue

(1)

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

(2)

4)得到該種群中Smell值最大的果蠅個體,記為當前最優果蠅個體.

[bestSmellbestIndex]=max(Smell)

(3)

5)判斷當前最優個體濃度值bestSmell是否高于上一次迭代的最優味道濃度值,若是,執行(6);若否,執行(7).

6)保存下來當前最優個體的味道濃度值與其二維坐標X、Y,其他果蠅個體則操縱方向飛往最優位置.

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

(4)

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

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

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

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

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

(5)

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

基于混沌策略的果蠅優化算法的基礎思想為:每次迭代過程中,對整個果蠅群體搜尋到的最優個體A進行混沌擾動操作,將混沌序列中的最優個體A*保留,以A和A*各自為中心的隨機搜索方向和距離范圍內產生一半種群個體,并搜索到當前迭代過程中的最優值,繼續進行混沌操作.融入混沌策略的進化算法可在迭代中不斷產生局部最優點運動距離外的混沌個體,協助相應算法跳出局部極值點,以此更快的搜尋到全局最優值.

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

3.1 路徑覆蓋測試問題描述

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

3.2 C-FOA算法的路徑覆蓋測試

在路徑覆蓋測試中,利用果蠅優化算法的收斂性迭代出最優個體來達到測試目標.將每個果蠅個體作為一條測試數據,設F0=(t1,t2,…,tm)表示路徑覆蓋測試中的目標路徑標識序列,于是該問題就轉化為尋找最優向量(x1,x2,…,xm)覆蓋目標路徑標識序列,具體如下:

1)編碼

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

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

2)果蠅個體

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

3)混沌果蠅個體

4)味道濃度函數

味道濃度函數代表著果蠅個體的效用,用Fitness表示,以此用來區分不同果蠅個體間的優劣情況,進而挑選出最優的那一個個體.本文的味道濃度函數依據路徑覆蓋測試適應度函數的設計,分為層接近度(approach_level)和分支距離(branch_distance)兩部分相結合.

假設果蠅個體Gi穿越的路徑標識序列為F(Gi),目標測試路徑標識序列為F0.Gi的層接近度為approach_level(Gi),計算方法為:統計F(Gi)與F0相同標識變量的個數,用其除以目標測試路徑標識序列F0的標識變量總數來計算,故層接近度值與個體的優異程度成正比;分支距離為branch_distance(Gi),計算方法與Tracey方法相同[21].同時為防止分支距離過大,從而使層接近度失去引導作用,將其采取1.001-branch_distance(Gi)做出標準化操作,故分支距離值與個體的優異程度成正比.

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

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

(6)

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

3.3 算法步驟

假設需要覆蓋的目標路徑為F0,C-FOA算法具體流程如下:

輸入:群體數量為 N,最大迭代次數為 Maxgen,混沌次數為K,并隨機果蠅群體m維開始位置X1_axis,X2_axis,…,Xm_axis

輸出:目標測試數據x1,x2,…,xm

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

Step2.運行插樁后的程序;

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

Step4.判斷當前最優個體的濃度值是否高于上一次迭代的值,若是,保存最優個體GBest(x1,x2,…,xm),若否,繼續下一步;

Step5.判斷是否覆蓋目標路徑F0,或達到最大迭代次數,若是,跳轉Step 8,若否,繼續下一步;

Step7.給予個體GBest*和GBest的隨機方向與間隔,且分別對GBest*和GBest給予一半種群數目的個體,跳轉Step 2;

Step8.終止種群的進化,保存并輸出相應的測試結果.

C-FOA算法過程對應的流程圖如圖2所示.

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

為了防止混沌策略太過干擾最優值的尋找,同時也為了保持FOA計算量小的優勢,根據情況對混沌次數做出了恰當的調整,即每兩個周期添加一次混沌干擾.即使算法在未添加混沌的周期內出現“早熟”征兆,隨后的混沌干擾便會迅速的使算法脫離局部極值.

4 仿真實驗及結果分析

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

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

共進行了兩組實驗,第一組為在不同迭代次數下的覆蓋率;第二組為找到覆蓋目標路徑測試數據的評價次數與運行時間.實驗條件:Windows 7 操作系統,MyEclipse 10仿真環境,計算機主頻 2.80GHz,內存4GB.

4.1 基準程序

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

程序分支結構三個數排序3個選擇并列關系三角形分類2個多分支選擇結構，4個選擇并列關系冒泡程序 2層循環嵌套，內層嵌套含有1個選擇結構輸入分量個數目標路徑數代碼行數插樁節點數37183319276434246

4.2 對比實驗

實驗1.不同迭代次數下的覆蓋率

程序輸入變量取值范圍為 0-1023 之間的整數,種群大小為 50.對三個基準程序,分別在限定迭代次數為1、50、100、150、200的條件下,對于所有目標路徑進行覆蓋測試,得到相應的覆蓋率,如圖3-圖5.

圖3 三個數排序覆蓋率Fig.3 Coverage of ranking of three numbers

由圖3-圖5可得:

1)從遺傳算法、蟻群算法和果蠅優化算法的對比可以看出,在相同環境下,FOA的覆蓋率在多數情況下是高于GA和ACO的,說明FOA方法應用在路徑覆蓋測試領域內是可行的.

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

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

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

實驗2.覆蓋目標路徑下的評價次數與運行時間

程序輸入變量取值范圍為 0-127 之間的整數,種群大小為 50.對三個基準程序進行所有目標路徑的覆蓋測試,得到相應的評價次數與運行時間.若評價次數超過1000,即認為該路徑的測試數據尋找失敗.具體結果如表2.

表2 覆蓋全部目標路徑下的評價次數與運行時間
Table 2 Evaluation times and runtime with all the target paths covered

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

由表2可以得到:

1)從評價次數來看,在5種方法中,本文方法以最少的評價次數獲取了所有的測試數據.如在三角形分類程序中,本文方法的評價次數為54.26,遺傳算法的評價次數為495.65,且未能全部覆蓋,蟻群算法的評價次數為195.82,果蠅算法的評價次數為187.84,文獻[11]中遺傳算法的評價次數為76.10.以上數據說明本文方法的性能優于同類方法;

2)從運行時間來看,本文方法的運行時間明顯少于另外4種方法.特別是,隨著程序的復雜度增加,本文方法的優勢更加明顯,這是因為,本文方法具有計算量小,復雜度低等優勢,再次證明本文方法生成測試用例的效能優于同類方法;

3)從覆蓋成功率來看,隨著目標路徑的增多以及路徑復雜程度的增加,本文方法的評價次數和運行時間也有所增加.但是本文方法仍能有效生成測試數據.而且生成測試數據的成功率均可達到 100%,說明本文方法具有有效性.

通過以上的兩組實驗,本文方法充分考驗了 FOA 算法應用在路徑覆蓋測試用例進化生成領域內的可行性,并且考證了本文方法生成路徑覆蓋測試數據的有效性,提升了獲取測試用例的效率.

5 結 論

鑒于果蠅優化算法和遺傳算法等智能算法同屬于一類算法,同時果蠅優化算法具有計算量小,復雜度低,尋優精度高等優點,本文把果蠅優化算法應用到路徑覆蓋測試領域內,并針對果蠅優化算法穩定性差的缺點,對迭代過程中的最優個體加入混沌策略,在保留優秀個體的同時,增加種群多樣性,優化全局搜索能力,加快算法收斂速度,有效提高了生成測試數據的效率.實驗結果表明,本文方法與同類方法相比生成測試數據的效率更高.

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

附中文參考文獻：

[1] 董躍華,戴玉倩.一種改進PSO的軟件測試數據自動生成算法[J].小型微型計算機系統,2015,36(9):2015-2020.

[3] 夏春艷,張 巖,宋 麗.基于節點概率的路徑覆蓋測試數據進化生成[J].軟件學報,2016,27(4):802-813.

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

[5] 鞏敦衛,張 巖.一種新的多路徑覆蓋測試數據進化生成方法[J].電子學報,2010,38(6):1299-1304.

[6] 張 巖,鞏敦衛.基于搜索空間自動縮減的路徑覆蓋測試數據進化生成[J].電子學報,2012,40(5):1011-1016.

[7] 張 巖,鞏敦衛.基于稀有數據撲捉的路徑覆蓋測試數據進化生成方法[J].計算機學報,2013,36(12):2429-2440.

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

[13] 張衛祥,魏 波,杜會森.一種基于遺傳算法的測試用例優先排序方法[J].小型微型計算機系統,2015,36(9):1998-2002.

[14] 潘文超.果蠅最佳化演算法—最新演化式計算技術[M].臺灣:滄海書局,2011.

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

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

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

[21] 張 巖.路徑覆蓋測試數據進化生成理論與方法[D].北京：中國礦業大學,2012.