基于MOABCO的多目標測試用例優先級排序

張 娜，張 唯，吳 彪，包曉安

(1.浙江理工大學 信息學院，浙江 杭州 310018； 2.山口大學 東亞研究科，山口 753-8514)

0 引 言

隨著工業程序的日益復雜，將代碼覆蓋率、 測試需求覆蓋、 平均錯誤檢測率等因素之一作為測試用例排序準則的單目標測試用例優先級技術(Test Case Prioritization，TCP)，已經難以滿足回歸測試的測試需求，研究者們亟需將研究重心轉移至多目標測試用例優先級排序(Multi-Objective Test Case Prioritization，MOTCP)問題上[1].根據排序方法的不同，已有的關于MOTCP問題的研究可以分為加權法[2-6]和Pareto最優法兩類[7-10]，其中加權法占大多數，Pareto最優法的相對較少.同時，Pareto最優法的研究算法主要集中在以NSGA-II算法為代表的進化算法，關于其他智能搜索算法的研究還相對較少.

MOTCP問題從本質上來說是求解最優測試用例執行次序的組合優化問題[11]，可以描述為： 對于給定的測試用例集T,PT為T的全排列集合，目標函數向量F=[f1(p),f2(p),…,fi(p),…,fM(p)],fi表示第i個優化目標的目標函數，fi∶PT→R，p∈PT，1≤i≤M.要求找到一個PT′屬于PT，使?p′∈PT′∩F達到Pareto最優.人工蜂群算法(Artificial Bee Colony Algorithm, ABC)相對于其他智能搜索算法具有結構簡單、 控制參數少、 易于實現等特點[12].基于ABC算法的多目標人工蜂群優化(Multi-Objective Artificial Bee Colony，MOABC)算法，在解決多目標組合優化問題上表現出良好的特性[13,14].因此，可將MOABC算法引入到解決MOTCP問題中.

本文針對已有MOABC算法存在易陷入局部最優等問題，對外部精英解集及全局最優解的更新、 局部搜索和蜜源選擇方式上做出了改進，提出了一種MOABCO算法.將測試用例的平均語句覆蓋率和有效執行時間作為優化目標，并用MOABCO算法求Pareto最優解，以解決MOTCP問題.

1 多目標人工蜂群優化算法

基本的MOABC算法除了增加外部候選解集，在雇傭蜂、 觀察蜂和偵查蜂三個階段的操作均與標準ABC算法相同，本文在基本MOABC的基礎上進行改進.

1.1 精英解集及全局最優解更新策略

在基本的MOABC算法中，當某個蜜源經過limit次的開采后沒有開采價值時與之對應的雇傭蜂轉化為偵查蜂，并按照式(1)隨機產生一個新蜜源代替.

xij=xmin,j+rand(0,1)×(xmax,j-xmin,j),

(1)

式中：xij為新蜜源的第j維分量，j∈{1,2,…,D}，rand(0,1)為范圍在(0,1)內的一個隨機數，xmax,j和xmin,j分別為蜜源第j維分量的上下界.

為了充分利用所搜過程中所產生的非劣解(蜜源)，提高算法的收斂性和多樣新，本文在外部建立精英解集，精英解集的更新策略，如下算法1所示.

算法1：

輸入： 外部精英集M，精英集的最大容量m，新蜜源個體S

輸出： 外部精英集M

If (個體S至少被M中的一個個體支配)

外部精英集M不更新；

Else if (個體S支配M中的某些個體)

將外部精英集M中被S支配的個體刪除，并將S加入到M中；

Else

if (外部精英集M中個體的個數

將S加入到外部精英集M中；

Else

If (個體S在外部精英解集的最擁擠區域)

不更新外部精英集M；

Else

用個體S替換外部精英解集中最擁擠區域的個體，更新外部精英集M；

End if

在外部精英解集中，每一個非支配解相對其他的解而言都是最優的，而在算法運行過程中，只需要選取一個作為全局最優解.擁擠距離d(i)用于描述精英解集中某個解的密度值，本文首先計算精英解集中每個解的d(i)值并降序排列，取d(i)值大的前50%的精英解(即，處于Pareto前端的分散個體)作為全局最優解的候選者.擁擠距離的計算公式如式(2)所示，

(2)

為了提高精英解集中個體的多樣性，同時使其均勻分布在目標空間上，本文采用如式(3)的隨機選法.

(3)

式中：Num為非劣解的個數，xbest為全局最優解，A為精英解集中擁擠距離值較大的前50%的個體的集合，rand_int(0,i)為產生(0,i)內隨機正整數的函數.

1.2 最優個體引導差分變異的局部搜索

已有的研究表明，充分利用精英解的特征信息能夠有效地促進種群進化[15].而基本的MOABC算法在局部搜索過程中采用隨機選擇的方式挑選一個可行解作為局部搜索的引導信息，按照式(4)進行搜索并根據貪婪選擇機制對蜜源進行更新，忽略了精英個體的引導作用.

(4)

式中：i,k∈{i=1,2,…,N}且i≠k，j∈{i=1,2,…,D},R為[-1,1]中的隨機數.

同時，差分變異策略是差分進化算法中的變異方法，通過種群個體間的差分向量對個體進行擾動，實現個體的變異，能夠有效利用群體分布特性，提高算法的搜索能力.本文將差分進化算法中的變異策略引入到人工蜂群算法中，同時采用精英個體引導策略對雇傭蜂的搜索模式進行改進，如式(5)所示.

(5)

式中：xbest為全局最優解，來自于外部精英解集；xr1,j和xr2,j為蜜源中隨機選擇的兩個個體；F為縮放因子，F的值越小，算法跳出局部最優解的能力越強，但過小的縮放因子會導致收斂速度緩慢，影響算法的效率，F的值越大，有利于提高算法的開發能力，但是過大的F值會使算法陷入局部束縛.本文將當前蜜源與全局最優蜜源之間的歐氏距離作為F值，計算方法如式(6)所示，使算法在精英解的引導下能夠根據個體與精英個體之間的相似度自適應地調整搜索范圍的大小，從而提高算法的搜索效率.

(6)

1.3 基于信息熵的蜜源選擇

觀察蜂通過雇傭蜂傳來的信息，按照式(7)計算每個蜜源被選擇的概率，用輪盤賭的方式選擇具有一定的隨機性.

(7)

式中：fiti為第i個蜜源的適應度值.

信息熵能度量隨機事件發生的不確定性，本文將信息熵引入到蜂群算法中，以信息熵值控制蜜源被選擇的概率的大小.多目標的測試用例優先級排序問題屬于離散的多目標優化問題，因此蜜源被選擇的概率的信息熵計算如式(8)所示，

(8)

借鑒信息冗余度衡量信息源的相關性程度的思想，本文定義蜜源相關性程度a，計算公式如式(9)所示，

a=1-H/Hmax,

(9)

式中：Hmax為最大熵值，即當pi=1/Dim時，Dim為所處理數據的維度.a的值越大表示蜜源與最優蜜源之間的相關性越小； 反之，蜜源與最優蜜源之間的相關性越大.為了提高算法跳出局部最優的能力，本文按照式(10)進行選擇，從而提高與當前最優解相似度較小的解被選擇的概率，以保證蜜源個體的多樣性.

(10)

2 基于MOABCO的多目標測試用例優先級排序

2.1 優化目標

回歸測試旨在較短的時間內發現更多的軟件錯誤，可以用軟件缺陷檢測率(Average Percentage of Fault Detect，APFD)作為度量準則.而在實際測試過程中，測試用例未執行之前，APFD的值未知，而一般情況下，測試用例對軟件的語句、 分支、 塊等的覆蓋率越大，該用例能夠發現軟件中存在缺陷的概率就越大.因此，通常會用代碼覆蓋率代替APFD值作為優化目標，而將APFD值作為衡量優先級排序效果的準則.為了能讓代碼覆蓋率較高且執行時間較短的測試用例優先執行，本文將平均語句覆蓋率(Average Percentage of Statement Coverage, APSC)和有效執行時間(Effective Execution Time, EET)作為優化目標，計算方法如式(11)和(12)所示.

(11)

(12)

式中：N為測試用例的個數，M為程序語句的個數，TSi為覆蓋程序語句i的第一個測試用例在序列中的位置，ETi為測試用例i的執行時間.

2.2 蜜源個體編碼

本文采用實數編碼的方式，假設測試用例集TS中有N個測試用例，那么任意一個執行順序可以表示為X={xr1,xr2,…,xrq,…,xrN}，其中rq表示測試用例集TS中的第q個測試用例，xrq表示測試用例rq在測試用例集TS中的序號，且1≤xrq≤N.因此，測試用例集TS中所有測試用例的全排列組合構成了MOTCP問題的解空間.

2.3 MOABCO算法基本流程

輸入： 搜索維度D，蜜源個數FN，最大開采次數Limit，算法最大迭代次數k，算法運行次數t.

輸出： 滿足Pareto最優解的個體.

根據D和FN，隨機初始化得到一組包含FN個個體的可行解集M′，M′={X1,X2,…,Xi,…,XFN}.

根據式(11)和(12)評估已有的可行解，將評估為非劣解的可行解加入到外部精英集M；

Do

在外部精英解集中按照式(3)選取全局最優解；

If 開采次數

利用式(5)進行局部搜索，獲得新蜜源；

根據式(11)和式(12)評價新蜜源；

采用算法1判斷是否更新精英解集M；

利用式(8)～式(10)選擇優質個體繼續進行局部搜索；

Else

放棄該蜜源，并利用式(1)隨機生成一個新蜜源；

根據式(11)和式(12)對新蜜源進行評價；

采用算法1判斷是否更新精英解集M；

While(運行次數t<最大迭代次數k)

在外部精英解集M中挑選一個Pareto最優解，作為測試用例優先級排序的結果.

3 實驗結果分析

為了驗證本文所提出MOABCO算法在收斂性和易陷入局部最優解這兩個問題上改善的有效性，本文參考文獻[12]選取了ZDT1、 ZDT2、 ZDT3函數進行測試，并在 MATLAB R2016b上編碼實現，測試函數的信息如表 1 所示.

表 1 測試函數信息表

實驗中，蜜源個數均為50，開采次數limit為100，最大迭代次數為1 000，維度D為30，精英解集大小為30，每次均獨立運行10次，取平均值記錄于表 2，括號內的數據是該指標對應的10次實驗的方差值.本文選擇逼近指標GD和分布指標SP作為比較兩個算法的評價標準，GD和SP的值越小越好.

表 2 MOABC算法與MOABCO算法的對比結果

從表 2 的整體結果看，無論是GD還是SP，本文提出的MOABCO算法均優于基本的MOABC算法，說明本文的算法具有良好的求解性能.

為了進一步分析本文改進策略對算法的影響，針對ZDT2優化問題，將本文所提的MOABCO算法記為算法1，使用本文所提的選擇策略的MOABC算法記為算法2，使用本文所提局部搜索策略的MOABC算法記為算法3，設定評價次數為1 000的條件下進行實驗，3種算法的Pareto最優解的對比結果如圖 1 所示.

圖 1 不同多目標蜂群算法的Pareto最優解對比Fig.1 Comparison of Pareto optimal solution of different multi-object bee colony algorithm

從圖 1 中可以看出，算法3產生的Pareto最優解在接近理論最優的程度上要優于算法2，證明了本文所提的局部搜索方法能夠有效地對解空間進行開采.但正是因為全局最優個體引導的開采而導致解的多樣性降低，在圖 1 上表現出了聚集現象，而算法2的解則表現出分布均勻，證明了本文的選擇策略能夠有效保證算法運行過程中解的多樣性.而多樣性的增加導致Pareto最優解無法有效接近理論最優值.算法1在逼近理論最優和保持解的多樣性上均表現良好，證明了本文所提的改進策略能夠有效地避免算法早熟收斂和陷入局部最優解.

為了驗證本文所提算法在解決MOTCP問題的有效性，分別將優化目標函數NSGA-II算法和MOABCO算法相結合，在Visual Studio 2015上采用C語言編程實現測試用例優先級排序，將本文提出的MOABCO算法與NSGA-II算法進行比較.本文選取了5個常用評測程序作為實驗基準，基本信息如表 3 所示，這些基準程序被廣泛應用于測試用例對軟件缺陷檢測能力的研究.

表 3 基準程序信息

實驗中的每組實驗數據均獨立運行50次，取平均值記錄，結果如圖 2 所示.從圖 2 中可以看出，隨著程序規模的增大，NSGA-II和MOABCO算法所計算的APFD值均呈現下降趨勢，但是MOABCO算法所計算的APFD值均優于NSGA-II算法，證明了由MOABCO算法進行的測試用例優先級排序的缺陷檢測能力要優于NSGA-II算法.

圖 2 MOABCO算法與NSGA-II算法針對不同程序計算的APFD值Fig.2 The APFD calculate value of different programs comparison among two algorithm

圖 3 為PG5使用NSGA-II算法迭代300代和MOABCO算法迭代250代后算法運行30次時的Pareto解集分布.從圖3中可以看出，MOABCO的Pareto解集中的個體分布更加均勻，分布范圍更加廣泛，且大多數個體均優于NSGA-II算法.證明了MOABCO算法可以加快種群的搜索速度，保證種群的多樣性.

圖 3 MOABCO算法和NSGA-II算法的Pareto解集的分布Fig.3 Distribution of Pareto solution sets of MOABCO algorithm and NSGA-II algorithm

4 結束語

文本針對基本MOABC算法存在的問題，改進了局部搜索策略、 蜜源的選擇策略和外部精英解集及最優解更新策略，提高了算法的開采能力且增加了解的多樣性，從而加快了算法的收斂速度，提升了算法的全局搜索能力.將MOABCO算法用于求解MOTCP問題中，相對于NSGA-II算法具有明顯的優勢.在今后的研究中，可以考慮增加優化目標的個數至3個及以上，以提升測試用例優先級排序的效率，降低回歸測試用例的成本.