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

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

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

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

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

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

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

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

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

1.1 基于需求的TCP問(wèn)題

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

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

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

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

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

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

(1)

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

1.2 評(píng)價(jià)指標(biāo)APWC

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

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

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

(2)

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

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

APWC公式化表示為：

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

表1 測(cè)試用例與測(cè)試點(diǎn)的對(duì)應(yīng)關(guān)系的一個(gè)實(shí)例

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

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

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

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

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

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

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

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

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

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

(4)

(5)

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

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

2.2.1 粒子群編碼

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

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

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

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

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

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

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

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

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

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

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

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

例如，對(duì)粒子位置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 乘法算子×。粒子速度(長(zhǎng)度為l的交換序列S)與實(shí)數(shù)α∈[0,1]的乘法運(yùn)算，其結(jié)果是對(duì)S的交換子隊(duì)列截?cái)喽纬傻拈L(zhǎng)度為α×l(取整)的新交換序列S′。

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

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

(6)

(7)

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

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

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

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

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

(8)

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

2.2.4 變異策略設(shè)計(jì)

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

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

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

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

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

2.3 TCP-DPSO算法基本流程

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

1)對(duì)粒子群進(jìn)行隨機(jī)初始化，給每個(gè)粒子賦予一個(gè)隨機(jī)的初始位置和一個(gè)隨機(jī)的交換序列。

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

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

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

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

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

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

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

3 實(shí)驗(yàn)驗(yàn)證

3.1 實(shí)驗(yàn)設(shè)置

實(shí)驗(yàn)采用三角形分類程序，并與文獻(xiàn)[21](利用遺傳算法和隨機(jī)測(cè)試方法)進(jìn)行結(jié)果比較。

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

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

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

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

表2 三角形分類程序的測(cè)試點(diǎn)[21]

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

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

3.2 結(jié)果分析

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

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

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

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

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

4 結(jié)語(yǔ)

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

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

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

)

[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] 陳翔,陳繼紅,鞠小林,等.回歸測(cè)試中的測(cè)試用例優(yōu)先排序技術(shù)述評(píng)[J].軟件學(xué)報(bào),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ìn)離散粒子群算法求解柔性流水車(chē)間調(diào)度問(wèn)題[J].計(jì)算機(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] 蘇貝貝.基于粒子群算法的軟件測(cè)試用例優(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] 屈波,聶長(zhǎng)海,徐寶文.基于測(cè)試用例設(shè)計(jì)信息的回歸測(cè)試優(yōu)先級(jí)算法[J].計(jì)算機(jī)學(xué)報(bào),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)祥,魏波,杜會(huì)森.一種基于遺傳算法的測(cè)試用例優(yōu)先排序方法[J].小型微型計(jì)算機(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。 基金項(xiàng)目:國(guó)家自然科學(xué)基金資助項(xiàng)目(61502015)。

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

1001-9081(2017)01-0108-06

10.11772/j.issn.1001-9081.2017.01.0108

TP311.5; TP181

A