基于離散粒子群算法的測試用例優(yōu)先排序

張衛(wèi)祥，齊玉華，李德治

(1.北京跟蹤與通信技術(shù)研究所，北京 100094; 2.中國宇航學(xué)會 飛行器測控專委會，北京 100094)

(*通信作者電子郵箱vxiang@126.com)

基于離散粒子群算法的測試用例優(yōu)先排序

張衛(wèi)祥1,2*，齊玉華1,2，李德治1,2

(1.北京跟蹤與通信技術(shù)研究所，北京 100094; 2.中國宇航學(xué)會 飛行器測控專委會，北京 100094)

(*通信作者電子郵箱vxiang@126.com)

測試用例優(yōu)先排序技術(shù)能夠有效提高回歸測試效率，是軟件測試的熱點研究課題之一。針對基于需求的測試用例優(yōu)先排序方法可操作性差的問題，提出了一種改進的基于測試點覆蓋和離散粒子群優(yōu)化算法的求解方法(TCP-DPSO)。首先，把影響排序的各種因素分為測試收益型因素和測試成本型因素兩大類，通過加權(quán)平均的方式進行歸一化，得到基于需求的通用測試平均收益率評價指標(biāo)；然后，利用交換子和基本交換序列定義粒子的位置和速度，借鑒遺傳算法(GA)變異策略引入變異算子，采用時變慣性權(quán)重調(diào)整粒子的探索能力和開發(fā)能力，促進可持續(xù)進化和逼近優(yōu)化目標(biāo)。實驗結(jié)果表明，TCP-DPSO在最優(yōu)解質(zhì)量上與遺傳算法相當(dāng)，大幅優(yōu)于隨機測試，在最優(yōu)解成功率和平均求解時間上優(yōu)于遺傳算法，具有更好的算法穩(wěn)定性。

軟件測試；測試用例優(yōu)先排序；離散粒子群優(yōu)化；評價指標(biāo)；黑盒測試

0 引言

在軟件的開發(fā)、維護過程中，由于修復(fù)軟件缺陷、改進軟件功能、增強軟件性能或者重構(gòu)部分代碼等原因，經(jīng)常需要對軟件進行更動。近年來，隨著增量式或迭代式軟件開發(fā)方式的流行，軟件更動得愈加頻繁。回歸測試可有效驗證軟件更動以及更動影響到的軟件原有功能或模塊的正確性，是保證軟件質(zhì)量的不可或缺的技術(shù)手段。但有數(shù)據(jù)表明，回歸測試費用一般占軟件維護預(yù)算的50%以上[1]。如何開展自動和高效的回歸測試，已成為軟件測試甚至軟件工程領(lǐng)域的一個重要研究課題。

在回歸測試中，測試用例的維護策略是一個核心問題[2]。一種簡單的維護策略是重新執(zhí)行全部已有的測試用例，但經(jīng)常由于存在項目預(yù)算緊張、工程進度不允許、部分測試用例已失效、已有測試用例不能覆蓋新增測試需求等諸多原因，導(dǎo)致重新執(zhí)行全部用例是不可行的。為此，學(xué)術(shù)界和工業(yè)界對測試用例維護進行研究，提出了包括失效測試用例的識別和修復(fù)、測試用例選擇、測試用例優(yōu)先排序(Test Case Prioritization, TCP)、測試用例集縮減和測試用例集擴充等[3-4]在內(nèi)的一系列典型技術(shù)。

TCP技術(shù)按照給定的排序準(zhǔn)則對測試用例進行排序，通過優(yōu)化測試用例的執(zhí)行次序來達到提高軟件測試效率的目的，一直是回歸測試的研究熱點之一[5]。Wong等[6]早在1997年進行了相關(guān)研究，結(jié)合測試用例歷史覆蓋信息和代碼修改信息識別出冗余測試用例，對非冗余測試用例根據(jù)覆蓋能力進行排序。Elbaum等[7]在2000年給出了TCP問題的一般性描述。Rothermel等[8]指出，除最大化測試用例集的早期缺陷檢測速率外，還可以以代碼覆蓋率、高風(fēng)險缺陷的檢測率和系統(tǒng)可靠性等其他指標(biāo)作為測試用例排序目標(biāo)。陳翔等[5]把TCP技術(shù)分為基于代碼的、基于模型的和基于需求的TCP等3類，目前基于代碼的TCP技術(shù)研究較為充分，從貪婪法、機器學(xué)習(xí)法、融合專家知識法等不同角度已有不少的研究成果，相對而言基于需求的TCP技術(shù)的研究成果還不多見。

粒子群優(yōu)化(Particle Swarm Optimization, PSO)算法是在1995年由Kennedy等[9]首先提出的。在PSO中，用一組多維向量表示不同粒子，根據(jù)個體最優(yōu)解和群體最優(yōu)解不斷修正粒子的飛行方向和速度。由于相對簡單、易于實現(xiàn)、參數(shù)少和不需要梯度信息等特點，PSO在連續(xù)優(yōu)化問題和離散優(yōu)化問題中都可取得良好效果，已成為智能優(yōu)化領(lǐng)域近年來的一個研究熱點。

在離散粒子群優(yōu)化(Discrete PSO, DPSO)算法研究方面，Kennedy等[10]提出了一種針對0-1規(guī)劃問題的二進制粒子群優(yōu)化算法，每個粒子用一個二進制變量來表示，粒子的速度表示為二進制變量的翻轉(zhuǎn)概率，通過變量翻轉(zhuǎn)來實現(xiàn)粒子在空間中的移動。Hu等[11]給出了一種求解置換排列問題的方法，用置換排列表示粒子，用粒子的相似度來定義速度并決定粒子位置變化的概率。Clerc[12]給出一種求解TSP問題的方法，粒子位置用所有城市的一個排列來表示，所有城市的全部排列就構(gòu)成了粒子的搜索空間。DPSO在電力系統(tǒng)、超大規(guī)模集成電路設(shè)計、無線傳感器網(wǎng)絡(luò)以及數(shù)據(jù)挖掘等領(lǐng)域中也有不少的應(yīng)用研究[13]。

由于TCP問題本質(zhì)上是尋找最優(yōu)測試用例排列次序的離散優(yōu)化問題，因此使用DPSO進行求解是可行的，但目前的研究還很少見，蘇貝貝[14]提出了一種基于改進代碼塊覆蓋的粒子群算法，用于結(jié)構(gòu)測試中的TCP問題，而功能測試中的應(yīng)用研究還未見到相關(guān)成果。

本文提出了一種求解TCP問題的DPSO(DPSO for TCP, TCP-DPSO)方法，主要思路是：

1)重新定義粒子的位置和速度，引入交換子和基本交換序列的概念，把粒子位置表示為所有測試用例的一個排列，把粒子速度定義為一個粒子位置變換為另一個粒子位置的基本交換序列。

2)提出基于需求的測試平均收益率評價指標(biāo)，作為評估粒子位置優(yōu)劣的適應(yīng)度函數(shù)。

3)借鑒遺傳算法(Genetic Algorithm, GA)中的變異策略，引入變異算子，促使群體可持續(xù)進化。

4)采用時變慣性權(quán)重，調(diào)整粒子的探索能力和開發(fā)能力。

實驗驗證及與已有成果的比較分析表明，TCP-DPSO能夠有效求解TCP問題，且效果優(yōu)于遺傳算法和隨機測試。

1 測試用例優(yōu)先排序問題描述

1.1 基于需求的TCP問題

Elbaum等[7]對TCP問題給出的一般性描述為：給定測試用例集T、T的全排列集PT、排序目標(biāo)函數(shù)f:PT→R，求解T′∈PT，使得對?T″∈PT(T″≠T′)，有f(T′)≥f(T″)。

由一般性描述可知，函數(shù)f的每個輸入是全部測試用例的一個特定執(zhí)行次序，其輸出值越大說明則排序效果越好。

按照TCP問題排序依據(jù)的不同，陳翔等[5]把TCP技術(shù)分為基于代碼的、基于模型的和基于需求的TCP技術(shù)等3類。目前的研究主要集中在基于代碼的TCP技術(shù)。

基于需求的TCP技術(shù)的研究成果還比較少。Srikanth等[15]考慮需求變更的可能性、客戶定義的需求優(yōu)先級、需求的實現(xiàn)復(fù)雜度和需求的缺陷傾向性等影響因素，提出了系統(tǒng)測試階段的PORT排序方法。屈波等[16]基于測試用例的設(shè)計信息，提出了一組基于需求的測試用例優(yōu)先級動態(tài)調(diào)整算法。Zhang等[17]提出了考慮測試需求優(yōu)先級和測試用例執(zhí)行開銷的基于Total策略和Additional策略的TCP技術(shù)。Krishnamoorthi等[18]基于軟件需求規(guī)約，考慮了包括需求優(yōu)先級、需求變動信息、需求完整性、需求實現(xiàn)復(fù)雜度、需求可追蹤性和缺陷影響程度等更多的影響因素，對測試用例進行排序。

綜合考慮影響測試用例排序的各種因素，總體上可以分為兩大類：測試成本型因素(Cost-Keys)，主要表現(xiàn)于測試用例執(zhí)行花銷等；測試收益型因素(Win-Keys)，主要表現(xiàn)于測試需求的重要程度和缺陷的潛在危害等。Cost-Keys和Win-Keys包含了上面提到的各種影響因素。有的影響因素所起的作用和測試用例次序是正相關(guān)的，有的是負相關(guān)的，有的影響大，有的影響小，但都可以通過加權(quán)平均的方式進行歸一化。

不失一般性，令Cost-Keys因素全集為C={c1,c2,…,cn}，Win-Keys因素全集為W={w1,w2,…,wm}，對任一測試用例ti∈T，有：

(1)

下節(jié)將利用Wi、Ci給出基于需求的TCP技術(shù)的一種通用量化指標(biāo)——測試平均收益率評價指標(biāo)。

1.2 評價指標(biāo)APWC

與隨機測試相比，TCP技術(shù)的一個顯著優(yōu)點是能夠更快地檢查出錯誤?；诖耍珽lbaum等[19]給出APFD(AveragePercentageofFaultDetection)評價指標(biāo),采用測試用例使用個數(shù)和檢測錯誤個數(shù)之間的關(guān)系來量化測試用例序列的優(yōu)劣。當(dāng)給定測試用例的執(zhí)行次序時，可用APFD指標(biāo)計算測試用例執(zhí)行過程中檢測到缺陷的平均累計比例，但需要事先知曉測試用例的缺陷檢測信息。一般地，缺陷檢測信息在測試用例全部執(zhí)行前是不可能知道的，所以APFD存在著明顯不足。

Li等[20]隨后提出APBC(AveragePercentageofBlockCoverage)、APDC(AveragePercentageofDecisionCoverage)和APSC(AveragePercentageofStatementCoverage)等系列指標(biāo)，分別量化測試用例序列對程序塊、分支和語句的覆蓋速率。由于在測試用例執(zhí)行之前可以通過覆蓋率分析工具得到覆蓋率信息，故可在測試用例全部執(zhí)行之前使用APBC、APDC和APSC等指標(biāo)，但是這些指標(biāo)顯然更適合于基于代碼的結(jié)構(gòu)測試。

在基于需求的功能測試中，測試人員以軟件規(guī)格說明為依據(jù)，進行測試用例的設(shè)計。一般流程是：首先將軟件需求轉(zhuǎn)化為測試需求；其次把測試需求細化分解為測試點；然后針對測試點進行測試用例設(shè)計；最后形成測試用例集合。張衛(wèi)祥等[21]提出基于測試點覆蓋的評價指標(biāo)APTC(Average Percentage of Test-Point Coverage)。對于測試用例集Φ={T1,T2,…,Tn}，APTC的計算公式[21]定義為：

(2)

其中，TTi表示首個可覆蓋到第i個測試點的測試用例在該用例序列中所處的次序，m為測試點個數(shù)，n為測試用例個數(shù)。APTC的取值范圍為0～100%，取值越高說明對測試點覆蓋的速率越快。

在這里，考慮到各因素對測試用例排序結(jié)果的影響，根據(jù)上節(jié)的分析，利用式(1)中的綜合收益和綜合成本對APTC進行改進。把評估目標(biāo)調(diào)整為單位綜合成本取得的綜合收益，提出測試平均收益率評價指標(biāo)APWC(Average Percentage of Win-Cost Coverage)。

APWC公式化表示為：

考慮如表 1所示的實例，共有10個測試點1～10和5個測試用例A～E，對于兩個不同的測試用例序列A-B-C-D-E和E-D-C-B-A，計算可得APTC取值分別為50%、64%，故執(zhí)行次序2的效果優(yōu)于執(zhí)行次序1。圖 1中折線下方陰影面積占整個面積的比例即為各執(zhí)行次序的APTC值。

表1 測試用例與測試點的對應(yīng)關(guān)系的一個實例

現(xiàn)假設(shè)，測試用例B的綜合成本CB是其他測試用例的2倍，但其綜合收益WB高于其他測試用例，它所覆蓋的測試點(即測試點1，5，6，7)的重要程度是其他測試點的2倍。即，在假設(shè)單位成本和單位重要程度均為1的情況下，測試用例B的綜合成本為2，測試點1，5，6，7重要程度值為2。根據(jù)公式可計算測試用例序列A-B-C-D-E和E-D-C-B-A的APTW的取值分別為56%和68%，如圖2所示。

可見，在不同測試用例的成本與收益差別較大時，APWC能夠更為準(zhǔn)確地反映測試用例優(yōu)先執(zhí)行序列的價值。

圖1 不同測試用例序列對應(yīng)的APTC值

圖2 不同測試用例序列對應(yīng)的APWC值

2 基于離散粒子群優(yōu)化的求解方法

本章給出求解TCP問題的離散粒子群優(yōu)化(DPSO for TCP， TCP-DPSO)算法。首先介紹標(biāo)準(zhǔn)粒子群優(yōu)化算法，隨后給出TCP-DPSO算法的實現(xiàn)原理和基本流程。

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

粒子群優(yōu)化算法的基本思想是：由m個粒子組成的群體在D維搜索空間中以一定的速度各自飛行以尋找最佳位置(最優(yōu)解)，每個粒子在搜索時，受到自身歷史最好點和群體內(nèi)其他粒子歷史最好點的影響，不斷進行自身位置優(yōu)化。

假設(shè)第i個粒子的位置表示為xi=(xi1,xi2,…,xiD)，速度為vi=(vi1,vi2,…,viD)，1≤i≤m。第i個粒子的歷史最好點為pi=(pi1,pi2,…,piD)，群體內(nèi)所有粒子的歷史最好點為pg=(pg1,pg2,…,pgD)。

粒子的位置和速度根據(jù)式(4)～(5)進行變化：

(4)

(5)

基于上述原理優(yōu)化的粒子群算法被稱為標(biāo)準(zhǔn)粒子群優(yōu)化算法，最初用于解決連續(xù)優(yōu)化問題，速度變量是連續(xù)的，但是許多實際應(yīng)用問題，比如著名的旅行商問題(TravelingSalesmanProblem,TSP)，是離散的，其變量是有限的，因此需要研究離散版本的粒子群算法。最典型的兩種離散策略是二進制編碼和順序編碼。下節(jié)采用順序編碼策略，提出用于TCP問題的TCP-DPSO算法。

2.2 TCP-DPSO算法實現(xiàn)原理

2.2.1 粒子群編碼

對于含有n個測試用例的測試用例集T={t1,t2,…,tn}和給定的排序目標(biāo)f，TCP問題的實質(zhì)是找到一個測試用例序列，使得排序目標(biāo)f達到最優(yōu)。

為了表示粒子速度，引入交換子和基本交換序的概念。

定義1 交換子。對于任一粒子位置，一個交換子s=s(p,q)的作用是交換其第p個和第q個元素的位置，從而形成一個新的粒子位置。

定義2 交換序列。稱一個或多個交換子的有序隊列為一個交換序列，記為S=(s1,s2,…,sl)。在交換序列中，各交換子的順序是有意義的，因為一個交換序列作用于某粒子位置上，意味著此交換序列中的所有交換子依次作用于該粒子位置上。交換序列中包含的交換子的個數(shù)稱為交換序列的長度。

例如，粒子位置x經(jīng)S作用后變?yōu)閤″，即x″=x+S=x+(s1,s2,…,sl)=[(x+s1)+s2]+…+sl。

定義3 基本交換序列。不同的交換序列作用在同一粒子位置上可能產(chǎn)生相同的效果，稱具有相同作用效果的交換序列的集合為交換序列的等價集，稱擁有最少交換子的交換序列為該等價集的基本交換序列。

可以看出，粒子速度就是從一個粒子位置變換為另一個粒子位置的交換序列。為了保證唯一性，令粒子速度取基本交換序列。

2.2.2 粒子位置與速度的迭代方程

為了給出粒子位置與粒子速度的迭代方程，需要定義減法算子(粒子位置與粒子位置相減)、加法算子(粒子位置與粒子速度相加)、乘法算子(粒子速度與實數(shù)相乘)、合并算子(粒子速度與粒子速度相加)。

定義4 減法算子-。兩個粒子位置進行減法運算，其結(jié)果是一組交換子，準(zhǔn)確地講，是減數(shù)變成被減數(shù)所需的一個基本交換序列(粒子速度)。

例如，對粒子位置x1=(1,2,3,4,5)和x2=(3,1,5,2,4)，x2-x1=((1,3),(2,3),(3,5),(4,5))。

定義5 加法算子+。粒子位置與粒子速度相加，其結(jié)果是把粒子速度對應(yīng)的交換序列作用于該粒子位置后形成的新粒子位置。加法算子滿足交換律。

例如，對粒子位置x1=(1,2,3,4,5)和粒子速度v1=((1,3),(2,3),(3,5),(4,5))，其和x1+v1=v1+x1=(3,1,5,2,4)。

定義6 乘法算子×。粒子速度(長度為l的交換序列S)與實數(shù)α∈[0,1]的乘法運算，其結(jié)果是對S的交換子隊列截斷而形成的長度為α×l(取整)的新交換序列S′。

定義7 合并算子⊕。粒子速度的合并運算就是對它們對應(yīng)的交換序列的合并操作，其結(jié)果是把后一個交換序列的交換子隊列連接到前一個交換序列的交換子隊列的隊尾，形成一個更長的交換序列。合并運算滿足分配律。

根據(jù)上述定義，對式(4)、(5)進行更新，給出TCP-DPSO算法粒子位置與速度的迭代方程：

(6)

(7)

其中：ωk為慣性權(quán)重，將在下節(jié)介紹；α、β分別表示粒子自身極值和群體全局極值對粒子的影響程度，值越大說明影響程度越大。為了平衡粒子的自我總結(jié)和向群體中優(yōu)秀個體學(xué)習(xí)的能力，進行如下設(shè)置：當(dāng)?shù)螖?shù)不大于最大迭代次數(shù)的一半時(k≤Kmax/2)，取α=Cmax,β=Cmin；否則，取α=Cmin,β=Cmax。一般地，可令Cmax=0.95,Cmin=0.35。

2.2.3 慣性權(quán)重設(shè)計

慣性權(quán)重是粒子群優(yōu)化算法的重要參數(shù)，常見的設(shè)置方法有固定權(quán)重、時變權(quán)重、模糊權(quán)重等。固定權(quán)重方法賦予慣性權(quán)重一個0和1之間的常數(shù)值，有實驗表明，群體規(guī)模越小需要的慣性權(quán)重越大，反之亦然。模糊權(quán)重方法使用模糊系統(tǒng)來動態(tài)調(diào)節(jié)慣性權(quán)重，例如Shi等[22]使用了具有9條規(guī)則、2個輸入和1個輸出的模糊系統(tǒng)。時變權(quán)重方法能使粒子群在初期具有較好的探索能力，而在后期具有較好的開發(fā)能力。

假設(shè)慣性權(quán)重的取值范圍為[ωmin,ωmax]，最大迭代次數(shù)為Kmax，TCP-DPSO算法采用式(8)定義第k次迭代時的慣性權(quán)重：

ωk=ωmax-(ωmax-ωmin)×(k/Kmax)2

(8)

一般地，令ωmax=0.9，ωmin=0.4，Kmax根據(jù)實際問題確定。

2.2.4 變異策略設(shè)計

隨著迭代的進行，由于排列的趨同性，在粒子到達局部最優(yōu)位置附近時，不活躍粒子的速度將會越來越小，甚至停止運動。因此，在TCP-DPSO算法中引入變異策略，用隨機產(chǎn)生的新粒子替換趨于停滯的粒子，以促進群體的可持續(xù)進化。

具體地，設(shè)置臨界值SimilarDegree，在每次迭代后對粒子活躍度進行判斷，當(dāng)一個粒子與局域最優(yōu)位置的排列相似度(測試用例個數(shù))大于SimilarDegree時，隨機生成新粒子替代該粒子。

2.2.5 適應(yīng)度函數(shù)設(shè)計

以執(zhí)行測試序列時單位綜合成本取得的綜合收益為評價目標(biāo)，采用式(3)定義的測試平均收益率評價指標(biāo)APWC作為適應(yīng)度函數(shù)Fitness，也可采用其他評價指標(biāo)。

需注意的是，APWC為一般性指標(biāo)，可通過設(shè)置適當(dāng)假設(shè)條件或選擇特定參數(shù)使其進行簡化，例如，假設(shè)所有測試用例的綜合收益相同且綜合成本相等，APWC就簡化為文獻[21]中的APTC。

2.3 TCP-DPSO算法基本流程

TCP-DPSO算法的基本步驟包括：

1)對粒子群進行隨機初始化，給每個粒子賦予一個隨機的初始位置和一個隨機的交換序列。

2)使用適應(yīng)度函數(shù)Fitness計算每個粒子的適應(yīng)度值。

3)比較每個粒子的當(dāng)前適應(yīng)值和自身歷史最優(yōu)位置pi的適應(yīng)值，如果當(dāng)前值更優(yōu)，則更新pi。

4)比較每個粒子的當(dāng)前適應(yīng)值和群體最優(yōu)位置pg的適應(yīng)值，如果當(dāng)前值更優(yōu)，則更新pg。

5)使用變異策略判斷每個粒子的活躍度，并用隨機產(chǎn)生的新粒子替換趨于停滯的粒子。

6)使用式(8)調(diào)整時變慣性權(quán)重ωk。

7)使用式(6)和式(7)更新粒子的速度和位置。

8)如果當(dāng)前迭代次數(shù)k達到預(yù)設(shè)的最大迭代次數(shù)或者pg的適應(yīng)值已足夠好，算法結(jié)束；否則，k加1，返回第2)步。

3 實驗驗證

3.1 實驗設(shè)置

實驗采用三角形分類程序，并與文獻[21](利用遺傳算法和隨機測試方法)進行結(jié)果比較。

三角形分類程序通過分析輸入變量的取值及其相互關(guān)系，來判斷它們將組成何種三角形。三角形分類程序共有7個測試點，如表 2所示，設(shè)計測試用例6個，測試用例與測試點的關(guān)系如表3所示。

由于粒子群算法和遺傳算法都是啟發(fā)式方法，不能保證在任何情況下都能得到最優(yōu)解。為了檢驗算法的效果，從兩個方面進行考慮：首先是求得的最優(yōu)解的質(zhì)量，其次是最優(yōu)解的平均生成時間。

為了便于比較，分別采用APWC的兩種簡化變體APWC-1和APWC-2作為TCP-DPSO的適應(yīng)度函數(shù)，其中，APWC-1的簡化原則是令所有測試用例的綜合收益相同且綜合成本相等，即如果所有測試用例的綜合收益相同且綜合成本相等，APWC就簡化為APWC-1，等價于文獻[21]的APTC；APWC-2的簡化原則是假設(shè)每個測試點的重要程度及每個測試用例的成本不等，以單位測試成本覆蓋測試點的重要性程度值作為評價目標(biāo)，APWC-2等價于文獻[21]的APTC_C。

TCP-DPSO的主要參數(shù)配置如表4所示，其中Cmax=0.95，Cmin=0.35，ωmax=0.9，ωmin=0.4。

表2 三角形分類程序的測試點[21]

表3 三角形分類程序的測試點與測試用例的對應(yīng)關(guān)系[21]

表4 TCP-DPSO的主要參數(shù)配置

3.2 結(jié)果分析

TCP-DPSO求得的最優(yōu)序列及其與文獻[21]的比較如表5所示。

TCP-DPSO與遺傳算法(GA)[21]的最優(yōu)序列的平均求解時間如表6所示。運行環(huán)境為：IntelCore2Duo1.40GHz，2.94GB內(nèi)存、WindowsXP、Matlab。

由表5可見，在求解最優(yōu)序列的效果方面，TCP-DPSO與遺傳算法相當(dāng)，大幅優(yōu)于隨機測試。由表6可以得到，在求解最優(yōu)解即最優(yōu)測試序列的成功率方面，TCP-DPSO略優(yōu)于遺傳算法；而在平均求解時間上，TCP-DPSO也比遺傳算法要略優(yōu)，說明TCP-DPSO算法的穩(wěn)定性更好。

表5 不同方法最優(yōu)序列比較

表6 不同方法最優(yōu)序列平均求解時間比較

4 結(jié)語

測試用例優(yōu)先排序問題的實質(zhì)是找到一個測試用例序列，使得排序目標(biāo)達到最優(yōu)。粒子群優(yōu)化算法能夠有效減少測試用例排序過程中的盲目性，提高排序搜索的速度和效果，從而提高軟件測試效率。

TCP-DPSO算法基于群體進化思想，通過個體間協(xié)作和相互競爭來尋找最優(yōu)解，若粒子當(dāng)前位置比所經(jīng)歷過的最優(yōu)位置有更好的適應(yīng)度值，將替換其經(jīng)歷的最優(yōu)位置；粒子還能夠從全局最優(yōu)值中取得更新信息，使粒子不斷地向群體經(jīng)驗認可好的方向飛行；另外引入變異機制，避免陷于局部最優(yōu)，使得快速地達到或逼近優(yōu)化目標(biāo)。實驗數(shù)據(jù)表明，TCP-DPSO算法效果優(yōu)于遺傳算法和隨機測試。

利用智能優(yōu)化技術(shù)求解測試用例優(yōu)先排序、測試用例約簡、測試自動化生成等軟件測試中的熱門問題，是一個可行的技術(shù)方向，具有很好的研究價值。下一步將就粒子群算法、遺傳算法、蟻群算法、模擬退火等在軟件測試中的應(yīng)用作進一步的研究。

)

[1]AMMANNP,OFFUTTJ.IntroductiontoSoftwareTesting[M].Cambridge,UK:CambridgeUniversityPress, 2008: 9-10.

[2]ORSOA,ROTHERMELG.Softwaretesting:aresearchtravelogue(2000—2014) [C]//FOSE2014:ProceedingsoftheFutureofSoftwareEngineering.NewYork:ACM, 2014: 117-132.

[3]YOOS,HARMANM.Regressiontestingminimization,selectionandprioritization:asurvey[J].SoftwareTesting,Verification&Reliability, 2012, 22(2): 67-120.

[4]HARROLDM,ORSOA.Retestingsoftwareduringdevelopmentandmaintenance[C]//Proceedingsofthe2008FrontiersofSoftwareMaintenance.Piscataway,NJ:IEEE, 2008: 99-108.

[5] 陳翔,陳繼紅,鞠小林,等.回歸測試中的測試用例優(yōu)先排序技術(shù)述評[J].軟件學(xué)報,2013,24(8):1695-1712.(CHENX,CHENJH,JUXL,etal.Surveyoftestcaseprioritizationtechniquesforregressiontesting[J].JournalofSoftware, 2013, 24(8): 1695-1712.)

[6]WONGW,HORGANJ,LONDONS,etal.Astudyofeffectiveregressiontestinginpractice[C]//Proceedingsofthe1997InternationalSymposiumonSoftwareReliabilityEngineering.Piscataway,NJ:IEEE, 1997: 264-274.

[7]ELBAUMS,MALISHEVSKYAG,ROTHERMELG.Prioritizingtestcasesforregressiontesting[C]//Proceedingsofthe2000InternationalSymposiumonSoftwareTestingandAnalysis.NewYork:ACM, 2000: 102-112.

[8]ROTHERMELG,UNTCHRH,CHUC,etal.Testcaseprioritization:anempiricalstudy[C]//Proceedingsofthe1999InternationalConferenceonSoftwareMaintenance.Piscataway,NJ:IEEE, 1999: 179-188.

[9]EBERHARTRC,KENNEDYJ.Anewoptimizerusingparticlesswarmtheory[C]//ProceedingsoftheSixthInternationalSymposiumonMicroMachineandHumanScience.Piscataway,NJ:IEEE, 1995: 39-43.

[10]KENNEDYJ,EBERHARTR.Adiscretebinaryversionoftheparticleswarmoptimization[C]//Proceedingsofthe1997IEEEInternationalConferenceonNeuralNetworks.Piscataway,NJ:IEEE, 1997: 4104-4108.

[11]HUXH,EBERHARTRC,SHIYH.Swarmintelligenceforpermutationoptimization:acasestudyofn-queens problem [C]// Proceedings of the 2003 IEEE Swarm Intelligence Symposium.Piscataway, NJ: IEEE, 2003: 243-246.

[12] CLERC M.Discrete particle swarm optimization-illustrated by the traveling salesman problem [EB/OL].[2016-03-20].http://clerc.maurice.free.fr/pso/pso_tsp/Discrete_PSO_TSP.htm.

[13] 徐華,張庭.改進離散粒子群算法求解柔性流水車間調(diào)度問題[J].計算機應(yīng)用,2015,35(5):1342-1347.(XU H, ZHANG T.Improved discrete particle swarm algorithm for solving flexible flow shop scheduling problem [J].Journal of Computer Applications, 2015, 35(5): 1342-1347.)

[14] 蘇貝貝.基于粒子群算法的軟件測試用例優(yōu)先排序方法研究[D].重慶:重慶大學(xué),2012:13-41.(SU B B.Study on test case prioritization based on particle swarm optimization [D].Chongqing: Chongqing University, 2012: 13-41.)

[15] SRIKANTH H, WILLIAMS L, OSBORNE J.System test case prioritization of new and regression test cases [C]// Proceedings of the 2005 International Symposium on Empirical Software Engineering.Piscataway, NJ: IEEE, 2005: 64-73.

[16] 屈波,聶長海,徐寶文.基于測試用例設(shè)計信息的回歸測試優(yōu)先級算法[J].計算機學(xué)報,2008,31(3):431-439.(QU B, NIE C H, XU B W.Test case prioritization based on test suite design information [J].Chinese Journal of Computers, 2008, 31(3): 431-439.)

[17] ZHANG X F, NIE C H, XU B W, et al.Test case prioritization based on varying testing requirement priorities and test case costs [C]// Proceedings of the 2007 International Conference on Quality Software.Piscataway, NJ: IEEE, 2007: 15-24.

[18] KRISHNAMOORTHI R, SAHAAYA ARUL MARY S A.Factor oriented requirement coverage based system test case prioritization of new and regression test cases [J].Information and Software Technology, 2009, 51(4): 799-808.

[19] ELBAUM S, MALISHEVSKY A, ROTHERMEL G.Prioritizing test cases for regression testing [C]// Proceedings of the 2000 International Symposium on Software Testing and Analysis.New York: ACM, 2000: 102-112.

[20] LI Z, HARMAN M, HIERONS R M.Search algorithms for regression test case prioritization [J].IEEE Transactions on Software Engineering, 2007, 33(4): 225-237.

[21] 張衛(wèi)祥,魏波,杜會森.一種基于遺傳算法的測試用例優(yōu)先排序方法[J].小型微型計算機系統(tǒng),2015,36(9):1998-2002.(ZHANG W X, WEI B, DU H S.Test case prioritization method based on genetic algorithm [J].Journal of Chinese Computer Systems, 2015, 36(9): 1998-2002.)

[22] SHI Y, EBERHART R.Fuzzy adaptive particle swarm optimizer [C]// Proceedings of the 2001 IEEE International Congress on Evolutionary Computation.Piscataway, NJ: IEEE, 2001: 101-106.

This work is supported by the National Natural Science Foundation of China (61502015).

ZHANG Weixiang, born in 1979, M.S., engineer.His research interests include software testing, intelligent testing.

QI Yuhua, born in 1985, Ph.D., assistant researcher.His research interests include software testing, defect analysis and repair.

LI Dezhi, born in 1963, M.S., senior engineer.His research interests include software testing, software engineerization.

Test case prioritization based on discrete particle swarm optimization algorithm

ZHANG Weixiang1,2*, QI Yuhua1,2, LI Dezhi1,2

(1.BeijingInstituteofTrackingandTelecommunicationsTechnology,Beijing100094,China;2.CommitteeofSpacecraftTT&CTechnology,ChineseSocietyofAstronautics,Beijing100094,China)

With the ability to improve regression testing efficiency, test case prioritization has become a hot topic in software testing research.Since test case prioritization based on requirement is usually inefficient, a test case prioritization method based on discrete particle swarm optimization and test-point coverage, called Discrete Particle Swarm Optimization for Test Case Prioritization (TCP-DPSO) was proposed.Firstly, the various factors affecting prioritization were divided into two categories: Cost-Keys and Win-Keys, and then general test average yield index by normalizing was obtained.Then, particle’s position and velocity were defined by use of switcher and basic switching sequence, the mutation operator was introduced by referencing mutation strategy of Genetic Algorithm (GA), and the exploration and development capabilities were adjusted by adopting variable inertia weight, which could promote sustainable evolution and approach optimization goals.The experimental results show that TCP-DPSO is similar to GA and dramatically better than random testing on optimal solution quality and it is superior to GA on success rate and average computing time, which indicates its better algorithm stability.

software testing; test case prioritization; Discrete Particle Swarm Optimization (DPSO); evaluation index; functional testing

2016-08-24;

2016-09-04。 基金項目:國家自然科學(xué)基金資助項目(61502015)。

張衛(wèi)祥(1979—)，男，山東濟寧人，工程師，碩士，主要研究方向：軟件評測、智能化測試； 齊玉華(1985—)，男，河南睢縣人，助理研究員，博士，主要研究方向：軟件評測、缺陷分析與修復(fù)； 李德治(1963—)，男，河南偃師人，高級工程師，碩士，主要研究方向：軟件評測、軟件工程化。

1001-9081(2017)01-0108-06

10.11772/j.issn.1001-9081.2017.01.0108

TP311.5; TP181

A