基于離散粒子群算法的測試用例優先排序

張衛祥，齊玉華，李德治

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

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

基于離散粒子群算法的測試用例優先排序

張衛祥1,2*，齊玉華1,2，李德治1,2

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

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

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

軟件測試；測試用例優先排序；離散粒子群優化；評價指標；黑盒測試

0 引言

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

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

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

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

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

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

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

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

2)提出基于需求的測試平均收益率評價指標，作為評估粒子位置優劣的適應度函數。

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

4)采用時變慣性權重，調整粒子的探索能力和開發能力。

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

1 測試用例優先排序問題描述

1.1 基于需求的TCP問題

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

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

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

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

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

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

(1)

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

1.2 評價指標APWC

與隨機測試相比，TCP技術的一個顯著優點是能夠更快地檢查出錯誤。基于此，Elbaum等[19]給出APFD(AveragePercentageofFaultDetection)評價指標,采用測試用例使用個數和檢測錯誤個數之間的關系來量化測試用例序列的優劣。當給定測試用例的執行次序時，可用APFD指標計算測試用例執行過程中檢測到缺陷的平均累計比例，但需要事先知曉測試用例的缺陷檢測信息。一般地，缺陷檢測信息在測試用例全部執行前是不可能知道的，所以APFD存在著明顯不足。

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

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

(2)

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

在這里，考慮到各因素對測試用例排序結果的影響，根據上節的分析，利用式(1)中的綜合收益和綜合成本對APTC進行改進。把評估目標調整為單位綜合成本取得的綜合收益，提出測試平均收益率評價指標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%，故執行次序2的效果優于執行次序1。圖 1中折線下方陰影面積占整個面積的比例即為各執行次序的APTC值。

表1 測試用例與測試點的對應關系的一個實例

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

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

圖1 不同測試用例序列對應的APTC值

圖2 不同測試用例序列對應的APWC值

2 基于離散粒子群優化的求解方法

本章給出求解TCP問題的離散粒子群優化(DPSO for TCP， TCP-DPSO)算法。首先介紹標準粒子群優化算法，隨后給出TCP-DPSO算法的實現原理和基本流程。

2.1 標準粒子群優化算法

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

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

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

(4)

(5)

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

2.2 TCP-DPSO算法實現原理

2.2.1 粒子群編碼

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

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

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

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

例如，粒子位置x經S作用后變為x″，即x″=x+S=x+(s1,s2,…,sl)=[(x+s1)+s2]+…+sl。

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

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

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

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

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

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

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

例如，對粒子位置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)與實數α∈[0,1]的乘法運算，其結果是對S的交換子隊列截斷而形成的長度為α×l(取整)的新交換序列S′。

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

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

(6)

(7)

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

2.2.3 慣性權重設計

慣性權重是粒子群優化算法的重要參數，常見的設置方法有固定權重、時變權重、模糊權重等。固定權重方法賦予慣性權重一個0和1之間的常數值，有實驗表明，群體規模越小需要的慣性權重越大，反之亦然。模糊權重方法使用模糊系統來動態調節慣性權重，例如Shi等[22]使用了具有9條規則、2個輸入和1個輸出的模糊系統。時變權重方法能使粒子群在初期具有較好的探索能力，而在后期具有較好的開發能力。

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

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

(8)

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

2.2.4 變異策略設計

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

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

2.2.5 適應度函數設計

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

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

2.3 TCP-DPSO算法基本流程

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

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

2)使用適應度函數Fitness計算每個粒子的適應度值。

3)比較每個粒子的當前適應值和自身歷史最優位置pi的適應值，如果當前值更優，則更新pi。

4)比較每個粒子的當前適應值和群體最優位置pg的適應值，如果當前值更優，則更新pg。

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

6)使用式(8)調整時變慣性權重ωk。

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

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

3 實驗驗證

3.1 實驗設置

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

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

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

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

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

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

表3 三角形分類程序的測試點與測試用例的對應關系[21]

表4 TCP-DPSO的主要參數配置

3.2 結果分析

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

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

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

表5 不同方法最優序列比較

表6 不同方法最優序列平均求解時間比較

4 結語

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

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

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

)

[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] 陳翔,陳繼紅,鞠小林,等.回歸測試中的測試用例優先排序技術述評[J].軟件學報,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] 徐華,張庭.改進離散粒子群算法求解柔性流水車間調度問題[J].計算機應用,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] 蘇貝貝.基于粒子群算法的軟件測試用例優先排序方法研究[D].重慶:重慶大學,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] 屈波,聶長海,徐寶文.基于測試用例設計信息的回歸測試優先級算法[J].計算機學報,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] 張衛祥,魏波,杜會森.一種基于遺傳算法的測試用例優先排序方法[J].小型微型計算機系統,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。 基金項目:國家自然科學基金資助項目(61502015)。

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

1001-9081(2017)01-0108-06

10.11772/j.issn.1001-9081.2017.01.0108

TP311.5; TP181

A