基于逐幸存路徑處理的測試用例集約簡技術

摘要：針對基于智能算法的測試用例集約簡技術存在的容易陷入局部收斂、過早熟等問題，提出一種基于逐幸存路徑處理的測試用例集約簡算法，該算法運用逐幸存路徑處理算法的順序網格搜索思路，將測試用例集進行二進制編碼，使其構成順序網格搜索的狀態空間，在狀態轉移階段將代碼覆蓋率和測試用例有效執行時間作為分支度量，進而選擇分支重量最大的路徑作為幸存路徑，從而剔除冗余狀態，完成測試用例集約簡。實驗結果表明，在相同的實驗環境下，與其他算法相比該算法在具有較高冗余率的同時也保證了較高的檢錯率，在一定程度上降低軟件測試的復雜度，提高軟件測試的效率。

關鍵詞：測試用例集約簡；逐幸存路徑處理；分支重量；代碼覆蓋率；冗余率；檢錯率

中圖分類號：TP311.56文獻標志碼：A文章編號：1001-3695（2023）01-035-0000-00

doi： 10.19734/j.issn.1001-3695.2022.05.0260

Test case reduction technology based on per-survivor processing algorithm

Huo Tingting， Sun Qiang， Ding Rui， Xia Chunyan

（College of Computer amp; Information Technology，Mudanjiang Normal University， Mudanjiang Heilongjiang 157000， China）

Abstract：

Aiming at the problems of test case reduction（TCR） technology based on intelligent algorithms that it is easy to fall into local convergence and premature maturity，this paper proposed a test case set reduction algorithm based on per-survivor processing（PSP）. The algorithm used the sequential grid search idea of PSP algorithm to binary code the test case set to form the state space of sequential grid search. In the state transition stage， the algorithm took the code coverage and the effective execution time of test cases as branch metrics. According to the calculation results， the path with the largest branch weight was the surviving path， so as to eliminate redundant states and complete the reduction of test case set. The experimental results show that under the same experimental environment， compared with other algorithms， this algorithm not only has higher redundancy rate（RR）， but also ensures higher error detection rate（EDR）. This algorithm reduces the complexity of software testing to a certain extent and improves the efficiency of software testing.

Key words：test case reduction; per-survivor processing; branch weight; code coverage; redundancy rate; error detection rate

0引言

回歸測試是一種重要的軟件測試方法，其目的是在程序有修改的情況下保證原有功能正常的一種測試策略和方法［1］。在很多實際的軟件項目中，由于每次軟件版本更新都會引入新的測試用例，加上之前的測試用例集，測試用例庫的規模在日益增加，引發回歸測試開銷的劇增，測試用例集優化技術應運而生。測試用例集優化技術大致可分為測試用例選擇［2］、測試用例優先級排序［3］和測試用例集約簡（test case reduction，TCR）三類。

測試用例集約簡的目的是對軟件開發過程中涉及到的所有測試用例進行有效的管理，去除冗余測試用例，找出一組在保證充分滿足所有測試需求的基礎上，數量少且運行代價最小的測試用例子集，使得在保證和提高軟件質量的同時，降低軟件測試的成本。在進行約簡時，約簡后的測試用例集必須要與原始測試用例集具有相同的覆蓋率，例如語句覆蓋率、分支覆蓋率、塊覆蓋率等。

Harrold等人［4］提出測試用例集約簡的概念，隨后研究人員又相繼提出多種用例集約簡技術，包括貪心算法、啟發式搜索算法和整數規劃等［5］。其中，文獻［6］提出一種基于螢火蟲算法的測試用例集約簡算法來提高算法的約簡能力和穩定性；文獻［7］中提出的貪心算法是一種用于尋找測試用例集問題的近似最優解的經典方法，但是該算法并不能盡早處理那些唯一可以覆蓋某寫測試需求的測試用例；文獻［8］提出了一種基于K均值的軟件測試用例集約簡算法，該算法通過盡可能的發現相似的用例，實現最小化約簡用例集的目的；文獻［9］提出了一種基于Memetic算法的測試用例集約簡算法，該算法對其中的全局策略和各算子以及局部策略進行了改進，Memetic 算法較標準遺傳算法的收斂速度更快、用例集更精簡，較大程度地降低了回歸測試的運行代價；文獻［10］提出了一種基于多種群協同粒子群算法的多目標測試用例優先排序算法來提高回歸測試效率。但是由于智能算法具有一定的隨機性，導致在對相同測試用例進行約簡時，可能會陷入局部收斂，無法達到最優值等問題［6］。

針對智能算法在對測試用例進行約簡時存在過早熟、搜索速度較慢、容易陷入局部最優等問題，本文提出一種基于逐幸存路徑處理的測試用例集約簡算法（test case reduction based on per-survivor processing algorithm，TCR_PSP），改進了一些群體智能算法存在的收斂速度較慢且容易陷入局部最優解等問題，從而加快了算法的收斂速度，提升了算法的全局搜索能力。該算法以冗余率（redundancy rate，RR）和檢錯率（error detection rate，EDR）作為度量準則，將語句塊覆蓋率（average percentage block coverage，APBC）和有效執行時間（effective execution time，EET）作為優化目標對回歸測試進行優化，并通過實驗對TCR_PSP算法的效果進行分析，同傳統的測試用例集約簡技術相比，TCR_PSP算法能夠在基本保證測試用例集檢錯率的情況下，進一步較大程度地減少回歸測試中的測試用例數量，降低無關測試用例的占比。

1多目標測試用例集約簡建模

一般情況下，測試用例對軟件的語句、分支、塊等的覆蓋率越大，該用例能夠發現軟件中存在缺陷的概率就越大。因此，為了能讓代碼覆蓋率較高且執行時間較短的測試用例優先執行，本文將平均語句塊覆蓋率作為優化目標，計算方法如式（1）所示。測試用例執行之前可以通過覆蓋率分析工具得到它的覆蓋率信息，所以APBC可以在測試用例全部執行之前使用，用來指導測試用例的優先排序。

APBC=1－TB1+TB2+…+TBi+…+TBmn×m+12n（1）

EET=∑nt=1ETt（2）

其中：n為測試用例的個數；m為這個序列發現錯誤個數； TBi表示為序列中第一個發現錯誤i∈［1，m］ 的測試用例位置編號；ETt為測試用例t的執行時間。

由于APBC是測試用例序列塊覆蓋率的平均值，值越大表示這個序列能盡早地達到更高的塊覆蓋率。如表1所示，其中A、B、C、D、E為測試用例，相應的行表示這個測試用例覆蓋的塊，“0”表示該用例未能覆蓋對應的程序塊，“1”表示該用例能覆蓋對應的程序塊。

假設測試用例序列Ts1=〈A-B-D-E-C〉，Ts2=〈E-A-C-D-B〉，其測試用例序列與塊覆蓋率之間的關系如圖1所示。測試用例序列Ts1=〈A-B-D-E-C〉執行完測試用例A后覆蓋了一塊，執行完B后一共覆蓋了三塊，依此類推。而測試用例序列Ts2=〈 E-A-C-D-B〉執行完測試用例E后覆蓋了三塊，執行完A后一共覆蓋了四塊，執行完C后即覆蓋了全部程序塊。每個測試用例分別都對應一個測試開銷，實際上這組測試用例是有冗余的，不考慮開銷的情況下，只需要〈A-E-C〉 便可以覆蓋全部測試點，因此另外2個便是需要約簡的冗余測試用例。

2基于逐幸存路徑處理算法的測試用例集約簡

2.1逐幸存路徑處理算法簡介

逐幸存路徑處理算法是由Raheli等人［11］在1993年提出的，該算法的基本思想是將未知參數的數據輔助估計嵌入到Viterbi算法本身的結構中，所以逐幸存路徑處理算法是基于卷積碼網格圖的最大似然序列估計（maximum likelihood sequence estimation，MLSE）算法［12］。

MLSE算法的過程就是根據接受序列，按最大似然譯碼準則找出編碼器在網格圖上所經過的路徑，這個過程也就是譯碼器計算、尋找最大似然函數式（3）的過程，也可以說是尋找有最大“度量” 的路徑的過程。

max Pi（R|Ci）i=1，2，…，m（3）

其中：m為編碼長度；R為觀測序列；Pi（R|Ci）為給定碼字Ci時R的似然函數。

對二進制對稱信道而言，尋找有最大度量的路徑，等價于尋找與R有最小漢明距離的路徑，即尋找

min di（R|Ci）i=1，2，…，m（4）

PSP算法正是在此基礎上所引入的一種最大似然譯碼算法，它并不是在網格圖上一次比較所有可能的m條路徑，而是接收一段，比較一段，選擇一段最可能的路徑，從而達到整個碼序列是一個有最大似然函數的序列。利用編碼網格圖的特殊結構，降低了計算的復雜性。該算法考慮的是，去除不可能成為最大似然選擇對象的網格圖上的路徑，即如果有兩條路徑到達同一狀態，則具有最佳度量的路徑被選中，稱為幸存路徑。對所有狀態都將進行這樣的選路操作，譯碼器不斷在網格圖上深入，通過去除可能性最小的路徑實現判決，較早地拋棄不可能的路徑降低了譯碼器的復雜性。

為了更具體的理解逐幸存路徑處理算法的過程，本文以（2，1，2） 卷積碼為例，為簡化討論，假設信道為二進制對稱信道。譯碼過程的前幾步如下：假定輸入數據序列m，碼字U，接收序列Z，如圖2所示［13］，并假設譯碼器確知網格圖的初始狀態。

由圖2可知，時刻t1接收到的碼元是11，從狀態00出發只有00和10兩種狀態轉移方向，其中狀態轉換的路徑度量是2和0。時刻t2從每個狀態出發都有兩種可能的分支，同樣地，時刻t3從每個狀態出發都有兩個分支，因此，各個時刻到達每個狀態的路徑都有兩條，這兩條路徑中，累積路徑度量較大的將被舍棄。如果這兩條路徑的路徑度量恰好相等，則任意舍棄其中一條路徑。因此這時譯碼器可以判決時刻t1和t2之間的狀態轉移是00→10。

2.2基于逐幸存路徑處理算法的測試用例集約簡

基于本文第1節及2.1節對于測試用例集約簡的分析，本文提出一種基于逐幸存路徑處理的測試用例集約簡算法（TCR_PSP）。TCR_PSP算法的測試用例集約簡主要包括兩個過程：狀態初始化和狀態轉移與更新，其執行過程如圖3所示。

首先，對測試用例集中的用例進行編碼，然后進行狀態初始化。狀態初始化過程主要計算已編碼的測試用例集中用例的漢明重量，選擇最大的一個作為初始狀態。然后開始狀態轉移和更新，此階段的主要目的是根據路徑度量和分支度量來選擇路徑。通過重復上述過程，直到分支度量達到最大值，然后進行回溯找到該路徑中的各個狀態就是約簡后的測試用例集。為了更加詳細地給出算法的實現過程，接下來給出TCR_PSP算法具體描述。

2.2.1測試用例編碼階段

本文算法采用二進制編碼的方式，假設測試用例集Ts中有n個測試用例，那么利用覆蓋率分析工具得到它的覆蓋率信息，本文將該用例可覆蓋代碼塊用“1”標記，將其不可覆蓋代碼塊用“0”進行標記，那么對于有Q個代碼塊的待測程序來說，其任意一個測試用例均可表示為一個二進制序列，例如表1給出的測試用例A本文可以將其表示為二進制{00010}，因此，測試用例集Ts中所有測試用例的全排列組合構成了順序網格搜索的狀態空間。

2.2.2確定初始狀態

接下來，本文利用漢明距離［5，12］相關理論來確定狀態空間的初始狀態。漢明距離是使用在數據傳輸差錯控制編碼里面的，它表示兩個（相同長度）字對應位不同的數量，本文以d（x，y）表示兩個字x，y之間的漢明距離。對兩個字符串進行異或運算，并統計結果為1的個數，那么這個數就是漢明距離。因此漢明距離的計算公式可表示為

d（x，y）=∑Q－1i=0［x（i）⊕y（i）］（5）

其中：i=0，1，…，Q-1，x，y都是Q位的編碼；x（i）表示取x的第i位碼字；⊕表示異或運算。

而漢明重量是字符串相對于同樣長度的“0”字符串的漢明距離，也就是說，它是字符串中非零的元素個數：對于二進制字符串來說，就是“1”的個數，所以11101的漢明重量是 4。那么，對于任意一個二進制編碼，本文可以將其漢明重量看做是該字符串與等長全“0”字符串的漢明距離，故漢明重量可以表示為

d（x）=∑Q－1i=0［x（i）⊕0］（6）

因此，測試用例集經過二進制編碼后，如果某一個測試用例自身覆蓋率較高，那么其漢明重量就相對較大，如表1中，d（A）=1，d（B）=2，d（C）=2，d（D）=1，d（E）=3，則測試用例E可覆蓋3個代碼塊，其二進制編碼為{11001}，其漢明重量為3。故本文可以以每個測試用例的漢明重量的大小為依據，選擇漢明重量最大者為該狀態空間的初始狀態。

2.2.3狀態轉移

初始狀態確立后開始進入狀態轉移階段，在該階段需要確立各節點的狀態。

a）各個節點的狀態為除去初始用例T0c的所有測試用例即{ Tic，i=1，…，n-1}，k時刻狀態轉移到i節點的路徑度量，記做lik（j），接下來用式（7）計算初始化路徑度量Ζi（j），式（8）計算進入狀態Tic的分支度量lik（j）。

Ζ0（j）=T0c（j），j=0，1，2，…，Q-1（7）

lik（j）=（Zk-1（j）Tic（j）），i=1，…，n-1，j=0，…，Q-1（8）

其中：n為測試用例的個數，m為這個序列發現錯誤個數，這里j=0，1，…m-1，Ζi－1和Tic都是m位的編碼，⊕表示異或運算。

為了衡量k時刻第i個分支的重要程度，本文引入分支重量lwik的概念，用它來表示此時各分支對代碼塊的覆蓋程度，lwik越大分支覆蓋的程序塊越多，即

lwik=∑Q-1j=0lik（j）（9）

b）比較分支重量lwik，i=1，…，n-1并選擇值最大的路徑作為幸存路徑，排除其他路徑，如果存在相等的路徑，則比較兩者ET的大小，此時取ET較小者為幸存路徑。

c）把k-1時刻路徑度量Ζk－1與連接該狀態支路的另一端節點的路徑度量相加，得到k-1時刻狀態轉移到k時刻的路徑度量，記作Ζk，因此

Ζk（j）=Zk-1（j）+Tic（j），wheremax（lik，i=1，…，n-1）（10）

Ζk（j）=1ifΖk（j）gt;1Ζk（j）elsej=0，…，Q－1（11）

為了衡量k時刻幸存路徑長度，本文引入路徑長度Ζlk的概念，用它來表示此時幸存路徑對代碼塊的整體覆蓋程度，Ζlk越大總路徑覆蓋的程序塊越多，即

Ζlk=∑Q－1j=0Ζk（j）（12）

當所有狀態Tic經步驟a）～c）后，每個狀態將只有一條幸存路徑，并保存路徑信息和路徑度量。

d）設路徑的記憶長度為NT。當Ζlklt;Q且NTlt;i－1時重復步驟a）～c）；當Ζlk=Q或NT≥i－1時，找出所有狀態中路徑度量最大的狀態Tic。

e）找到所有的幸存路徑，沿著路徑回溯，找到這條路徑的起點所對應的狀態Tci-NT+1，最終將回溯得到的所有狀態倒序輸出作為測試用例集約簡的結果。

2.3基于逐幸存路徑處理算法的測試用例集約簡分析

不失一般性，現以表1給出的5測試用例以及5個代碼塊覆蓋率信息對應表為例，在2.2.2小節確定初始狀態為E的基礎上，利用逐幸存路徑處理算法的順序網格對其進行約簡，如圖4所示，與表1相對應，可以證明理論上通過TCR_PSP算法是可以得到約簡后的測試用例集Ts=〈A-E-C〉。接下來，根據式（9）計算此時各狀態的分值重量，即lw11=4，lw21=1，lw31=3，lw41=2，根據計算結果本文選取E→A為幸存分支，此時路徑長度Ζl1=4，計算過程如圖5（a）所示。

第一次狀態轉移路徑確定后，接下來，按照此過程確定第二次狀態轉移路徑，其過程如圖6所示。此時lw12=1，lw22=4，lw32=3，因此本文選取狀態C為下一時刻狀態，故此時E→A→C為幸存路徑，根據式（10）～（12）計算此時路徑長度Ζl2=5，其過程如圖5（b）所示。因為Ζl2與程序的代碼塊數相等，此時塊覆蓋率為100%，故輸出總的路徑即最后約簡后的測試用例集E→A→C，達到了除去冗余用例B、D的目的，實現了用例約簡，且約簡率為40%。

從測試用例的代碼覆蓋率的角度來看，利用PSP算法的順序網格搜索思路，首先進行狀態初始化，此時根據編碼后測試用例的漢明重量進行選擇，此時選擇出的初始測試用例E為塊覆蓋率最大者，而在進行狀態轉移過程中，如果出現分支度量相等情況選擇ET較小者為幸存路徑，從而綜合考慮APBC和EET兩個優化目標。

3實驗結果與分析

為驗證TCR_PSP算法的有效性和適用性，本文的實驗是在Intel CoreTM i5-1035G1，CPU @ 1.00 GHz，1.19 GHz，Windows 11操作系統的機器上進行的，算法實現使用的是Java語言。

3.1實驗數據集

實驗過程中，從軟件基礎庫（software-artifact infrastructure repository，SIR）（https：//sir.csc.ncsu.edu/content/sir.php）中選擇了5個來自不同的應用領域Java程序作為實驗對象，表2出了它們的基本信息。對于每個目標程序，有１個無錯誤版本和一些含有錯誤的版本，本文使用自動化的 JUnit測試用例生成工具Randoop［14］生成了大量的隨機測試用例。

3.2評價標準

為了對TCR_PSP算法的約簡效果進行定量檢驗，在實驗過程中，本文采用冗余率和檢錯率這兩個指標來評價實驗結果，以驗證算法的可行性和有效性。

3.2.1冗余率

冗余率計算如式（13）所示，它指的是軟件測試用例集中的原有測試用例數減去約簡后測試用例集中剩余用例數與軟件測試用例集中原有測試用例數的比值。

Rredundancy=|Ninitial|－|Nsurplus||Ninitial|×100%（13）

其中：|·|表示集合的大小；Rredundancy表示冗余率；|Ninitial|為軟件測試用例集中的原有測試用例數；|Nsurplus|為約簡后測試用例集中剩余用例數。事實上，一個有效的測試用例約簡技術應該有一個高的冗余率，冗余率越高，約簡后的測試用例集中剩余用例數越少，約簡率越高［8］。

3.2.2檢錯率

檢錯率指的是執行約簡后測試用例集中剩余用例后檢測到的程序代碼錯誤個數與實際程序代碼錯誤個數的比值［15］。

Rdetection=|Dsurplus||Dtotal|×100%（14）

其中：Rdetection為檢錯率；|Dtotal|表示程序代碼缺陷總數；|Dsurplus|表示執行剩余測試用例后檢測到的程序代碼錯誤個數。

3.3實驗驗證及分析

為了驗證本文提出的基于逐幸存路徑處理算法的測試用例集約簡（TCR_PSP）算法的性能，本文復原了文獻［6］中的螢火蟲（TCR_Firefly）算法、文獻［7］中的貪心（TCR_Greedy）算法、文獻［8］中K均值（TCR_Kmeans）算法和文獻［9］中提出的Memetic算法（TCR_Memetic）與本文TCR_PSP算法進行對比實驗。

在實驗過程中，本文取20次實驗運行結果的平均值，各算法約簡后剩余用例數如表3所示，根據式（13）冗余率計算公式得出各算法的平均冗余率箱線圖，如圖7所示，由圖可以看出，TCR_PSP算法的平均冗余率為43.4%，說明本文算法與其他其他算法相比能夠更加有效的減少測試用例數目，可以在一定程度上降低軟件測試的復雜度，提高軟件測試的效率。

事實上，衡量測試用例約簡算法的效果還需要考慮到約簡后用例集的檢錯率。為此，本文在使用以上五種算法完成對用例的約簡后，為了驗證剩余用例的錯誤檢測率，本文使用剩余用例進行測試，測試后各算法檢測出的錯誤個數如表4所示，根據式（14）錯誤檢測率計算公式得出各算法的平均檢錯率箱線圖，如圖8所示，由圖可以看出，TCR_PSP算法的平均錯誤檢測率為92%，說明本文算法與其他其他算法相比在有效的減少測試用例數目的同時可以保證較高的錯誤檢測率，可以提高軟件測試的可靠性。

此外，算法執行測試用例約簡耗費的時間資源也是影響該算法有效性的一個重要因素。為此，本文在使用以上五種算法對用例進行約簡的過程中記錄算法的運行時間并得到各個算法的運行時間的平均值如圖9所示。由圖9可知，在相同實驗條件下，本文的TCR_PSP算法進行用例集約簡的平均運行時間低于與之對比的其他算法，在一定程度上縮減了算法的運行時間，從另一個側面驗證了本文算法的有效性。

最后，執行測試用例約簡時算法的收斂速度是影響各個算法有效性的至關重要的因素。為此，本文在使用以上五種算法對程序P5的用例集進行約簡并記錄各算法達到最終約簡后剩余用例數的運行時間并計算出其均值如圖10所示。由圖10可知，在相同實驗條件下，本文的TCR_PSP算法進行用例集約簡的收斂速度快于與之對比的其他算法，在一定程度上避免了進化算法存在的收斂速度較慢且容易陷入局部最優解等問題，從而驗證了本文算法的有效性。

4結束語

本文針對基于智能算法的測試用例集約簡存在的容易陷入局部收斂、過早熟的等問題，提出了一種基于逐幸存路徑處理技術的測試用例集約簡算法。該算法在一定程度上避免了進化算法存在的收斂速度較慢且容易陷入局部最優解等問題，從而加快了算法的收斂速度，提升了算法的全局搜索能力。最后，通過對五種不同測試用例集約簡算法的比較分析可以看出，TCR_PSP算法在具有高冗余率的同時也保證了較好的檢錯率，實驗證明了該算法能夠高效率、高質量地完成對測試用例集的約簡，然而本文僅僅是從對現有的測試用例集進行約簡的角度出發而進行研究的，并未考慮在變異測試環境下本算法的效率，因此后續的研究中，可以考慮能否將TCR_PSP算法應用到變異測試技術中，以達到減少變異體的數量、降低變異測試時間成本的目的。

參考文獻：

［1］Kim J，Porter A. A history-based test prioritization technique for regression testing in resource constrained environments ［C］// Proc of the 24th International Conference on Software Engineering. Piscataway，NJ： IEEE Press，2002： 119-129.

［2］Yoo S，Harman M. Pareto efficient multi-objective test case selection ［C］// Proc of International Symposium on Software Testing amp; Analysis. New York： ACM Press，2007： 140-150.

［3］張衛祥，齊玉華，李德治. 基于離散粒子群算法的測試用例優先排序［J］. 計算機應用，2017，37（1）： 108-113，169.（Zhang Weixiang，Qi Yuhua，Li Dezhi. Test case prioritization based on discrete particle swarm optimization ［J］. Journal of Computer Applications，2017，37（1）： 108-113，169）

［4］Harrold M J，Gupta R，Soffa M L. A methodology for controlling the size of a test suite ［C］//Proc of Conference on Software Maintenance. Los Alamitos，CA： IEEE Computer Society，1990： 302-310.

［5］丁蕊，董紅斌，張巖，等. 基于關鍵點路徑的快速測試用例自動生成方法 ［J］. 軟件學報，2016，27（4）： 814-827.（Ding Rui，Dong Hongbin，Zhang Yan，et al. Automatic generation method of fast test cases based on key point path ［J］. Journal of Software，2016，27（4）： 814-827.）

［6］宮云戰，徐健豪，邢穎. 螢火蟲算法在測試用例集約簡中的應用 ［J］. 哈爾濱工程大學學報，2020，41（4）： 577-582.（Gong Yunzhan，Xu Jianhao，Xing Ying. Application of firefly algorithm in test case set reduction ［J］. Journal of Harbin Engineering University，2020，41（4）： 577-582.）

［7］Lin Chuti，Tang Kaiwei，Wang Jiunshiang，et al. Empirically evaluating greedy-based test suite reduction methods at different levels of test suite complexity ［J］. Science of Computer Programming，2017，150： 1-25.

［8］高丑光，林都，鮮浩. 基于K均值的軟件測試集用例約簡算法研究 ［J］. 微電子學與計算機，2016，33（5）： 133-136，141.（Gao Chouguang，Lin Du，Xian Hao. Research on case reduction algorithm of software test set based on K-means ［J］. Microelectronics and Computer，2016，33（5）： 133-136，141.）

［9］楊祎巍，匡曉云，黃開天，等. 基于Memetic算法的仿真用例集約簡技術 ［J］. 浙江大學學報： 理學版，2021，48（3）： 331-337.（Yang Yiwei，Kuang Xiaoyun，Huang Kaitian，et al. Simulation case set reduction technology based on memetic algorithm ［J］. Journal of Zhejiang University： Science Edition，2021，48（3）： 331-337.）

［10］Wang Hongman，Li Jinzhong，Xing Ying，et al. Multi-objective test case prioritization based on multi-population cooperative particle swarm optimization ［J］. The Journal of China Universities of Posts and Telecommunications，2020（1）： 38-50.

［11］Raheli R，Polydoros A，Tzou C K. Per-survivor processing ［J］. Digital Signal Processing，1993，3（3）： 175-187.

［12］Jr Forney G. Maximum-likelihood sequence estimation of digital sequences in the presence of intersymbol interference ［J］. IEEE Trans on Information Theory，2003，18（3）： 363-378.

［13］簡藝恒，余嘯. 基于數據過采樣和集成學習的軟件缺陷數目預測方法 ［J］. 計算機應用，2018，38（9）： 2637-2643，2659.（Jian Yiheng，Yu Xiao. Software defect number prediction method based on data oversampling and ensemble learning ［J］. Journal of Computer Applications，2018，38（9）： 2637-2643，2659.）

［14］薛義生，朱雪龍. 基于逐幸存路徑處理的空時格形碼自適應解碼器 ［J］. 電子學報，2001，29（10）： 1352-1355.（Xue Yisheng，Zhu Xuelong. Adaptive space-time trellis code decoder based on survival path processing ［J］. Acta Electronica Sinica，2001，29（10）： 1352-1355.）

［15］陳夢涵，郭躬德，林崧. 基于漢明距離的量子推薦算法 ［J］. 量子電子學報，2021，38（3）： 332-340.（Chen Menghan，Guo Gongde，Lin Song. Quantum recommendation algorithm based on Hamming distance ［J］. Journal of Quantum Electronics，2021，38（3）： 332-340.）

［16］Pacheco C，Ernst M D. Randoop： feedback-directed random testing for Java ［C］// Companion to the 22nd ACM SIGPLAN Conference on Object-Oriented Programming Systems and Applications Companion. New York： ACM Press，2007： 815-816.

［17］丁蕊，董紅斌，馮憲彬，等. 基于煙花爆炸優化算法的測試數據生成方法 ［J］. 計算機應用，2016，36（10）： 2816-2821.（Ding Rui，Dong Hongbin，Feng Xianbin，et al. Method for testing data generation based on fireworks explosion optimization algorithm ［J］. Journal of Computer Applications，2016，36（10）： 2816-2821）

收稿日期：2022-05-27；修回日期：2022-07-26基金項目：黑龍江省自然科學基金資助項目（LH2020F038）；黑龍江省省屬高等學校基本科研業務費資助項目（1353ZD004）；牡丹江師范學院科研項目（1451TD003）

作者簡介：霍婷婷（1991-），女，黑龍江蘭西人，講師，碩士研究生，主要研究方向為軟件測試、盲分離、智能算法及其應用；孫強（1979-），男（通信作者），河北承德人，教授，碩導，博士研究生，主要研究方向為電子設計自動化、計算機專業教學（huotingtingscu@163.com）；丁蕊（1977-），女，遼寧鳳城人，副教授，碩導，博士研究生，主要研究方向為基于搜索的軟件工程，群智計算，無人集群，多目標優化；夏春艷（1980-），女，黑龍江省樺川人，副教授，碩士研究生，主要研究方向為軟件測試、數據挖掘.