基于Tent混沌的測試用例優先級排序

張 娜,滕賽娜,吳 彪2,包曉安

(1.浙江理工大學 信息學院, 杭州 310018； 2.山口大學 東亞研究科,日本 山口 753-8514)

0 引言

回歸測試是指對修改后的代碼進行重復測試，確認未產生新的缺陷。在軟件開發過程中，頻繁使用回歸測試可以確保軟件的質量，所以降低回歸測試的成本是重中之重，而生成后的測試用例集進行排序或優化[1]是一種非常有效的方法。近年來，智能搜索算法也開始被應用于解決測試用例排序問題，如粒子群算法[2]、蜂群算法等。

目前，在已有的研究中，Yu等人[3]將軟件轉換為類級有向網絡模型，通過杠鈴模型的風險值作為排序依據，從而提高錯誤檢出率。Zhang等人[4]通過關注三個影響因子(需求覆蓋率、測試用例失效率、測試用例重要度)，動態調整測試同理優先級。Chang等人[5]基于歷史信息和動態調整策略，改進測試用例優先級技術以盡早地發現缺陷。Meng等人[6]將混沌融入粒子群中，當最優粒子與普通粒子的距離小于某值時，進行混沌搜索。Zhang等人[7]將OTT策略和粒子群相結合，在測試用例重要度和失效率上具有一定優勢。Zhu[8]在測試用例優先級排序中引入了缺陷影響因素，通過實驗證明其可以有效保證軟件產品的質量。Xu等人[9]提出粒子可以通過在混沌與穩定之間的交替運動,從而得到最優解，以跳出局部最優。Wang等人[10]通過定義失效覆蓋等價劃分優化選擇準則來提高錯誤定位的有效性，不同的測試同理賦予不同優先級。Zheng等人[11]根據函數調用關系圖進行關聯性分析并對測試用例排序，大大減少了回歸測試的成本。

結合上述研究，本文對PSO進行改進，結合了混沌算法的思想，提出了基于Tent混沌的粒子群優化算法(Tent-Chaos Particle Swarm Optimization，TCPSO)。對Tent映射引入參數，防止粒子落入小周期內，并引入帶有權重函數的學習因子，兩者相結合進行非線性遞減變化，平衡TCPSO算法全局與局部能力，其次，對陷入局部最優的粒子及部分最差粒子進行混沌搜索優化，保證種群多樣性，同時跳出局部最優，最后，以測試用例缺陷檢測率作為排序的評判標準進行實驗，并驗證算法具有較好的尋優能力。

1 粒子群算法優化

1.1 初始化優化

在標準粒子群的初始化中，解的質量對最終結果有著重要影響，種群的速度和位置信息一般隨機產生，它可以使得初始種群均勻分布，由于部分粒子可能會遠離最優解，所以粒子的質量不能完全保證，從而影響算法收斂速度和最終結果。

利用混沌序列本身具有的規律性，隨機性及遍歷性三大特性對粒子進行初始化優化，既能保持種群多樣性，同時利于跳出局部最優，改善PSO算法的全局搜索能力。映射算法一般有四種，被引用最多的為Logistic和Tent[12]兩種，Dan等人[13]指出在[0，1]區間內，Tent映射產生的混沌序列與Logistic映射產生的混沌序列相比分布更均勻，所以本文在種群初始化中引入Tent混沌映射算法，并對Tent方程進行改進，以提高初始解質量。

改進后Tent映射的迭代公式如下：

(1)

其中：xk為粒子的位置信息，K為粒子的迭代次數，α，β為調度參數，取值范圍[-0.1，0.1]，其作用是避免粒子落入小周期內。

Tent映射經貝努利移位變換后的公式如下所示：

xk+1=2(xk)mod

(2)

1.2 位置和速度更新

(3)

(4)

將學習因子與慣性權重相結合,兩者進行相關聯的非線性遞減變化，公式如下所示：

(5)

其中:A，B，C為常系數。

同時慣性權重ω采用常用的指數函數遞減法，用以匹配算法過程中的非線性變化特點：

ω=ωmin+(ωmax-ωmin)×exp[-20(t/T)6]

(6)

在本文提出的TCPSO中，隨著每一維位置與速度信息的更新，均計算個體歷史最優pid和種群全局最優pgd，而非所有維度的位置和速度信息更新完畢后，再計算pid和pgd。

1.3 混沌優化算法

混沌運動有三大特點：1)隨機性，混沌類似于隨機，因而具有隨機性；2)遍歷性，在一定范圍之內，混沌能夠使粒子不重復經歷任何一種狀態；3)規律性，雖然混沌類似于隨機，但是混沌本身也有一定的規律。因此，通過混沌運動，種群在跳出局部最優的同時也能尋找全局最優。

當粒子經過幾次迭代后，少數優秀粒子被保存下來，此時，粒子容易陷入局部最優，所以為了跳出局部最優，保證種群多樣性，本文引入了混沌搜索進行優化。首先分別以當前粒子的最優解pid和最差的百分之20的粒子piw為基礎，進行混沌搜索，產生與之對應的混沌序列，然后，以pid為基礎產生的混沌序列中的最優解代替原粒子的最優解pid，以piw為基礎產生的混沌序列中的粒子代替原粒子中最差的百分之20。

最優解取代的具體步驟如下所示：

步驟1：利用以下公式將最優解pid的變量取值范圍[a,b]映射到混沌算法的區間[0,1]

(7)

步驟3：將m個混沌變量通過逆轉換，從區間[0,1]映射到粒子群算法的取值區間[a,b]

公式如下所示：

(8)

步驟4：將混沌序列中的最優解取代原粒子群算法得到最優解pid。

最差的百分之20的粒子piw的具體步驟如下所示：

步驟1：利用以下公式將最差的百分之20的粒子piw的變量取值范圍[a,b]映射到混沌算法的區間[0,1]。

(9)

步驟3：將k個混沌變量通過逆轉換，從區間[0,1]映射到粒子群算法的取值區間[a,b]，公式如下所示：

(10)

步驟4：將混沌序列中的粒子取代原粒子群算法得到的最差的百分之20的粒子piw。

2 基于混沌的測試用例優先級排序

2.1 實數編碼

測試用例排序是指對測試用例集TS中的測試用例進行排序，通過判斷最終找到一個最優的排列，降低測試成本，能更早發現程序中的錯誤。本文通過實數編碼表示測試用例集中每個測試用例的序號。假設測試用例集TS中有M個測試用例，那么TS的任意一個序列可用粒子X=(xt1,xt2,…,xtm)表示，其中tm表示測試用例集 TS中第m個測試用例，xtm表示測試用例tm在測試用例集TS中的序號，且1≤xt≤M。

2.2 優先級評價標準

測試用例優先級技術(test case prioritization， TCP)是一個廣泛的研究熱點。該問題可以描述為滿足下列公式:

(?T″)(T″∈PT)(T″≠T′)[f(PT′)≥f(PT″)]

(12)

其中:T為測試用例集，PT為測試用例集中所有的可能的排列組合，f為目標函數。

適應度函數用以引導搜索算法的搜索方向，它決定了搜索算法能否快速有效地找到全局最優解，同時粒子的適應度值反應了該粒子是否為優質解，本文目的在于對測試用例進行優先級排序，減少回歸測試成本，盡早發現缺陷，所以采用標準化的測試用例程序度量標準(normalized average of the percentage of faults detected，NAPFD)計算缺陷檢測率，該標準用于衡量測試用例的優先級，公式如下所示：

(11)

其中:n表示測試用例集中參與測試的測試用例個數，m表示缺陷個數，p是n中缺陷個數與候選測試用例集T中缺陷個數的比率，TFi(1≤i≤m)表示檢測出第i個缺陷需要運行的測試用例個數。通過公式可以得出，當NAPFD的值越大，則發現錯誤的速度越快。

3 實驗仿真及結果分析

3.1 實驗對象

實驗使用 Matlab2012a實現，基本參數設置如下：最大迭代次數K=1 000，種群規模為K=30，c2,c1參考前文所寫公式(5)，ω參考前文所寫公式(6)，Ω∈[0.4,0.9]，為了避免隨機性帶來的影響，每組實驗運行100次。本文采用了四種典型測試函數驗證TCPSO算法的性能，并將結果與表粒子群算法進行對比，4種測試函數如表1所示。

表1 4種測試函數表

其中函數F1函數為Sphere，F2函數為Rosenbrock,F3函數為Rastrigrin，F4函數為Griewank。為驗證本文提出的TCPSO算法在測試用例排序上的有效性，本文對6個不同類型的程序進行實驗，并與標準粒子群算法進行結果對比，從缺陷檢測率角度進行評價，程序相關信息如表2所示。

表2 6個被測程序

3.2 實驗結果分析

針對4個測試函數，本文采用標準粒子群優化算法和TCPSO算法分別進行了實驗，評判標準為平均適應度值的大小，如表3所示。

表3 各測試函數的平均適應度值

從表3中可以看出，本文提出的TCPSO算法得到的函數值明顯優于標準粒子群算法，搜索精度提高了5倍以上，普遍在10倍左右，其中改進后的粒子群算法在f4函數上取得了最好的優化結果，將精度提高了近20倍。實驗結果表明，TCPSO算法的適用范圍廣泛，全局和局部搜索能力得到提高。

本文對標準粒子群優化算法和TCPSO算法分別通過表1中的 6個被測程序進行了測試用例排序實驗。對于程序Print_tokens和Schedule，由于兩者的測試用例較多，所以均勻地從中隨機選取了56和75個測試用例用于排序實驗。通過計算6個被測程序排序后的最優排列的NAPFD，以上實驗進行100次，由于實驗次數較多，所以實驗結果用箱形圖形式展現，便于整體觀察分析，箱形圖如圖1～2所示。

圖1 PSO算法對應的NAPFD

圖2 TCPSO算法對應的NAPFD

通過圖1和2的箱形圖對比可知，TCPSO算法在缺陷檢測率上明顯優于標準粒子群算法，其中對于Schedule程序而言，優化程度是最高的，NAPFD將近提高百分之二十五，但對于tokens程序而已，缺陷檢測率提高并不明顯，兩種算法的NAPFD相近，其余算法的缺陷檢測率提高程度近似；count程序在PSO算法的應用中，NAPFD數值波動較大，而在TCPSO算法的應用中，較為均衡。

通過兩個實驗結果表明，基于Tent混沌的粒子群算法在測試用例排序問題上效果顯著，在粒子尋優能力與測試用例缺陷檢測率兩個指標上均有優勢。

4 結束語

本文將粒子群算法與混沌算法相結合，應用于測試用例排序研究中。對Tent映射添加參數，使粒子避免落入小周期內，提高了初始種群質量；學習因子與慣性權重相結合，進行非線性遞減變化，用以平衡算法；對陷入局部最優和部分最差粒子進行混沌搜索優化，以跳出局部最優同時保證種群多樣性。在實驗部分，通過4種典型測試函數和6個被測程序對優先級排序進行驗證，結果表明在粒子尋優能力和測試用例缺陷檢測率上有優勢。本實驗用到的程序并非大型程序，如何對大型的程序進行測試用例優先級排序是進一步的研究問題。