基于改進(jìn)粒子群算法的測試用例優(yōu)先排序

袁光輝

(安徽大學(xué) 江淮學(xué)院 理工部， 安徽 合肥 230031)

在大規(guī)模軟件演化進(jìn)程中，頻繁使用回歸測試可保證軟件質(zhì)量，但測試開銷巨大[1]。測試用例優(yōu)化技術(shù)可有效降低回歸測試成本，提高測試用例使用效率。測試用例優(yōu)先排序(Test Case Prioritization，TCP)作為一種高效實(shí)用的回歸測試優(yōu)化技術(shù)，受到廣泛關(guān)注。李征等[2]證實(shí)TCP問題是一個(gè)NP完全問題，并驗(yàn)證了遺傳算法和額外貪婪算法求解TCP問題的有效性。Walcott等[3]采用遺傳算法求解資源約束下復(fù)用測試用例子集，通過對該子集按平均代碼覆蓋率排序，有效提高了時(shí)間限制下的測試用例缺陷檢測率。李龍澍等[4]提出采用3個(gè)不同進(jìn)化規(guī)律的多種群遺傳算法處理測試用例排序問題，實(shí)驗(yàn)結(jié)果較標(biāo)準(zhǔn)遺傳算法具有更強(qiáng)的性能和更好的效率。陳云飛等[5]提出了基于粒子群優(yōu)化多目標(biāo)問題方法，采用遺傳算法中的交叉操作，設(shè)計(jì)了粒子的表示和狀態(tài)更新方式，選取多個(gè)優(yōu)化目標(biāo)，提高軟件測試效率。張衛(wèi)祥等[6]提出基于離散粒子群算法的TCP，重新定義粒子速度和位置，引入變異算子，動(dòng)態(tài)調(diào)整粒子慣性權(quán)重，提高算法性能。張娜等[7]提出基于Tent混沌的TCP，采用慣性權(quán)重改進(jìn)學(xué)習(xí)因子，通過混沌搜索跳出局部最優(yōu)，從而得到最優(yōu)解。將智能優(yōu)化算法應(yīng)用于測試用例優(yōu)先排序已被眾多學(xué)者證明是一種有效的方法，可大幅提高排序搜索的速度和效果。其中粒子群算法因收斂速度快、參數(shù)少、易于實(shí)現(xiàn)等特點(diǎn)在求解TCP問題時(shí)表現(xiàn)出較好的效果。但標(biāo)準(zhǔn)粒子群算法在求解TCP問題時(shí)，求解過程存在易早熟收斂、尋優(yōu)精度低、算法穩(wěn)定性不強(qiáng)等問題。

針對上述問題，本文以標(biāo)準(zhǔn)粒子群優(yōu)化算法(Standard Particle Swarm Optimization，SPSO)為基礎(chǔ)，結(jié)合混沌思想，通過對慣性權(quán)重、學(xué)習(xí)因子等參數(shù)調(diào)整，提出了改進(jìn)的粒子群優(yōu)化算法(Improved Particle Swarm Optimization，IPSO)，將該算法應(yīng)用于測試用例優(yōu)先排序。通過實(shí)驗(yàn)對比分析，驗(yàn)證本文所提測試用例優(yōu)先排序方法的可行性和有效性。

1 測試用例優(yōu)先排序建模

1.1 問題描述

TCP是指對測試用例集按照某種特定順序進(jìn)行排序，進(jìn)而找到一個(gè)最優(yōu)的排列，使其能在更短的時(shí)間發(fā)現(xiàn)更多的軟件缺陷，并以此來降低測試成本。Rothermel等[8]對TCP問題給出了具體定義，其形式為：令T為測試用例集，PT為T的全排列集，即T中所有可能的測試用例執(zhí)行次序集合，f為優(yōu)先排序目標(biāo)函數(shù)(其中定義域?yàn)镻T，值域?yàn)閷?shí)數(shù))。測試用例優(yōu)先排序就是尋找一個(gè)T′∈PT，使得對于任意T″(T″∈PT且T″≠T′)，均滿足f(T′)≥f(T″)。

由上述定義知，目標(biāo)函數(shù)f輸入某個(gè)測試用例特定執(zhí)行次序，輸出與排序目標(biāo)相關(guān)的判定值，其值越大說明該次序的排序效果越好，檢測軟件缺陷的能力越強(qiáng)。

1.2 度量準(zhǔn)則

軟件測試目的是通過設(shè)計(jì)、使用測試用例來盡可能多地發(fā)現(xiàn)被測軟件的缺陷。為了評估軟件測試的完整性和有效性，需要某些指標(biāo)來度量給定測試用例集系統(tǒng)測試的滿足程度，在設(shè)計(jì)TCP技術(shù)評測指標(biāo)時(shí)，通常使用測試用例序列盡早發(fā)現(xiàn)軟件內(nèi)部存在的缺陷，以此作為測試用例優(yōu)先排序的目標(biāo)。目前，研究人員采用最廣泛的評價(jià)指標(biāo)是由Rothermel等率先提出的APFD，即缺陷檢測平均百分比(Average Percentage of Fault Detection，APFD)，能有效評估TCP的平均缺陷檢測效率。Elbaum等[9]給出其計(jì)算公式為

(1)

其中n表示測試用例集T中參與評估測試的有效測試用例個(gè)數(shù)，m表示已檢測出的缺陷個(gè)數(shù)，TFi(1≤i≤m)表示首個(gè)檢測到缺陷i的測試用例在本次執(zhí)行序列中的位置編號(hào)。APFD評價(jià)指標(biāo)的取值范圍均是0～100%，其值越高表示對應(yīng)測試用例集檢測缺陷的速度越快，排序效率相對越好。

在測試用例執(zhí)行前，測試者無法事前預(yù)知測試用例執(zhí)行中將發(fā)現(xiàn)的待測程序缺陷個(gè)數(shù)。測試覆蓋率可在測試用例執(zhí)行前通過覆蓋率分析工具得出，因此，可使用覆蓋率信息指導(dǎo)測試用例的優(yōu)先排序。測試用例序列通常通過塊覆蓋率(APBC)、分支覆蓋率(APDC)和語句覆蓋率(APSC)等評價(jià)指標(biāo)來量化待測程序?qū)嶓w的覆蓋率，其評價(jià)指標(biāo)的計(jì)算公式與APFD類似。以APSC為例，計(jì)算公式為

(2)

其中TSi表示首個(gè)檢測到語句i的測試用例在本次執(zhí)行序列中的位置編號(hào)。

有效執(zhí)行時(shí)間(Effective Execution Time，EET)用于計(jì)算首次達(dá)到最大語句覆蓋率時(shí)執(zhí)行測試用例所需的總時(shí)間，其計(jì)算公式為

(3)

其中ETi表示執(zhí)行第i個(gè)測試用例時(shí)所需時(shí)間。

2 基于改進(jìn)粒子群算法的測試用例優(yōu)先排序設(shè)計(jì)

2.1 標(biāo)準(zhǔn)粒子群優(yōu)化算法(SPSO)

粒子群優(yōu)化算法是一種生物啟發(fā)式的群體智能優(yōu)化算法，最早由Kennedy和Eberhart提出[10]，模擬了自然界中鳥群飛行及覓食的個(gè)體行為與群體行為。

SPSO基本思想為：算法將每只鳥看作一個(gè)粒子，把優(yōu)化問題在搜索空間中的潛在解表示為粒子在D維空間中的位置，各粒子根據(jù)個(gè)體最優(yōu)解和群體最優(yōu)解的大小，通過速度來調(diào)整其飛行方向和位置，以此尋找問題的最優(yōu)解。

(4)

(5)

從公式(4)中可知，粒子的更新速度由3項(xiàng)組成：第一項(xiàng)是粒子自身的速度，是維持粒子運(yùn)動(dòng)的基本；第二項(xiàng)是粒子的認(rèn)知分量，即在搜索過程中積累的自身經(jīng)驗(yàn)；第三項(xiàng)是粒子的社會(huì)分量，即粒子在搜索過程中種群的全體經(jīng)驗(yàn)。通過3項(xiàng)的有機(jī)擬合，粒子可以在本身運(yùn)動(dòng)的基礎(chǔ)上，通過學(xué)習(xí)自身經(jīng)驗(yàn)與群體經(jīng)驗(yàn)來調(diào)整運(yùn)動(dòng)狀態(tài)，以進(jìn)行全局最優(yōu)的搜索。

SPSO結(jié)構(gòu)簡單、參數(shù)少、交互機(jī)制容易、全局搜索能力強(qiáng)等特點(diǎn)，相較于其他群體智能算法而言，其在解決連續(xù)或離散多目標(biāo)優(yōu)化問題上都有很大優(yōu)勢。但隨著算法的不斷迭代，粒子種群的多樣性也會(huì)在進(jìn)化中隨之降低，容易出現(xiàn)早熟收斂現(xiàn)象，進(jìn)而導(dǎo)致算法陷入局部最優(yōu)。

2.2 改進(jìn)的粒子群優(yōu)化算法(IPSO)

2.2.1 粒子編碼及種群初始化

測試用例優(yōu)先排序輸入為若干測試用例組成的測試用例集，輸出結(jié)果為測試用例執(zhí)行序列，其排序過程只是交換測試用例的排列位置，因此，本文采用實(shí)數(shù)編碼方式表示測試用例集中每個(gè)測試用例的序號(hào)，而每個(gè)粒子則表示一種測試用例排列方案。

為提高粒子群算法初始解的質(zhì)量，使粒子最大程度地對搜索空間的每個(gè)方位進(jìn)行遍歷，本文算法使用混沌優(yōu)化思想初始化粒子群。經(jīng)混沌化的粒子序列能均勻地分布在搜索空間，提高粒子群的多樣性，便于算法求解。研究表明，Tent映射比Logistic映射產(chǎn)生的混沌序列更具有全局遍歷性、分布較均勻等特點(diǎn)，所以本文在初始化粒子種群時(shí)引入Tent映射，其公式定義為

(6)

2.2.2 適應(yīng)度函數(shù)設(shè)計(jì)

適應(yīng)度函數(shù)用來指導(dǎo)算法尋優(yōu)方向，可依據(jù)適應(yīng)度值的大小來淘汰種群中的劣質(zhì)解，以便算法快速收斂、精確尋找最優(yōu)解。在對測試用例排序時(shí)，對于較早達(dá)到較高代碼覆蓋率的測試用例序列而言，其發(fā)現(xiàn)錯(cuò)誤的能力較強(qiáng)，即在盡短時(shí)間內(nèi)發(fā)現(xiàn)更多缺陷。因此，可用程序?qū)嶓w覆蓋率來構(gòu)造IPSO的適應(yīng)度函數(shù)。本文選取公式(2)定義的平均代碼覆蓋率(APSC)和公式(3)定義的有效執(zhí)行時(shí)間(EET)作為優(yōu)化目標(biāo)，選取公式(1)定義的缺陷檢測率(APFD)作為測試用例排序的評測指標(biāo)。

2.2.3 自適應(yīng)調(diào)整慣性權(quán)重及學(xué)習(xí)因子

公式(4)中ω為慣性權(quán)重，表示粒子在問題空間中的歷史搜索速度對當(dāng)前速度的影響，在SPSO算法中，慣性權(quán)重一般設(shè)為固定值。如權(quán)重設(shè)置過大，有利于算法的全局搜索，易陷入局部最優(yōu)，不易得到精確解；如其設(shè)置過小，雖有利于局部搜索，但會(huì)導(dǎo)致種群收斂速度變慢。

隨著算法迭代次數(shù)的不斷增加，粒子是否需要調(diào)整搜索范圍應(yīng)與粒子自身的適應(yīng)度值緊密相關(guān)，因此，適應(yīng)度值不同粒子的慣性權(quán)重也應(yīng)有所不同。根據(jù)分析慣性權(quán)重與適應(yīng)度之間的關(guān)系，本文提出自適應(yīng)調(diào)節(jié)的慣性權(quán)值策略，慣性權(quán)重公式如下：

(7)

其中fiti表示適應(yīng)度函數(shù)值，gBest表示全局極值。由公式(7)可知，當(dāng)粒子的適應(yīng)度值較小時(shí)，對應(yīng)的ω越大，粒子需要以較快的速度進(jìn)行全局搜索，提高算法收斂效率；反之，當(dāng)粒子的適應(yīng)度值較大時(shí)，越接近最優(yōu)解，對應(yīng)的ω越小，粒子應(yīng)降低搜索速度，并在局部區(qū)域精細(xì)探索，進(jìn)而尋找最優(yōu)解。自適應(yīng)慣性權(quán)重可保證粒子群在算法初期具有較好的探索能力，而在晚期具有較好的開發(fā)能力。

公式(4)中l(wèi)1和l2為學(xué)習(xí)因子，分別表示粒子對自身歷史最優(yōu)和整體歷史最優(yōu)的學(xué)習(xí)認(rèn)知能力，一般取l1=l2=2。在算法初期，l1>l2，其較大的l1值便于粒子更多地依靠自身的認(rèn)知搜索，避免早熟；較小的l2值可弱化其他粒子的影響，加快算法收斂速度。在算法晚期，l1

根據(jù)上述分析，本文提出了隨慣性權(quán)重變化而動(dòng)態(tài)調(diào)整的學(xué)習(xí)因子公式：

(8)

其中l(wèi)1,start、l1,end分別表示學(xué)習(xí)因子l1的初始值和終止值；l2,start、l2,end分別表示學(xué)習(xí)因子l2的初始值和終止值。由公式(8)可知，此學(xué)習(xí)因子可保證算法前期自我認(rèn)知能力強(qiáng)，后期社會(huì)認(rèn)知能力強(qiáng)，達(dá)到更快的收斂速度和更好的尋優(yōu)精度。

2.2.4 混沌搜索

混沌是非線性確定系統(tǒng)中出現(xiàn)的類似隨機(jī)的不規(guī)則運(yùn)動(dòng)，具有隨機(jī)性、遍歷性及規(guī)律性三大特性。結(jié)合混沌運(yùn)動(dòng)的特性，利用混沌映射完成優(yōu)化變量從解空間到混沌空間的轉(zhuǎn)換，進(jìn)行混沌搜索，可幫助算法跳出局部極小點(diǎn)，保證種群多樣性，并快速找到全局最優(yōu)解。

本文算法利用Tent混沌模型進(jìn)行混沌搜索，對公式(6)中Tent映射進(jìn)行貝努利移位變換，變換后的公式為

(9)

混沌搜索優(yōu)化的具體步驟如下：

步驟1 將當(dāng)前全局最優(yōu)值Pg按式(10)由取值區(qū)間[pmin,pmax]映射至混沌變量的取值區(qū)間[0,1]，

(10)

(11)

步驟4 選取最優(yōu)解向量P*，替換掉在迭代中不是全局最優(yōu)且所有個(gè)體極值亦未發(fā)生變化的粒子個(gè)體。

在SPSO中引入混沌搜索方法生成新粒子，并用新粒子代替原種群的惰性粒子，幫助算法跳出某個(gè)小范圍，進(jìn)而使算法擺脫早熟收斂。

2.3 改進(jìn)粒子群算法求解測試用例優(yōu)先排序框架

通過前文對TCP問題建模分析及對SPSO相關(guān)參數(shù)的改進(jìn)與調(diào)整，將改進(jìn)的粒子群算法用于求解測試用例優(yōu)先排序，基本流程如下：

(1)設(shè)定粒子種群大小N、搜索維數(shù)D、最大迭代次數(shù)T、速度上限vmax、搜索范圍、學(xué)習(xí)因子的初始值和終止值等相關(guān)參數(shù)；

(2)使用Tent映射粒子種群的位置和速度，即隨機(jī)生成測試用例優(yōu)先級序列；

(3)根據(jù)公式(2)、(3)計(jì)算每個(gè)粒子的適應(yīng)度值；

(4)如粒子適應(yīng)度值優(yōu)于個(gè)體極值，則更新它；

(5)如粒子適應(yīng)度值優(yōu)于全局極值，則更新它；

(6)進(jìn)行混沌搜索，性能最好的可行解代替原種群的惰性粒子；

(7)根據(jù)公式(7)計(jì)算慣性權(quán)重ω，根據(jù)公式(8)計(jì)算學(xué)習(xí)因子l1和l2；

(9)獲得新測試用例優(yōu)先級序列；

(10)判斷是否滿足終止條件，若是，則輸出測試用例優(yōu)先級序列，算法停止，否則，迭代次數(shù)增1，轉(zhuǎn)至步驟(3)。

3 實(shí)驗(yàn)分析

3.1 實(shí)驗(yàn)設(shè)計(jì)

為了驗(yàn)證本文所改進(jìn)的粒子群算法(IPSO)的優(yōu)越性及在測試用例排序中的有效性，通過兩組實(shí)驗(yàn)進(jìn)行測試，將其測試的結(jié)果與標(biāo)準(zhǔn)粒子群算法(SPSO)、文獻(xiàn)[5]的粒子群算法(PSO*)的測試結(jié)果進(jìn)行對比。

實(shí)驗(yàn)1 采用平均適應(yīng)度值作為評價(jià)指標(biāo)，使用兩個(gè)典型測試函數(shù)進(jìn)行對比實(shí)驗(yàn)，以驗(yàn)證算法性能。各算法的參數(shù)設(shè)置為：在SPSO和PSO*算法中，慣性權(quán)重ω為0.7，學(xué)習(xí)因子l1=l2=2；在IPSO算法中，慣性權(quán)重ω由公式(7)計(jì)算，學(xué)習(xí)因子l1和l2由公式(8)計(jì)算。實(shí)驗(yàn)時(shí)粒子群規(guī)模N為40，維數(shù)D為30，最大迭代次數(shù)T為500，測試函數(shù)如表1所示。

表1 測試函數(shù)及相關(guān)參數(shù)

實(shí)驗(yàn)2 為檢測本文所提的IPSO在解決測試用例優(yōu)先排序問題時(shí)的有效性，實(shí)驗(yàn)從軟件工件基礎(chǔ)設(shè)施庫(Software-artifact Infrastructure Repository，SIR)中選擇printtokens、schedule、tcas、replace、space等5個(gè)程序作為實(shí)驗(yàn)待測程序，5個(gè)待測程序統(tǒng)計(jì)信息如表2所示。因待測程序的用例集合中含有許多冗余測試用例，為保障測試結(jié)果的可靠性，在實(shí)驗(yàn)開始前應(yīng)先從用例池中選取冗余度較小的目標(biāo)測試用例集，其語句覆蓋率達(dá)到用例池的最大語句覆蓋率即可。

表2 待測程序統(tǒng)計(jì)信息

表3 IPSO主要參數(shù)配置

本文程序使用MATLAB2012a實(shí)現(xiàn)，實(shí)驗(yàn)主要參數(shù)配置如表3所示。其運(yùn)行環(huán)境為：Intel Core i5-4590 CPU，主頻3.3 GHz，內(nèi)存4 GB，Windows 7操作系統(tǒng)。

3.2 結(jié)果與分析

為避免不確定因素帶來的影響，保證3種算法比較的科學(xué)性、公平性，對3種算法各評價(jià)指標(biāo)分別獨(dú)立運(yùn)行100次，取平均。通過對實(shí)驗(yàn)1的仿真測驗(yàn)，3種算法在兩個(gè)測試函數(shù)上的平均適應(yīng)度值如表4所示。

表4 兩個(gè)測試函數(shù)的平均適應(yīng)度值

從表4可以看出，在求解F1和F2函數(shù)最優(yōu)時(shí)，本文所提的IPSO算法，平均適應(yīng)度值明顯小于其他兩個(gè)算法，其搜索精度相較于SPSO和PSO*算法均提高了5倍以上。實(shí)驗(yàn)結(jié)果表明，IPSO算法在求解單峰函數(shù)(Sphere)和多峰函數(shù)(Griewank)上均有優(yōu)勢，能達(dá)到較好的尋優(yōu)精度并找到全局最優(yōu)解。

實(shí)驗(yàn)2使用3種算法對表2中的5個(gè)待測程序進(jìn)行實(shí)驗(yàn)比較，從缺陷檢測率、測試用例語句覆蓋率和有效執(zhí)行時(shí)間等方面評價(jià)優(yōu)劣。實(shí)驗(yàn)結(jié)果如箱形圖1、2、3所示。

圖1 SPSO、PSO*、IPSO針對各測試程序的APFD值

圖2 SPSO、PSO*、IPSO針對各測試程序的APSC值

圖3 SPSO、PSO*、IPSO針對各測試程序的EET值

通過圖1的箱形圖對比可知，IPSO算法在缺陷檢測率上明顯優(yōu)于SPSO和PSO*算法，其中tcas程序數(shù)值較集中。通過圖2的箱形圖對比可知，IPSO算法在語句檢測率上也優(yōu)于SPSO和PSO*算法，取值區(qū)間波動(dòng)較小，優(yōu)化效果更加穩(wěn)定，其中replace程序優(yōu)化最為明顯。通過圖3的箱形圖對比可知，IPSO算法的EET值比SPSO和PSO*算法大幅降低，總時(shí)間基本在0.8 s以內(nèi)，由于space程序規(guī)模稍大，所用時(shí)間較長。IPSO算法通過Tent映射初始化粒子群，防止其落入小周期，并引入隨適應(yīng)度值自適應(yīng)調(diào)節(jié)的慣性權(quán)重及學(xué)習(xí)因子，平衡算法的全局搜索和局部開發(fā)能力，并對惰性粒子進(jìn)行混沌搜索優(yōu)化，使其跳出局部最優(yōu)，實(shí)驗(yàn)結(jié)果表明，本文所提方法較SPSO和文獻(xiàn)[5]的粒子群算法(PSO*)收斂速度快、尋優(yōu)精度高。綜上所述，IPSO在測試用例優(yōu)先排序問題上效果顯著，在缺陷檢測率、測試用例語句覆蓋率和有效執(zhí)行時(shí)間等方面均有優(yōu)勢。

4 結(jié) 語

本文基于標(biāo)準(zhǔn)粒子優(yōu)化算法，引入Tent混沌映射初始粒子種群，通過非線性自適應(yīng)調(diào)節(jié)因子方式來平衡算法性能，對惰性粒子進(jìn)行混沌搜索優(yōu)化，以提高種群的多樣性，使改進(jìn)的算法具有較快的收斂速度及較強(qiáng)的尋優(yōu)能力。采用5個(gè)待測程序?qū)?yōu)先級排序進(jìn)行實(shí)驗(yàn)驗(yàn)證，結(jié)果表明，該方法對TCP問題在缺陷檢測率、測試用例語句覆蓋率和有效執(zhí)行時(shí)間等方面均有優(yōu)勢，大幅提高了軟件測試效率。下一步將就其他群體智能算法在軟件測試中的應(yīng)用做進(jìn)一步的研究。