基于Tent混沌的測(cè)試用例優(yōu)先級(jí)排序

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

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

0 引言

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

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

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

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

1.1 初始化優(yōu)化

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

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

改進(jìn)后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)

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

(5)

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

同時(shí)慣性權(quán)重ω采用常用的指數(shù)函數(shù)遞減法，用以匹配算法過(guò)程中的非線(xiàn)性變化特點(diǎn)：

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

(6)

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

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

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

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

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

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

(7)

步驟3：將m個(gè)混沌變量通過(guò)逆轉(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個(gè)混沌變量通過(guò)逆轉(zhuǎn)換，從區(qū)間[0,1]映射到粒子群算法的取值區(qū)間[a,b]，公式如下所示：

(10)

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

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

2.1 實(shí)數(shù)編碼

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

2.2 優(yōu)先級(jí)評(píng)價(jià)標(biāo)準(zhǔn)

測(cè)試用例優(yōu)先級(jí)技術(shù)(test case prioritization， TCP)是一個(gè)廣泛的研究熱點(diǎn)。該問(wèn)題可以描述為滿(mǎn)足下列公式:

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

(12)

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

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

(11)

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

3 實(shí)驗(yàn)仿真及結(jié)果分析

3.1 實(shí)驗(yàn)對(duì)象

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

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

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

表2 6個(gè)被測(cè)程序

3.2 實(shí)驗(yàn)結(jié)果分析

針對(duì)4個(gè)測(cè)試函數(shù)，本文采用標(biāo)準(zhǔn)粒子群優(yōu)化算法和TCPSO算法分別進(jìn)行了實(shí)驗(yàn)，評(píng)判標(biāo)準(zhǔn)為平均適應(yīng)度值的大小，如表3所示。

表3 各測(cè)試函數(shù)的平均適應(yīng)度值

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

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

圖1 PSO算法對(duì)應(yīng)的NAPFD

圖2 TCPSO算法對(duì)應(yīng)的NAPFD

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

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

4 結(jié)束語(yǔ)

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