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

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

0 引言

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

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

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

1 粒子群算法優(yōu)化

1.1 初始化優(yōu)化

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

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

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

(1)

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

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

xk+1=2(xk)mod

(2)

1.2 位置和速度更新

(3)

(4)

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

(5)

其中:A，B，C為常系數(shù)。

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

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

(6)

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

1.3 混沌優(yōu)化算法

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

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

最優(yōu)解取代的具體步驟如下所示：

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

(7)

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

公式如下所示：

(8)

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

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

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

(9)

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

(10)

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

2 基于混沌的測試用例優(yōu)先級排序

2.1 實數(shù)編碼

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

2.2 優(yōu)先級評價標準

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

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

(12)

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

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

(11)

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

3 實驗仿真及結(jié)果分析

3.1 實驗對象

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

表1 4種測試函數(shù)表

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

表2 6個被測程序

3.2 實驗結(jié)果分析

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

表3 各測試函數(shù)的平均適應度值

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

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

圖1 PSO算法對應的NAPFD

圖2 TCPSO算法對應的NAPFD

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

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

4 結(jié)束語

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