融入蛻變關(guān)系的雜交粒子群算法及在測(cè)試數(shù)據(jù)生成中的應(yīng)用

焦重陽(yáng),周清雷

1(中國(guó)人民解放軍戰(zhàn)略支援部隊(duì)信息工程大學(xué),鄭州 450001) 2(數(shù)學(xué)工程與先進(jìn)計(jì)算國(guó)家重點(diǎn)實(shí)驗(yàn)室,鄭州 450001) 3(河南信息工程學(xué)校,鄭州 450000) 4(鄭州大學(xué) 信息工程學(xué)院,鄭州 450001)

1 引 言

軟件測(cè)試用于發(fā)現(xiàn)和糾正軟件中存在的錯(cuò)誤和缺陷,是軟件開發(fā)過(guò)程中一個(gè)必不可少的質(zhì)量保證和驗(yàn)證的環(huán)節(jié).美國(guó)國(guó)家標(biāo)準(zhǔn)與技術(shù)研究所的報(bào)告指出,軟件測(cè)試可以減少超過(guò)三分之一的軟件故障成本[1].但是,軟件測(cè)試是一項(xiàng)耗時(shí)耗力的工作,它大約消耗了軟件開發(fā)成本的50%[2].在軟件測(cè)試中有著兩個(gè)基本問(wèn)題:oracle問(wèn)題和可靠測(cè)試集問(wèn)題[3].為緩解oracle問(wèn)題,蛻變測(cè)試(Metamorphic Testing,MT)是一種有效的方法,越來(lái)越受到研究者們的關(guān)注,并檢測(cè)出了大量的現(xiàn)實(shí)故障.蛻變測(cè)試的中心是一系列的蛻變關(guān)系(Metamorphic Relations,MR),這是目標(biāo)函數(shù)在多個(gè)輸入和它的預(yù)期輸出方面的必要屬性.在蛻變測(cè)試中,一些程序輸入(源輸入,Source Input)首先被生成為源測(cè)試用例,利用蛻變關(guān)系可以生成衍生輸入(Follow-up Input)成為后續(xù)的測(cè)試用例.有效的測(cè)試數(shù)據(jù)可以發(fā)現(xiàn)軟件中存在的錯(cuò)誤,由于軟件測(cè)試數(shù)據(jù)的設(shè)計(jì)和生成是非常耗時(shí)和錯(cuò)誤率高的,如何有效快速的自動(dòng)生成測(cè)試數(shù)據(jù)成為軟件測(cè)試中研究的一個(gè)熱點(diǎn).多年來(lái),為了解決可靠測(cè)試集的問(wèn)題,許多研究者提出了不同的方法來(lái)自動(dòng)生成測(cè)試數(shù)據(jù).其中,基于搜索的軟件測(cè)試(Search Based Software Testing,SBST)[4]方法具有自動(dòng)化、智能化、高效等優(yōu)點(diǎn),引起了廣大學(xué)者們的關(guān)注和研究.

粒子群算法作為一種群體智能搜索算法,因算法規(guī)則簡(jiǎn)單、容易實(shí)現(xiàn)、收斂速度快以及可調(diào)節(jié)參數(shù)少等優(yōu)勢(shì),在工程應(yīng)用中頗為廣泛.目前,將粒子群算法應(yīng)用于測(cè)試數(shù)據(jù)自動(dòng)生成中已有很多的研究,如張娜等[5]提出了一種基于反向?qū)W習(xí)與再次搜索的粒子群優(yōu)化算法用于測(cè)試用例生成;Sahoo等[6]提出了一種新的適應(yīng)度函數(shù)計(jì)算方法,通過(guò)覆蓋關(guān)鍵路徑生成測(cè)試用例實(shí)現(xiàn)最大的路徑覆蓋;董躍華等[7]提出了一種基于離散度大小的動(dòng)態(tài)調(diào)整粒子群參數(shù)的優(yōu)化算法并將該算法應(yīng)用于測(cè)試數(shù)據(jù)生成.Wang等[8]為了提高PSO的性能,提出了一種改進(jìn)的PSO生成測(cè)試用例;Molaei等[9]將遺傳算法與粒子群算法相結(jié)合,提出了基于增強(qiáng)學(xué)習(xí)策略引導(dǎo)粒子群的學(xué)習(xí),采用交叉操作將粒子群變異,該算法在精度方面和收斂速度方面具有更大的優(yōu)勢(shì).

以上研究中針對(duì)提高目標(biāo)路徑的測(cè)試數(shù)據(jù)生成的效率做了很多研究,但都不涉及程序自身的固有屬性,本文利用待測(cè)程序的自身性質(zhì)構(gòu)造出程序的蛻變關(guān)系,提出了融入蛻變關(guān)系的雜交粒子群算法(Hybrid Particle Swarm Optimization Algorithm With Metamorphic Relations,MRHPSO),找出覆蓋多條路徑的測(cè)試數(shù)據(jù),進(jìn)一步提高了測(cè)試數(shù)據(jù)生成的效率.本文為提高算法的進(jìn)化速度,提出了自適應(yīng)的慣性權(quán)重的調(diào)節(jié)方案,即根據(jù)全局最優(yōu)點(diǎn)的距離進(jìn)行動(dòng)態(tài)調(diào)整;為避免粒子群算法陷入局部極值,呈現(xiàn)早熟性,將遺傳算法的雜交思想引入粒子群算法中,提出了雜交粒子群算法;為找到多條路徑覆蓋的測(cè)試數(shù)據(jù),融入待測(cè)程序的蛻變關(guān)系.后續(xù)的測(cè)試數(shù)據(jù)能夠利用待測(cè)程序的蛻變關(guān)系生成,節(jié)省了大量的測(cè)試時(shí)間.通過(guò)實(shí)驗(yàn)結(jié)果表明,本文所提出的方法在收斂速度和生成多路徑的測(cè)試數(shù)據(jù)上有明顯優(yōu)勢(shì).

2 標(biāo)準(zhǔn)粒子群算法

(1)

(2)

其中,w為慣性權(quán)重;c1和c2為學(xué)習(xí)因子,也稱加速常數(shù),代表粒子向優(yōu)秀個(gè)體學(xué)習(xí)能力的大小;r1和r2為介于0和1之間的均勻隨機(jī)數(shù),增加了粒子飛行的隨機(jī)性.

從公式(1)可以看出,粒子的移動(dòng)速度是在三方面的共同作用下進(jìn)行迭代更新的.第1部分代表粒子的慣性功能,表示前一次速度值對(duì)當(dāng)前速度的影響;第2部分代表粒子的自身認(rèn)知功能,根據(jù)自身的經(jīng)驗(yàn)進(jìn)行學(xué)習(xí);第3部分代表粒子的社會(huì)學(xué)習(xí)功能,粒子向整個(gè)種群中的最優(yōu)粒子學(xué)習(xí),反映了粒子間的協(xié)同合作和知識(shí)共享.

3 MRHPSO算法及在測(cè)試數(shù)據(jù)生成中的應(yīng)用

3.1 慣性權(quán)重w的自適應(yīng)調(diào)節(jié)方案

慣性權(quán)重是指粒子能保持前一時(shí)刻運(yùn)動(dòng)狀態(tài)的能力,設(shè)計(jì)良好的慣性權(quán)重能推動(dòng)粒子在合適的時(shí)機(jī)進(jìn)行適當(dāng)?shù)奶剿?并在整體上保持前期搜索速度較快,后期搜索速度較為緩慢的節(jié)奏.從粒子更新公式可以看出,慣性權(quán)重值越大,算法的全局搜索能力越強(qiáng);慣性權(quán)重值越小,算法的局部搜索能力越強(qiáng),越有利于提高搜索精度.總體來(lái)看,慣性權(quán)重依然是平衡粒子群算法全局和局部搜索能力的重要參數(shù)之一,在一定程度上決定了算法性能的優(yōu)劣.目前采用較多的動(dòng)態(tài)慣性權(quán)重是Shi等[12]提出的線性遞減權(quán)值策略.

(3)

其中,wmax和wmin分別表示慣性權(quán)重最大值和最小值,通常為0.9和0.4,t表示當(dāng)前迭代次數(shù),T表示最大進(jìn)化代數(shù).

此方法解決了基本PSO算法容易早熟及后期在全局最優(yōu)解附近產(chǎn)生振蕩的現(xiàn)象.研究者們發(fā)現(xiàn)控制參數(shù)慣性權(quán)重w的設(shè)置效果不但和進(jìn)化代數(shù)有關(guān)而且和全局最優(yōu)值的位置也有關(guān)系.所以,本文提出慣性權(quán)重w的調(diào)整如公式(4)所示:

(4)

其中,f表示粒子實(shí)時(shí)的函數(shù)適應(yīng)度函數(shù)值;fmin表示當(dāng)前所有粒子最小適應(yīng)度函數(shù)值;favg表示當(dāng)前所有粒子的平均適應(yīng)度函數(shù)值.

(5)

其中,N表示種群規(guī)模;fi表示第i個(gè)粒子的適應(yīng)度函數(shù)值.

3.2 雜交粒子群算法

為解決粒子群算法在后期易陷入局部極值,本文在粒子群算法中融入遺傳算法的雜交操作,提出了雜交粒子群算法(Hybrid Particle Swarm Optimization algorithm,HPSO).HPSO的主要思想是:在粒子群每次進(jìn)化的過(guò)程中,首先,根據(jù)設(shè)定的雜交概率取出一定數(shù)量的父代粒子(m)放入雜交池內(nèi);然后,在雜交池中,對(duì)被取出的一定數(shù)量的m兩兩任意進(jìn)行交配,形成一樣數(shù)量的子代粒子(n);最后,利用n代替m.

子代粒子的位置如公式(6)所示:

nx=i×mx(1)+(1-i)×mx(2)

(6)

其中,nx為子代粒子的位置;mx為父代粒子的位置;i為介于0和1之間的均勻隨機(jī)數(shù).

子代粒子的速度如公式(7)所示:

(7)

其中,nv為子代粒子的速度;mv為父代粒子的速度.

3.3 蛻變關(guān)系

定義1.蛻變關(guān)系:設(shè)f為目標(biāo)函數(shù),程序p實(shí)現(xiàn)函數(shù)f的功能,假設(shè)程序有兩個(gè)以上的輸入,n≥2,且程序所對(duì)應(yīng)的輸出是.

若滿足關(guān)系r時(shí),滿足關(guān)系rf,即:

r(x1,x2,…,xn)?rf(f(x1),f(x2),…,f(xn))

(8)

則稱(r,rf)為程序p的蛻變關(guān)系.

若程序p是正確的,則它一定滿足:

r(I1,I2,…,In)?rf(P(I1),P(I2),…,P(In))

(9)

其中,I1,I2,…,In是程序p的對(duì)應(yīng)于x1,x2,…xn的輸入,p(I1),P(I2),…,P(In)是相應(yīng)的輸出.

定義2.蛻變域(DMT(p))與非蛻變域(DNMT(p)):假設(shè)D(D′?D)是程序p的輸入域,在D′上對(duì)p進(jìn)行蛻變測(cè)試,則稱D′是p的蛻變域,記作DMT(p),稱D-D′為程序p的非蛻變域,記作DNMT(p).

定義3.源輸入和衍生輸入:假設(shè)(r,rf)是程序p的蛻變關(guān)系,若r是一個(gè)二元等式關(guān)系(r(x1,x2)),則稱(r,rf)是程序p的二元蛻變關(guān)系,記作(rb,rfb).若對(duì)于?I1∈ξ?DMT(P),?I2∈ξ?DMT(P),使得rb(I1,I2)成立,則稱ξ是二元蛻變關(guān)系(rb,rfb)的定義域,記作DR((rb,rfb)),稱I1為源輸入,I2為I1基于(rb,rfb)的衍生輸入,記作I2=FU(I1,(rb,rfb)).

例如,在測(cè)試計(jì)算函數(shù)f(x)=e-x的程序時(shí),依照定義2,pe-x的蛻變域DMT(pe-x)=(-∞,+∞).MRe-x:(x1+x2=0,f(x1)×f(x2)=1)是根據(jù)目標(biāo)函數(shù)的ex×e-x=1這一性質(zhì),為pe-x構(gòu)造的一條二元蛻變關(guān)系,依照定義3,MRe-x的定義域DR(MRe-x)=(-∞,+∞),任選一值0.2∈DR(MRe-x)作為源輸入,基于MRe-x的衍生輸入FU(0.2,MRe-x)=-0.2.

3.4 適應(yīng)度函數(shù)構(gòu)造方法

針對(duì)路徑覆蓋方法生成測(cè)試數(shù)據(jù),主要是給出程序在實(shí)參的驅(qū)動(dòng)下實(shí)際遍歷的路徑和分支路徑之間的偏離程度.適應(yīng)度函數(shù)構(gòu)造的目標(biāo)是它能夠很好地評(píng)價(jià)所生成的測(cè)試數(shù)據(jù)的優(yōu)劣,并且能引導(dǎo)粒子群最終找到目標(biāo)路徑的測(cè)試數(shù)據(jù).所以,適應(yīng)度函數(shù)的構(gòu)造是搜索算法自動(dòng)生成測(cè)試數(shù)據(jù)效率高低的關(guān)鍵.

本文參考Korel[13]和Tracey等[14]的理論研究成果,適應(yīng)度函數(shù)的設(shè)計(jì)采用“分支函數(shù)疊加法”.所有的分支謂詞都是“E1OPE2”的形式,其中,E1和E2表示算術(shù)表達(dá)式.OP∈{<,<=,>,>=,=,≠}.相應(yīng)的目標(biāo)函數(shù)是“frel0”的形式,其中,f是一個(gè)實(shí)值函數(shù),即“分支函數(shù)”.采用如表1所示的分支謂詞和分支函數(shù)的關(guān)系.

其中,邏輯運(yùn)算采用如表2的構(gòu)造方法(Bi表示分支謂詞,Fi為相應(yīng)的分支函數(shù)).

假設(shè)由m個(gè)分支,n個(gè)參數(shù)組成目標(biāo)路徑,則m個(gè)分支函數(shù)分別表示為:

f1=f1(x1,x2,…,xn)

f2=f2(x1,x2,…,xn)

…

fm=fm(x1,x2,…,xn)

表1 分支函數(shù)的構(gòu)造方法Table 1 Connection between branch predicates and branch functions

該路徑的適應(yīng)度函數(shù)表示為:

F=F(f1)+F(f2)+…+F(fm)

(10)

表2 邏輯運(yùn)算符的構(gòu)造方法Table 2 Information for processing logical operators

3.5 MRHPSO算法自動(dòng)生成測(cè)試數(shù)據(jù)的模型

本文提出的MRHPSO算法生成測(cè)試數(shù)據(jù)模型主要包括3個(gè)模塊,如圖1所示:測(cè)試環(huán)境的構(gòu)造模塊、基于HPSO算法的測(cè)試數(shù)據(jù)生成模塊和基于MR的測(cè)試數(shù)據(jù)生成模塊.

圖1 MRHPSO算法生成測(cè)試數(shù)據(jù)的模型Fig.1 Framework of the proposed method

測(cè)試環(huán)境構(gòu)造模塊是該模型的基礎(chǔ)模塊.在此模塊,對(duì)待測(cè)程序進(jìn)行靜態(tài)路徑分析,選擇目標(biāo)路徑,構(gòu)造出適應(yīng)度函數(shù)并構(gòu)建蛻變關(guān)系.基于HPSO算法的測(cè)試數(shù)據(jù)生成模塊是該模型的重要組成部分.根據(jù)HPSO算法的具體流程生成源測(cè)試用例.基于MR的測(cè)試數(shù)據(jù)生成模塊是該模型的核心部分.根據(jù)所構(gòu)造的蛻變關(guān)系利用源測(cè)試用例生成新的測(cè)試數(shù)據(jù).當(dāng)基于MR生成的所有衍生輸入都無(wú)法遍歷路徑時(shí),該算法將結(jié)束.

3.6 MRHPSO自動(dòng)生成測(cè)試數(shù)據(jù)的算法流程

輸入:經(jīng)分支函數(shù)插樁后的待測(cè)程序

輸出:找到目標(biāo)路徑的測(cè)試數(shù)據(jù)

Step 1.對(duì)待測(cè)程序進(jìn)行靜態(tài)分析,插裝待測(cè)程序,構(gòu)造蛻變關(guān)系.

Step 2.對(duì)粒子群進(jìn)行初始化,設(shè)定種群規(guī)模N的值、學(xué)習(xí)因子c1、c2的值和慣性權(quán)重的最大值wmax和最小值wmin,以及最大進(jìn)化代數(shù)T.在數(shù)據(jù)范圍內(nèi),對(duì)每個(gè)粒子隨機(jī)初始化它們的位置Xi和速度vi.

Step 3.對(duì)進(jìn)化個(gè)體進(jìn)行解碼,執(zhí)行插樁后的待測(cè)程序.

Step 4.首先,找到目標(biāo)路徑的測(cè)試數(shù)據(jù),保存此測(cè)試數(shù)據(jù)并將該目標(biāo)路徑從目標(biāo)路徑集中去除;然后,如果此測(cè)試數(shù)據(jù)(源輸入)范圍不在非蛻變域DNMT(p)中,那么,根據(jù)MR生成新的測(cè)試數(shù)據(jù)(衍生輸入);最后,判斷衍生輸入是否在預(yù)定義的數(shù)據(jù)范圍內(nèi)且是否覆蓋了目標(biāo)路徑集中的路徑,如果是,則保存該測(cè)試數(shù)據(jù),并將此路徑去除.

Step 5.對(duì)每個(gè)粒子計(jì)算適應(yīng)度值F(xi),將粒子的位置和適應(yīng)值存儲(chǔ)在粒子的個(gè)體極值Pbest(i)中,將全部Pbest中適應(yīng)度值最好的粒子的個(gè)體位置和適應(yīng)度值存儲(chǔ)在全局極值gbest中.

Step 6.根據(jù)公式(4)自適應(yīng)調(diào)節(jié)慣性權(quán)重,根據(jù)粒子群進(jìn)化公式(1)、公式(2),生成子代進(jìn)化種群.

Step 7.對(duì)每個(gè)粒子,用它的適應(yīng)度值F(xi)與個(gè)體極值Pbest(i)進(jìn)行比較.如果F(xi)

Step 8.按照HPSO算法的主要思想,根據(jù)公式(6)和公式(7)更新子代種群.

Step 9.判斷終止條件是否得到滿足,若是,則輸出測(cè)試數(shù)據(jù);否則,返回Step 3.

4 實(shí) 驗(yàn)

4.1 實(shí)驗(yàn)方案

本文采用三角形分類程序(TriClassArea)、求最大最小值程序(MaxMin)和冒泡排序程序(BubbleSort)作為基準(zhǔn)程序,分析比較本文所提出的算法(MRHPSO)與自適應(yīng)粒子群算法(APSO)在數(shù)據(jù)自動(dòng)生成上的性能.被測(cè)程序TriClassArea的功能是:判斷輸入的3條邊a,b,c是否均大于零且滿足構(gòu)成三角形的條件,若滿足,則將所構(gòu)成的三角形類型輸出并計(jì)算三角形的面積.三元組(a,b,c)分別表示三角形的三條邊,作為程序的源輸入,三角形類型和面積作為程序的結(jié)果輸出.該程序有多個(gè)條件控制,但不包括循環(huán)結(jié)構(gòu),共有6個(gè)分支,含有3個(gè)選擇嵌套.被測(cè)程序MaxMin的功能是:輸出3個(gè)數(shù)中的最大值和最小值.該程序有2個(gè)選擇構(gòu)成選擇并列關(guān)系.被測(cè)程序BubbleSort的功能是:10個(gè)數(shù)由小到大順序輸出.該程序共有2個(gè)循環(huán),1個(gè)選擇.每組實(shí)驗(yàn)操作100次,分析兩個(gè)重要指標(biāo):平均進(jìn)化代數(shù)和平均進(jìn)化時(shí)間.在實(shí)際實(shí)驗(yàn)中,存在找不到目標(biāo)路徑測(cè)試數(shù)據(jù)的情況,記錄100次重復(fù)實(shí)驗(yàn)?zāi)軌蛩阉鞯綔y(cè)試數(shù)據(jù)的平均成功率.

4.2 蛻變關(guān)系的構(gòu)造

蛻變關(guān)系是蛻變測(cè)試的重要組成部分,且不具有通用性,決定了蛻變測(cè)試的有效性[15].蛻變關(guān)系的構(gòu)造需要根據(jù)程序的特定屬性,通常需要測(cè)試人員有一定的先驗(yàn)知識(shí).根據(jù)三角形的性質(zhì)可知:DMT={(a,b,c)|(a+b>c∧(a+c>b)∧(b+c>a))}為TriClassArea程序的蛻變域.依據(jù)三角形的性質(zhì)和平行四邊形的性質(zhì)為待測(cè)程序TriClassArea構(gòu)造出6條蛻變關(guān)系,分別為MR1—MR6.其中,(a,b,c)表示源輸入,(a′,b′,c′)表示衍生輸入,TriClassArea(a,b,c)表示3個(gè)邊長(zhǎng)分別為a,b,c的三角形的面積.根據(jù)數(shù)組中任意兩個(gè)元素進(jìn)行交換,程序結(jié)果輸出不變的性質(zhì)為待測(cè)程序MaxMin構(gòu)造出2條蛻變關(guān)系,分別為MR7—MR8.待測(cè)程序BubbleSort和MaxMin程序有相同的蛻變關(guān)系.通常,一個(gè)程序的源輸入的衍生輸入有不同的價(jià)值,可能覆蓋不同路徑.一個(gè)蛻變關(guān)系的輸入關(guān)系可以用來(lái)生成覆蓋多個(gè)路徑的測(cè)試用例.假設(shè)輸入x所遍歷的路徑與-x不同,當(dāng)生成測(cè)試用例x時(shí),另一個(gè)測(cè)試用例-x由蛻變關(guān)系生成.

MR1:If (a′,b′,c′)=(b,a,c),thenTriClassArea(a′,b′,c′)=TriClassArea(a,b,c)

MR2:If (a′,b′,c′)=(c,b,a),thenTriClassArea(a′,b′,c′)=TriClassArea(a,b,c)

MR3:If (a′,b′,c′)=(a,c,b),thenTriClassArea(a′,b′,c′)=TriClassArea(a,b,c)

MR7:如果數(shù)組中任意兩個(gè)不同值的元素進(jìn)行交換,程序輸出結(jié)果相同.

MR8:如果將數(shù)組中的所有元素逆序排列,程序輸出結(jié)果相同.

圖2 程序TriClassArea蛻變關(guān)系的構(gòu)造原理Fig.2 Aufbau principle of metamorphic relations based on TriClassArea

本文提出的MRHPSO算法,在用雜交粒子群算法產(chǎn)生測(cè)試數(shù)據(jù)的過(guò)程中,對(duì)找到的測(cè)試數(shù)據(jù)通過(guò)蛻變關(guān)系衍生出覆蓋其他目標(biāo)路徑的測(cè)試數(shù)據(jù).使待測(cè)程序的路徑改變的蛻變關(guān)系(MR)和非蛻變域(DNMT(p))如表3所示.

表3 路徑改變的蛻變關(guān)系Table 3 Metamorphic relations of the program

4.3 實(shí)驗(yàn)環(huán)境和參數(shù)設(shè)置

4.3.1 硬件環(huán)境

系統(tǒng)處理器:Intel(R)Core(TM)i5-8500 CPU @ 3.00GHz 3.00GHz;

RAM:8.00GB.

4.3.2 軟件環(huán)境

操作系統(tǒng):Windows 10專業(yè)版;

實(shí)驗(yàn)平臺(tái):MATLAB R2016b;

開發(fā)語(yǔ)言:Matlab.

為避免算法參數(shù)的配置不同對(duì)算法性能有所影響,兩種算法采用相同的參數(shù)配置.被測(cè)程序相同的參數(shù)設(shè)置如下:最大進(jìn)化代數(shù)T=1000,學(xué)習(xí)因子c1=1.5,c2=1.5,慣性權(quán)重wmax=0.65,wmin=0.15.雜交概率bc=0.8,雜交池比例bs=0.1.

4.4 實(shí)驗(yàn)結(jié)果

4.4.1 TriClassArea程序

針對(duì)不同種群規(guī)模下,不同數(shù)據(jù)范圍下的三角形整數(shù)邊運(yùn)行100次實(shí)驗(yàn),記錄覆蓋目標(biāo)路徑的測(cè)試數(shù)據(jù)所需的進(jìn)化代數(shù)和運(yùn)行時(shí)間,實(shí)驗(yàn)結(jié)果如表4、表5和表6所示.

表4 測(cè)試數(shù)據(jù)生成效率實(shí)驗(yàn)結(jié)果Table 4 Comparison of two algorithms

表5 測(cè)試數(shù)據(jù)生成效率實(shí)驗(yàn)結(jié)果Table 5 Comparison of two algorithms

從表4可以看出:當(dāng)粒子群規(guī)模為100時(shí),在4種不同的數(shù)據(jù)范圍下,MRHPSO算法均比APSO算法的平均進(jìn)化代數(shù)少、平均進(jìn)化時(shí)間短;隨著數(shù)據(jù)范圍的不斷增大,生成測(cè)試數(shù)據(jù)的難度也隨著增加,兩種算法的平均進(jìn)化代數(shù)和平均進(jìn)化時(shí)間均不斷增多,但MRHPSO算法在4種數(shù)據(jù)范圍的實(shí)驗(yàn)結(jié)果總是APSO算法的平均進(jìn)化代數(shù)少、平均進(jìn)化時(shí)間短.如在數(shù)據(jù)范圍為[1,256],APSO算法的進(jìn)化代數(shù)平均為167.1代,而MRHPSO算法的進(jìn)化代數(shù)平均只需54.5代,約是APSO算法的1/3.與此相對(duì)應(yīng),APSO算法的平均進(jìn)化時(shí)間3.1811s,而MRHPSO算法的平均進(jìn)化時(shí)間只需2.3331s.

表6 測(cè)試數(shù)據(jù)生成效率實(shí)驗(yàn)結(jié)果Table 6 Comparison of two algorithms

從表5、表6不難看出:在種群規(guī)模為200和300的情況下,針對(duì)4種數(shù)據(jù)范圍,MRHPSO算法總是比APSO算法的平均進(jìn)化代數(shù)少,平均進(jìn)化時(shí)間短.隨著種群規(guī)模的增多,測(cè)試數(shù)據(jù)生成所需要平均進(jìn)化時(shí)間也增多.如在種群規(guī)模為300時(shí),數(shù)據(jù)范圍在[1,512]的情況下,平均進(jìn)化代數(shù)MRHPSO算法比APSO算法少118.2代,約為APSO算法的1/3.相應(yīng)地,MRHPSO算法的平均進(jìn)化時(shí)間比APSO算法少0.5755s.

圖3 生成測(cè)試數(shù)據(jù)的平均成功率Fig.3 Success rate of test data generation

圖3為兩種算法生成測(cè)試數(shù)據(jù)的平均成功率,從圖3中可以看出,當(dāng)數(shù)據(jù)范圍加大時(shí),APSO算法的生成測(cè)試數(shù)據(jù)的平均成功率有所下降.如在數(shù)據(jù)范圍為[1,1024]時(shí),MRHPSO算法平均成功率達(dá)到100%,而APSO算法的平均成功率為99%,說(shuō)明隨著數(shù)據(jù)范圍的增大,MRHPSO算法更具有優(yōu)勢(shì).

4.4.2 MaxMin程序

在種群規(guī)模為100的情況下,針對(duì)不同數(shù)據(jù)范圍下的3個(gè)整數(shù)運(yùn)行100次實(shí)驗(yàn),記錄覆蓋目標(biāo)路徑的測(cè)試數(shù)據(jù)所需的進(jìn)化代數(shù)和運(yùn)行時(shí)間,實(shí)驗(yàn)結(jié)果如表7所示.

表7 測(cè)試數(shù)據(jù)生成效率實(shí)驗(yàn)結(jié)果Table 7 Comparison of two algorithms

4.4.3 BubbleSort程序

在種群規(guī)模為100的情況下,針對(duì)不同數(shù)據(jù)范圍下的10個(gè)整數(shù)運(yùn)行100次實(shí)驗(yàn),記錄覆蓋目標(biāo)路徑的測(cè)試數(shù)據(jù)所需的進(jìn)化代數(shù)和運(yùn)行時(shí)間,實(shí)驗(yàn)結(jié)果如表8所示.

表8 測(cè)試數(shù)據(jù)生成效率實(shí)驗(yàn)結(jié)果Table 8 Comparison of two algorithms

從表7、表8不難看出:種群規(guī)模100的情況下,在不同的數(shù)據(jù)范圍下,MRHPSO算法在尋找目標(biāo)測(cè)試路徑時(shí)所需的進(jìn)化代數(shù)和所消耗的進(jìn)化時(shí)間上均少于APSO算法.

在不同的種群規(guī)模下,如200,300,400等情況做了大量的實(shí)驗(yàn),實(shí)驗(yàn)結(jié)果均顯示,MRHPSO算法在進(jìn)化代數(shù)和進(jìn)化時(shí)間上均優(yōu)于APSO算法.

通過(guò)對(duì)比實(shí)驗(yàn)表明,本文所提出的方法能有效的提高測(cè)試數(shù)據(jù)生成的效率.

5 結(jié) 論

手工測(cè)試過(guò)程消耗了軟件開發(fā)的40%～70%的時(shí)間和成本.自動(dòng)的生成測(cè)試可以有效降低測(cè)試成本,提高測(cè)試質(zhì)量,而測(cè)試數(shù)據(jù)的好壞直接決定軟件測(cè)試的結(jié)果,因此,如何生成高質(zhì)量的測(cè)試數(shù)據(jù)一直是研究人員關(guān)注的重點(diǎn).本文提出了融入蛻變關(guān)系的雜交粒子群算法并將其應(yīng)用于測(cè)試數(shù)據(jù)生成中,利用測(cè)試數(shù)據(jù)之間的蛻變關(guān)系,在進(jìn)化生成過(guò)程中,當(dāng)有一個(gè)目標(biāo)路徑測(cè)測(cè)試數(shù)據(jù)生成時(shí),作為源輸入,利用待測(cè)程序的蛻變關(guān)系衍生出后續(xù)的測(cè)試數(shù)據(jù),以覆蓋程序的其他目標(biāo)路徑,使得測(cè)試數(shù)據(jù)的生成效率得到提高.但是,本文方法只適用于能夠根據(jù)待測(cè)程序的本質(zhì)屬性構(gòu)造出有效的蛻變關(guān)系的這種情況,需要測(cè)試人員有一定的先驗(yàn)知識(shí).今后的工作中,繼續(xù)將提高測(cè)試數(shù)據(jù)自動(dòng)生成的效率作為主要的研究方向.