改進(jìn)遺傳算子的測(cè)試用例優(yōu)化研究

劉 音

（北京交通大學(xué)海濱學(xué)院 河北·滄州 061199）

0 引言

軟件測(cè)試的主要目的是通過(guò)執(zhí)行測(cè)試用例檢測(cè)出所有隱藏的錯(cuò)誤，是軟件質(zhì)量保證的重要手段。測(cè)試用例（Test Case）是由一組測(cè)試輸入、執(zhí)行條件及預(yù)期結(jié)果組成的，是用于衡量軟件是否存在錯(cuò)誤的主要依據(jù)，它的數(shù)量和質(zhì)量直接決定了測(cè)試效率和成本。隨著軟件規(guī)模不斷擴(kuò)大，測(cè)試用例集規(guī)模也會(huì)越來(lái)越大，其中的冗余測(cè)試用例也會(huì)隨之增多，測(cè)試成本也就隨著增大。為了有效降低測(cè)試成本，有必要對(duì)測(cè)試用例集進(jìn)行優(yōu)化，即在保證原檢測(cè)錯(cuò)誤能力的基礎(chǔ)上，尋找原始用例集的一個(gè)子集，使其覆蓋所有測(cè)試需求，且保證運(yùn)行成本最小。

遺傳算法（Genetic Algorithm,GA）是將生物進(jìn)化過(guò)程中適者生存規(guī)則與種群內(nèi)部染色體的信息隨機(jī)交換機(jī)制相結(jié)合的高效全局尋優(yōu)搜索算法。作為一種全局搜索方法廣泛應(yīng)用在測(cè)試用例優(yōu)化領(lǐng)域中，有著獨(dú)特的優(yōu)勢(shì)和高效性。

1 改進(jìn)遺傳算子

遺傳算法是由進(jìn)化論和遺傳學(xué)演化而來(lái)的一種直接搜索優(yōu)化方法。它將所有可能解看成是種群的一個(gè)個(gè)體，依據(jù)適者生存、優(yōu)勝劣汰的進(jìn)化原則，進(jìn)行選擇、交叉和變異操作，最終得出問(wèn)題最優(yōu)解。但遺傳算法中存在以下問(wèn)題：

（1）早熟現(xiàn)象，即過(guò)早陷入局部最優(yōu)解，而很難走向全局最優(yōu)。

（2）在選擇操作過(guò)程中，適應(yīng)度高的個(gè)體作為父代，可能導(dǎo)致遺傳基因趨于一致，也就是存在很多相似的個(gè)體，減少了種群的多樣性。

鑒于以上問(wèn)題，本文對(duì)選擇算子、交叉算子和變異算子進(jìn)行了改進(jìn)，進(jìn)而形成了一種新的改進(jìn)的遺傳算法（Improved Genetic Algorithm,IGA），并用改進(jìn)的遺傳算法實(shí)現(xiàn)測(cè)試用例集縮減。

1.1 改進(jìn)選擇算子

選擇算子作用就是依據(jù)個(gè)體適應(yīng)度值，從父代種群中選擇若干個(gè)體遺傳到下一代。輪盤(pán)賭法通過(guò)隨機(jī)性，保證了下一代種群的多樣性，但同時(shí)會(huì)使降低高適應(yīng)度個(gè)體選中概率難以收到最優(yōu)解。改進(jìn)的選擇算子是將排序與輪盤(pán)賭相結(jié)合的方法，增加了優(yōu)良個(gè)體的選擇概率，具體操作過(guò)程如下：

（1）種群中的個(gè)體按其適應(yīng)度的高低降序排列。

（2）對(duì)排好序的個(gè)體按5%、90%和5%分成三份，并用前5%的個(gè)體代替后5%的個(gè)體。

（3）計(jì)算個(gè)體適應(yīng)度 F(Ti)，i=(1,2,……，M)，M 為種群規(guī)模。

（4）計(jì)算選擇概率：個(gè)體適應(yīng)度值除以總適應(yīng)度值，如公式（1）所示。其中，P(Ti)為個(gè)體選擇概率，F(xiàn)(Ti)為個(gè)體適應(yīng)度。

（5）計(jì)算個(gè)體累積概率，如公式（2）所示，其中Qi表示個(gè)體累積概率。

（6）產(chǎn)生一個(gè)隨機(jī)數(shù)r，r在[0,1]范圍內(nèi)。

（7）若r

（8）重復(fù)7、8步驟M次。

1.2 改進(jìn)交叉算子

交叉操作就是兩個(gè)配對(duì)的個(gè)體按照某種方式交換某位基因或者某些位基因，從而產(chǎn)生新個(gè)體的過(guò)程。交叉類(lèi)型有：?jiǎn)吸c(diǎn)交叉、兩點(diǎn)交叉、多點(diǎn)交叉和均勻交叉等，本文采用單點(diǎn)交叉，實(shí)現(xiàn)過(guò)程是在交叉點(diǎn)的位置相互交換兩個(gè)配對(duì)個(gè)體的部分染色體。

交叉概率用于判斷兩個(gè)個(gè)體是否需要交叉，在遺傳進(jìn)化過(guò)程中，為保留優(yōu)良個(gè)體應(yīng)盡量降低其交叉概率，為優(yōu)化劣質(zhì)個(gè)體應(yīng)盡量增加其交叉概率。本文提出了新的計(jì)算動(dòng)態(tài)交叉概率方法，如公式（3）所示。

其中，f'表示兩個(gè)預(yù)交叉?zhèn)€體的高適應(yīng)度值，fmax為所有個(gè)體中的最大適應(yīng)度值，fmin為所有個(gè)體中的最小適應(yīng)度值，M1是適應(yīng)度值大于等于平均適應(yīng)度值的個(gè)體總數(shù)，M2是適應(yīng)度值小于平均適應(yīng)度值的個(gè)體總數(shù)，favg是平均適應(yīng)度值，Pc1和Pc2是兩個(gè)初始交叉概率、分別設(shè)置為：Pc1=0.5，Pc2=0.9。這樣就能保證進(jìn)化初期，有較大的交叉概率，保證種群多樣性，并且適應(yīng)度小的個(gè)體交叉概率更大；而在進(jìn)化后期，交叉概率相對(duì)較小，加快算法收斂。

圖1：用例集縮減規(guī)模

1.3 改進(jìn)變異算子

變異操作是模仿個(gè)體進(jìn)化過(guò)程中染色體的某個(gè)基因值發(fā)生突變過(guò)程，例如：采用二進(jìn)制編碼方式的個(gè)體，變異操作就是1變0或0變1。在變異操作中起關(guān)鍵作用的是變異概率，如果變異率較小，容易出現(xiàn)早熟現(xiàn)象，如果過(guò)大，會(huì)出現(xiàn)隨機(jī)搜索現(xiàn)象。本文提出了新的變異概率計(jì)算方法，如公式4所示。

Pm1和Pm2是初始變異率，Pm1=0.001，Pm2=0.005，fmax和fmin與公式8相同，f表示個(gè)體適應(yīng)度。適應(yīng)度小的個(gè)體變異率大，可以改良基因；適應(yīng)度大的個(gè)體變異率小，優(yōu)良基因可以遺傳給下一代。

2 IGA實(shí)現(xiàn)測(cè)試用例優(yōu)化

利用改進(jìn)遺傳算子解決測(cè)試用例優(yōu)化問(wèn)題時(shí)，首先根據(jù)測(cè)試用例與測(cè)試需求之間的覆蓋關(guān)系，形成初始個(gè)體集合，然后通過(guò)選擇、交叉和變異操作，求出測(cè)試用例集縮減問(wèn)題的最優(yōu)解。

2.1 測(cè)試用例優(yōu)化

測(cè)試用例優(yōu)化又稱(chēng)為測(cè)試用例約簡(jiǎn)，是M.J.Harrold等人在1993年提出的。早期，在測(cè)試用例縮減過(guò)程中并沒(méi)有考慮測(cè)試用例的運(yùn)行代價(jià)，導(dǎo)致執(zhí)行縮減后測(cè)試用例集代價(jià)并不能降低到最小?？s減過(guò)程中不僅要考慮測(cè)試需求覆蓋度，還要考慮測(cè)試用例執(zhí)行代價(jià)，測(cè)試用例集約簡(jiǎn)的定義：給出一組測(cè)試需求集R={r1,r2,r3,…,rm}，一組與測(cè)試需求相關(guān)的測(cè)試用例集T={t1,t2,t3,…,tn}，每個(gè)測(cè)試用例ti都有相應(yīng)的測(cè)試代價(jià)ci（ci>0），測(cè)試用例縮減問(wèn)題就是求T的一個(gè)真子集T’，滿足：T’的運(yùn)行代價(jià)最小，并且T’能覆蓋R。測(cè)試用例縮減結(jié)果就是滿足表1中的每行至少被一列覆蓋，且使“1”個(gè)數(shù)最少。

2.2 基因編碼

基因編碼就是把問(wèn)題空間的數(shù)據(jù)轉(zhuǎn)化成遺傳空間的由基因組成的個(gè)體，常用編碼方法有：二進(jìn)制編碼、浮點(diǎn)編碼和符號(hào)編碼。二進(jìn)制編碼就是由符號(hào)0和1所組成的二值符號(hào)集，編碼、解碼操作簡(jiǎn)單易行，交叉、變異等遺傳操作便于實(shí)現(xiàn)，故本文采用這種方法進(jìn)行基因編碼。根據(jù)測(cè)試需求和測(cè)試用例對(duì)應(yīng)關(guān)系構(gòu)建一個(gè)m×n矩陣：

圖2：算法運(yùn)行時(shí)間

R表示測(cè)試需求集，T表示測(cè)試用例集，m表示矩陣的行數(shù)、由測(cè)試需求的個(gè)數(shù)決定，n表示矩陣的列數(shù)、由測(cè)試用例個(gè)數(shù)決定。gij表示用例tj和需求ri之間的覆蓋關(guān)系，如果gij=1表示tj覆蓋ri，反之gij=0表示tj沒(méi)有覆蓋ri。矩陣中的每一行表示了一個(gè)需求被所有用例的覆蓋情況，把每一行看成一個(gè)個(gè)體，采用二進(jìn)制基因編碼如公式（6）所示。

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

適應(yīng)度是用來(lái)判斷種群中個(gè)體優(yōu)劣程度的指標(biāo)，并作為遺傳操作的依據(jù)。一般地，適應(yīng)度值越大，表明相應(yīng)的個(gè)體越優(yōu)，它的基因被復(fù)制到下一代的概率就越大，個(gè)體適應(yīng)度函數(shù)表示如公式（7）所示。

Cov(Tj)是用例集Tj的測(cè)試覆蓋度，計(jì)算方法如公式（8）所示。

Cost(Tj)是用例集Tj的運(yùn)行代價(jià)，計(jì)算方法如公式（9）所示，用測(cè)試時(shí)間執(zhí)行時(shí)間粗略表示其運(yùn)行代價(jià)。Cost(ti)表示執(zhí)行ti測(cè)試其覆蓋需求所用時(shí)間。

當(dāng)個(gè)體的適應(yīng)度達(dá)到給定的閾值或者個(gè)體的適應(yīng)度不在上升或者迭代次數(shù)達(dá)到閾值，終止計(jì)算。本文采用迭代次數(shù)達(dá)到閾值作為終止條件，最大迭代次數(shù)為150。不滿足收斂條件時(shí)，重復(fù)遺傳操作，直到收斂到最優(yōu)解。最后，根據(jù)測(cè)試用例與需求的覆蓋關(guān)系進(jìn)行解碼，獲得縮減后的測(cè)試用例集。

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

為驗(yàn)證改進(jìn)遺傳算法性能，在MATLAB仿真實(shí)驗(yàn)的環(huán)境下，完成了測(cè)試用例優(yōu)化系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)。以BBS論壇模擬程序?yàn)闇y(cè)試對(duì)象，從縮減測(cè)試用例規(guī)模和測(cè)試用例執(zhí)行時(shí)間這兩方面對(duì)遺傳算法和改進(jìn)遺傳算法進(jìn)行對(duì)比。

首先，從縮減測(cè)試用例規(guī)模上對(duì)比GA和IGA，實(shí)驗(yàn)結(jié)果如圖1所示。每條曲線表示原始測(cè)試用例數(shù)量與縮減后測(cè)試用例數(shù)量之間的對(duì)應(yīng)關(guān)系。從結(jié)果可以看出，IGA縮減測(cè)試用例后規(guī)模明顯小于GA，且縮減規(guī)模更穩(wěn)定。然后，對(duì)比GA和IGA縮減后的測(cè)試用例集運(yùn)行代價(jià)（時(shí)間），實(shí)驗(yàn)結(jié)果如圖2所示。從結(jié)果可以看出，IGA縮減后的運(yùn)行時(shí)間比GA的運(yùn)行時(shí)間更低。

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

針對(duì)遺傳算法容易陷入局部最優(yōu)解問(wèn)題，本文從選擇算子、交叉算子和變異算子三方面進(jìn)行改進(jìn)，得到了一種改進(jìn)遺傳算法，并將其應(yīng)用在解決測(cè)試用例集縮減問(wèn)題。通過(guò)仿真實(shí)驗(yàn)得出：

（1）改進(jìn)遺傳算法的收斂性?xún)?yōu)于遺傳算法，可以更好的縮減測(cè)試用例規(guī)模。

（2）改進(jìn)遺傳算法縮減測(cè)試用例能更好的降低運(yùn)行代價(jià)。

（3）應(yīng)用改進(jìn)遺傳算法縮減測(cè)試用例后得到的用例集與原測(cè)試用例集相同的錯(cuò)誤檢測(cè)能力。

改進(jìn)遺傳算法可以有效降低測(cè)試用例冗余度，減小了測(cè)試用例規(guī)模，縮短了測(cè)試時(shí)間，并且保證了縮減后的測(cè)試用例有著原測(cè)試用例集的檢錯(cuò)能力。但也存在問(wèn)題，如：采用單點(diǎn)交叉，隨機(jī)基因重組不能保證大概率地生成優(yōu)于父代的個(gè)體。在未來(lái)工作中，筆者將繼續(xù)致力于測(cè)試用例集約簡(jiǎn)的研究。