基于成對(duì)組合的遺傳算法生成聯(lián)鎖測(cè)試用例

李 娟，陳光武，范多旺

（蘭州交通大學(xué) 光電技術(shù)與智能控制教育部重點(diǎn)實(shí)驗(yàn)室，蘭州 730070）

計(jì)算機(jī)聯(lián)鎖系統(tǒng)是保證鐵路行車安全和效率的實(shí)時(shí)控制和防護(hù)系統(tǒng)。聯(lián)鎖軟件是聯(lián)鎖系統(tǒng)的安全性關(guān)鍵軟件，通過(guò)自動(dòng)測(cè)試可盡早發(fā)現(xiàn)并排除聯(lián)鎖軟件潛在的缺陷，使聯(lián)鎖軟件運(yùn)行時(shí)發(fā)生故障的幾率降到最低。聯(lián)鎖軟件測(cè)試的實(shí)質(zhì)是針對(duì)所設(shè)計(jì)的一組測(cè)試用例，執(zhí)行聯(lián)鎖程序，以發(fā)現(xiàn)聯(lián)鎖程序的缺陷。測(cè)試用例的設(shè)計(jì)與生成是聯(lián)鎖軟件測(cè)試中的難點(diǎn)和關(guān)鍵，它決定著軟件測(cè)試的質(zhì)量，影響軟件測(cè)試的效率和速度。

測(cè)試用例的自動(dòng)生成是在特定的數(shù)據(jù)空間中尋找符合測(cè)試標(biāo)準(zhǔn)的輸入數(shù)據(jù)，執(zhí)行將實(shí)際結(jié)果與預(yù)期結(jié)果比較的過(guò)程。本文研究的重點(diǎn)是測(cè)試用例質(zhì)量的提高和優(yōu)化。該問(wèn)題具有非線性特點(diǎn)，而遺傳算法的優(yōu)化計(jì)算和全局尋優(yōu)搜索策略適合于處理高度復(fù)雜的非線性問(wèn)題。本文提出一種新的設(shè)計(jì)方案：應(yīng)用基于成對(duì)組合的遺傳算法進(jìn)行聯(lián)鎖測(cè)試用例自動(dòng)生成和優(yōu)化，以提高聯(lián)鎖測(cè)試用例的質(zhì)量。

1 成對(duì)組合覆蓋

成對(duì)組合覆蓋是軟件測(cè)試方法之一，同時(shí)也是衡量測(cè)試充分性的一種準(zhǔn)則。它是一種面向應(yīng)用的測(cè)試方案，按照兩兩覆蓋的原則產(chǎn)生測(cè)試用例。成對(duì)組合的測(cè)試目標(biāo)是所設(shè)計(jì)的測(cè)試用例集合對(duì)系統(tǒng)的所有對(duì)象可能取值的兩兩組合至少覆蓋一次。滿足成對(duì)組合的最小測(cè)試用例集實(shí)際上是經(jīng)典的NP-Complete問(wèn)題，目前主要采用啟發(fā)式算法或人工智能方法產(chǎn)生測(cè)試用例的最優(yōu)解。

測(cè)試用例最優(yōu)解的生成模型分析如下。設(shè)DC為道岔測(cè)試用例集合，DZ為其一個(gè)子集，對(duì)應(yīng)每個(gè)測(cè)試用例都有相應(yīng)的測(cè)試代價(jià)，DR為測(cè)試需求。測(cè)試用例最優(yōu)解問(wèn)題等價(jià)于如何從測(cè)試用例空間DC中選取最小數(shù)量的用例子集DZ，使DZ能夠以最小的測(cè)試代價(jià)覆蓋測(cè)試需求集DR。

設(shè)道岔測(cè)試有3個(gè)輸入?yún)?shù)A、B、C。A表示道岔，有2個(gè)值A(chǔ)1、A2，V(A)={1/3,5}；B表示操縱，有4個(gè)值B1、B2、B3、B4，V(B)={定位單獨(dú)操縱, 反位單獨(dú)操縱，單獨(dú)解鎖，單獨(dú)鎖閉}；C表示條件，有4個(gè)值C1、C2、C3、C4，V(C)={一般狀態(tài)，進(jìn)路鎖閉，區(qū)段鎖閉，引導(dǎo)總鎖閉}。測(cè)試需求集DR可描述為DR={dr1,dr2,dr3,dr4,dr5}，其中需求dr1為道岔定、反位單獨(dú)操縱，dr2為道岔單獨(dú)鎖閉、操縱、解鎖，dr3為進(jìn)路鎖閉后道岔單操測(cè)試，dr4為區(qū)段鎖閉后道岔單操測(cè)試，dr5為引導(dǎo)總鎖閉后道岔單操測(cè)試。按照全覆蓋準(zhǔn)則，共需2×4×4=32個(gè)測(cè)試用例。而應(yīng)用成對(duì)組合覆蓋可以只包含16個(gè)測(cè)試用例。

圖1 道岔測(cè)試用例生成過(guò)程

測(cè)試用例生成過(guò)程如圖1，采用的是AETG啟發(fā)式算法。AETG(Automatic Efficient Test Genera-tor,自動(dòng)高效測(cè)試生成器)開(kāi)始于一個(gè)空的測(cè)試用例集，每次根據(jù)貪心算法產(chǎn)生一組候選用例，從中選取能夠覆蓋最多未被覆蓋的成對(duì)組合的用例為新的測(cè)試用例。最初未被覆蓋的成對(duì)組合集WZ={(A1,B1),(A1,B2),(A1,B3), (A1,B4),(A1,C1),(A1,C2),(A1,C3),(A1,C4),(A2,B1),(A2,B2),(A2,B3),(A2,B4),(A2,C1),(A2,C2),(A2,C3),(A2,C4),(B1,C1),(B1,C2),(B1,C3),(B1,C4),(B2,C1),(B2,C2),(B2,C3),(B2,C4), (B3,C1), (B3,C2),(B3,C3),(B3,C4),(B4,C1),(B4,C2),(B4,C3),(B4,C4)}。首先選擇測(cè)試用例DC1=(A1,B1,C1)，然后去掉WZ中的(A1,B1)、(A1,C1)和(B1,C1), 以剩下的組合中出現(xiàn)次數(shù)最多的A2為中心選擇DC2=(A2,B2,C2)。按照同樣的方法依次遞歸產(chǎn)生新的測(cè)試子集，直到集合WZ為空。測(cè)試用例集和測(cè)試需求間的覆蓋關(guān)系如表1。

表1 測(cè)試用例與測(cè)試需求覆蓋表

此例中利用16個(gè)交互測(cè)試用例組合覆蓋測(cè)試需求，能有效地避免測(cè)試用例集之間產(chǎn)生的組合爆炸問(wèn)題。采用傳統(tǒng)的貪心搜索方法求得的測(cè)試用例集并非最小化的測(cè)試用例子集，其中包含大量的冗余測(cè)試用例，影響了測(cè)試效率。

2 遺傳算法的設(shè)計(jì)

本文在設(shè)計(jì)遺傳算法時(shí)主要考慮3個(gè)因素：可靠性，收斂性，穩(wěn)定性。

解決滿足覆蓋需求的軟件測(cè)試用例集生成問(wèn)題時(shí)，通常先以隨機(jī)方法產(chǎn)生初始種群，然后將種群中的不可行個(gè)體通過(guò)選擇、交叉、變異轉(zhuǎn)化為可行個(gè)體，再根據(jù)種群中個(gè)體的適應(yīng)度函數(shù)值選取最優(yōu)的測(cè)試用例子集?；谏鲜鏊悸?，本文將GA嵌入到AETG中，并從貪心算法改進(jìn)為遺傳算法生成新的測(cè)試用例集。以道岔測(cè)試為例，所設(shè)計(jì)的算法框架如圖2。

圖2 算法的整體流程

其中遺傳算法的代碼結(jié)構(gòu)如下所示：

Genetic Algorithm Program

Begin

t<-0;

initialize(); //隨機(jī)產(chǎn)生N個(gè)個(gè)體進(jìn)行種群初始化

execute solution();//運(yùn)行N個(gè)初始個(gè)體

圖3 道岔測(cè)試用例的編碼表示

2.1 參數(shù)編碼方式

遺傳算法處理過(guò)程中參數(shù)編碼對(duì)算法的效率、性能有很大的影響。為了將問(wèn)題的潛在解使用適合遺傳算法的基因編碼表示，本文將組合測(cè)試中的輸入?yún)?shù)映射到位串空間Bl={0,1}l上，然后在其上進(jìn)行遺傳操作，得到的結(jié)果再通過(guò)解碼過(guò)程還原成其表現(xiàn)型以進(jìn)行適應(yīng)度函數(shù)值的評(píng)估。根據(jù)各個(gè)參數(shù)的取值范圍確定其編碼長(zhǎng)度。若一個(gè)參數(shù)的最大取值為L(zhǎng)i，且2n-1

2.2 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)是用以區(qū)分種群中個(gè)體好壞的演進(jìn)過(guò)程。利用遺傳算法生成的測(cè)試用例集，在滿足成對(duì)組合覆蓋的前提下，其例數(shù)盡可能的少。關(guān)于進(jìn)化個(gè)體的適應(yīng)度可按以下公式計(jì)算：

其中Cov(DCj)是用例集DCj的測(cè)試覆蓋度，Cost(DCj) 是用例集DCj的測(cè)試運(yùn)行代價(jià)。Cov(DCj)可按式（2）計(jì)算，Cost(DCj)可按式（3）計(jì)算。

測(cè)試用例中的覆蓋信息由表1給出，在第j列中有多少個(gè)“X”，就代表測(cè)試用例DCj覆蓋了哪些測(cè)試需求。設(shè)向量Xj=[xj1,xj2,…,xjk]表示表1中第j列的信息，向量W=[w1,w2,…,wk]表示每個(gè)測(cè)試需求的權(quán)重，用例子集DZ覆蓋度可按下式計(jì)算：

從以上計(jì)算方法可以看出，F(xiàn)值越高表示單位測(cè)試代價(jià)下測(cè)試用例子集DZ的覆蓋度越大。

2.3 遺傳操作設(shè)計(jì)

遺傳算法的基本操作包括3種：選擇、雜交和變異操作。

不同的選擇策略將導(dǎo)致不同的選擇壓力，從而影響算法的收斂速度。選用輪賭盤(pán)模型，選擇算子從當(dāng)前群體中按照某一概率選擇一些個(gè)體作為新生種群的父輩，某個(gè)體Xi被選擇的概率Pi與其適應(yīng)度函數(shù)值成正比。設(shè)累計(jì)函數(shù)Lj=∑i=1～jPi，每個(gè)個(gè)體DCj處于選擇區(qū)間[Lj,Lj+1），計(jì)算時(shí)每一輪產(chǎn)生一個(gè)[0,1]均勻分布的隨機(jī)數(shù)，以該隨機(jī)數(shù)為指針來(lái)確定對(duì)應(yīng)選擇區(qū)間的個(gè)體。個(gè)體的適應(yīng)值越大，它被選擇到的機(jī)會(huì)越多，其基因被遺傳到下一代的可能性越大。

雜交運(yùn)算是遺傳算法區(qū)別于其他進(jìn)化算法的重要特征。它的設(shè)計(jì)與所研究的問(wèn)題密切相關(guān)，本文采用單點(diǎn)雜交操作，能較少的破壞優(yōu)良個(gè)體的性狀，同時(shí)有效地產(chǎn)生較好的新個(gè)體。單點(diǎn)雜交是指在個(gè)體編碼串中只隨機(jī)設(shè)計(jì)一個(gè)雜交點(diǎn)，然后在該點(diǎn)相互交換兩個(gè)配對(duì)個(gè)體的部分染色體。兩個(gè)長(zhǎng)度為n的個(gè)體編碼串進(jìn)行單點(diǎn)雜交的過(guò)程如圖4。

圖4 單點(diǎn)雜交示意圖

變異操作可改善遺傳算法的局部搜索能力，維持群體的多樣性，防止出現(xiàn)過(guò)早收斂。本文中二值基因鏈模型，采用基本位變異操作，即對(duì)指定的變異點(diǎn)進(jìn)行取反運(yùn)算。若測(cè)試用例子集A編碼為：10111010，對(duì)選取的第5位基因值取反后產(chǎn)生新的A編碼為：10110010。雜交算子和變異算子的相互配合，共同完成對(duì)搜索空間的全局搜索和局部搜索，實(shí)現(xiàn)測(cè)試用例最優(yōu)解的尋優(yōu)過(guò)程。

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

遺傳算法因其自身強(qiáng)大的魯棒性和全局尋優(yōu)搜索能力，在解決非線性、大空間的測(cè)試數(shù)據(jù)自動(dòng)生成中顯示出獨(dú)特的優(yōu)勢(shì)和高效性。將其嵌入到成對(duì)組合的啟發(fā)式算法AETG中，可有效的減少冗余測(cè)試用例，更快的收斂到全局近似最優(yōu)解，提高測(cè)試效率。本文以道岔測(cè)試為例，著重介紹了應(yīng)用基于成對(duì)組合覆蓋的遺傳算法進(jìn)行計(jì)算機(jī)聯(lián)鎖測(cè)試用例生成和優(yōu)化的新想法，并對(duì)其應(yīng)用過(guò)程進(jìn)行了分析探討，給出了具體的設(shè)計(jì)思路。