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

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

0 引 言

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

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

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

1 多目標(biāo)人工蜂群優(yōu)化算法

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

1.1 精英解集及全局最優(yōu)解更新策略

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

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

(1)

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

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

算法1：

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

輸出： 外部精英集M

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

外部精英集M不更新；

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

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

Else

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

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

Else

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

不更新外部精英集M；

Else

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

End if

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

(2)

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

(3)

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

1.2 最優(yōu)個體引導(dǎo)差分變異的局部搜索

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

(4)

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

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

(5)

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

(6)

1.3 基于信息熵的蜜源選擇

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

(7)

式中：fiti為第i個蜜源的適應(yīng)度值.

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

(8)

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

a=1-H/Hmax,

(9)

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

(10)

2 基于MOABCO的多目標(biāo)測試用例優(yōu)先級排序

2.1 優(yōu)化目標(biāo)

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

(11)

(12)

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

2.2 蜜源個體編碼

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

2.3 MOABCO算法基本流程

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

輸出： 滿足Pareto最優(yōu)解的個體.

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

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

Do

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

If 開采次數(shù)

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

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

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

利用式(8)～式(10)選擇優(yōu)質(zhì)個體繼續(xù)進(jìn)行局部搜索；

Else

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

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

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

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

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

3 實驗結(jié)果分析

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

表 1 測試函數(shù)信息表

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

表 2 MOABC算法與MOABCO算法的對比結(jié)果

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

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

圖 1 不同多目標(biāo)蜂群算法的Pareto最優(yōu)解對比Fig.1 Comparison of Pareto optimal solution of different multi-object bee colony algorithm

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

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

表 3 基準(zhǔn)程序信息

實驗中的每組實驗數(shù)據(jù)均獨立運行50次，取平均值記錄，結(jié)果如圖 2 所示.從圖 2 中可以看出，隨著程序規(guī)模的增大，NSGA-II和MOABCO算法所計算的APFD值均呈現(xiàn)下降趨勢，但是MOABCO算法所計算的APFD值均優(yōu)于NSGA-II算法，證明了由MOABCO算法進(jìn)行的測試用例優(yōu)先級排序的缺陷檢測能力要優(yōu)于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解集中的個體分布更加均勻，分布范圍更加廣泛，且大多數(shù)個體均優(yōu)于NSGA-II算法.證明了MOABCO算法可以加快種群的搜索速度，保證種群的多樣性.

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

4 結(jié)束語

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