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

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

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

0 引 言

隨著工業(yè)程序的日益復(fù)雜，將代碼覆蓋率、 測(cè)試需求覆蓋、 平均錯(cuò)誤檢測(cè)率等因素之一作為測(cè)試用例排序準(zhǔn)則的單目標(biāo)測(cè)試用例優(yōu)先級(jí)技術(shù)(Test Case Prioritization，TCP)，已經(jīng)難以滿足回歸測(cè)試的測(cè)試需求，研究者們亟需將研究重心轉(zhuǎn)移至多目標(biāo)測(cè)試用例優(yōu)先級(jí)排序(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)法的相對(duì)較少.同時(shí)，Pareto最優(yōu)法的研究算法主要集中在以NSGA-II算法為代表的進(jìn)化算法，關(guān)于其他智能搜索算法的研究還相對(duì)較少.

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

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

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

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

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

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

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

(1)

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

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

算法1：

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

輸出： 外部精英集M

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

外部精英集M不更新；

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

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

Else

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

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

Else

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

不更新外部精英集M；

Else

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

End if

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

(2)

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

(3)

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

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

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

(4)

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

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

(5)

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

(6)

1.3 基于信息熵的蜜源選擇

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

(7)

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

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

(8)

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

a=1-H/Hmax,

(9)

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

(10)

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

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

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

(11)

(12)

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

2.2 蜜源個(gè)體編碼

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

2.3 MOABCO算法基本流程

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

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

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

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

Do

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

If 開采次數(shù)

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

根據(jù)式(11)和式(12)評(píng)價(jià)新蜜源；

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

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

Else

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

根據(jù)式(11)和式(12)對(duì)新蜜源進(jìn)行評(píng)價(jià)；

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

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

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

3 實(shí)驗(yàn)結(jié)果分析

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

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

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

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

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

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

圖 1 不同多目標(biāo)蜂群算法的Pareto最優(yōu)解對(duì)比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，證明了本文所提的局部搜索方法能夠有效地對(duì)解空間進(jìn)行開采.但正是因?yàn)槿肿顑?yōu)個(gè)體引導(dǎo)的開采而導(dǎo)致解的多樣性降低，在圖 1 上表現(xiàn)出了聚集現(xiàn)象，而算法2的解則表現(xiàn)出分布均勻，證明了本文的選擇策略能夠有效保證算法運(yùn)行過程中解的多樣性.而多樣性的增加導(dǎo)致Pareto最優(yōu)解無法有效接近理論最優(yōu)值.算法1在逼近理論最優(yōu)和保持解的多樣性上均表現(xiàn)良好，證明了本文所提的改進(jìn)策略能夠有效地避免算法早熟收斂和陷入局部最優(yōu)解.

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

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

實(shí)驗(yàn)中的每組實(shí)驗(yàn)數(shù)據(jù)均獨(dú)立運(yùn)行50次，取平均值記錄，結(jié)果如圖 2 所示.從圖 2 中可以看出，隨著程序規(guī)模的增大，NSGA-II和MOABCO算法所計(jì)算的APFD值均呈現(xiàn)下降趨勢(shì)，但是MOABCO算法所計(jì)算的APFD值均優(yōu)于NSGA-II算法，證明了由MOABCO算法進(jìn)行的測(cè)試用例優(yōu)先級(jí)排序的缺陷檢測(cè)能力要優(yōu)于NSGA-II算法.

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

圖 3 為PG5使用NSGA-II算法迭代300代和MOABCO算法迭代250代后算法運(yùn)行30次時(shí)的Pareto解集分布.從圖3中可以看出，MOABCO的Pareto解集中的個(gè)體分布更加均勻，分布范圍更加廣泛，且大多數(shù)個(gè)體均優(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é)束語(yǔ)

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