基于遺傳算法的測試用例自動生成技術研究

馬志兵　余榮學　周麗平

摘 要 本文對應用遺傳算法解決測試用例生成過程中的關鍵技術進行了分析，在突變因子選擇、染色體編碼和適應度函數設計等方面進行了分析、改進，最后結合經典算例對改進進行了驗證。

【關鍵詞】測試數據自動生成 GA 控制變異位置 改進自適應遺傳算法

1 引言

遺傳算法作為一種基于自然選擇原理和遺傳機制的通用搜索算法，與其它搜索算法的不同之處在于它在整個搜索空間隨機采樣，按一定的評估策略對每一樣本評價，并采用特定的算子進行樣本優化，直至產生最優解。本文闡述了用遺傳算法作為核心搜索算法生成軟件測試數據的方法和技術，對突變因子選擇、編碼策略和評價函數構造等問題進行了分析和改進，最后通過經典三角形判別問題檢驗了改進算法的有效性和使用效率。

2 遺傳操作

2.1 編碼策略

遺傳算法工作于參數的編碼而非參數本身，要求把問題的解空間表示為在某個有限字母表上的有限長度的串.因此用遺傳算法生成測試數據時，首要的問題是尋求適當的映射方式f，使得被測程序的輸人參數{x1，x2...xn}， 能夠表示成一種適當的編碼形式：

f：{x1，x2...xn}→{cI，c2，.. ，cn}

遺傳算法在運行時，遺傳算子g對參數編碼進行操作，改變其結構，形成新的編碼：

g：{cI，c2，.. ，cn}→ {cI`，c2`，.. ，cn`}

f逆映射f-l解碼得輸人參數的當前值 ，{x1`，x2`...xn`}即

f-1：{cI`，c2`，.. ，cn`}→ {x1`，x2`...xn`}

如果當前參數值{x1`，x2`...xn`}不滿足終止條件，遺傳算子g將重復上述過程，直至找到目標參數值。參數值到編碼的映射f的選取應遵循以下幾個原則：

（1）輸人參數所能取得的任何值都應存在相應的唯一編碼；

（2）任何一個編碼都應存在唯一的參數值與之對應；

（3）選擇使問題得以自然表達的最小字母表進行編碼；

（4）編碼方法應和問題本身的相關性大、結合緊密。

2.2 遺傳策略

通過遺傳算法尋找最優解時，能夠較快地逼近目標值，但是從逼近目標值到最終找到目標值這一步跨越是較為艱難的，所花費的代價甚至比前面逼近的過程還要大。通過對交叉算子和突變算子的改進，來提高遺傳算法的搜索效率，避免陷入局部最優解。

2.2.1 交叉算子

最簡單的交叉算子是單點交叉，它是在種群中任選2個個體，并在個體位串上隨機選取一個交叉點，然后將2個位串的尾部互換，形成2個新的個體。當參數個數增多，位串長度加長時，僅采用單點交叉，位串的結構改變很小，不利于新信息的引入，導致搜索效率降低。為此設想對交叉算子做如下形式的改進：

（1）增加交叉點。變單點交叉為多點交叉。多點交叉較之單點交叉總體效率取得了一定的提高，但也存在著明顯的問題：由于交叉點是隨機確定的，因此當交叉點在整個位串上分布不均勻，特別是在交叉點過分集中于某一個或少數幾個參數的位串上時，交叉操作對位串上，從而消除當突變點過分集中于少數參數的位串時，突變操作對這些位串破壞過大，而多數參數的位串卻無法引入新的信息所造成的不利影響。

（2）控制突變位置。實驗中發現，用遺傳算法生成測試數據能夠較快地逼近參數的目標值，然而實現從逼近目標值到最終找到目標值這一步決定性的跨越卻是較為艱難的，所花費的代價甚至比前面逼近的過程還要大，此時如何提高搜索效率顯得尤為重要.爬山法中探索性搜索的思想給我們帶來了很大的啟發，我們有意識地控制使參數位串上最不重要的幾位（位串的末幾位）發生突變 ，這相當于給參數的值增加或減少了一個小的步長。從而有可能以較小代價找到參數的目標值。因此我們在遺傳操作時設定一閥值p，若某一染色體的適應值大于p，說明此染色體逼近目標值。那么使得此染色體低位發生突變。按如下公式進行變化：

i=random（n）

pos=

其中p為給定的閥值，對于不同的適應度函數p的值不同，往往把p設為最接近目標路徑的適應值；f為變異染色體的適應值；n為參數個數；L為給定的單個參數的編碼長度；a根據情況取2—L之間的值。

2.2.2 突變方式

M.Srinivas提出的自適應遺傳算法中，交叉率Pc和變異率Pm是基于個體的適應值來自適應地進行改變。但該算法僅對群體處于進化后期時比較合適。在本文改進的自適應遺傳算法中，對應于群體中最大適值的個體的交叉率和變異率分別取為Pc2和Pm2，而在基本的自適應遺傳算法中最大個體的交叉率和變異率為0。這就相應地提高了群體中表現優良的個體的交叉率和變異率，使它們不會處于一種近似停滯不變的狀態。交叉率和變異率的改進自適應公式如下：

Pc1 =

Pm1 =

fmax代表群體中最大適值；favg代表每代群體的平均適應值；f'代表要交叉的兩個個體中較大的適值；f'代表要變異個體的適值。Pc1、Pm1分別代表個體的交叉率和變異率。

運用自適應遺傳算法的一個實際問題是，最優個體仍然會以較大的交叉率和變異率進行遺傳操作，從而較好的個體被破壞。本文采取最優保存策略來保留最優個體，在選擇前或選擇后保留當前最優解的遺傳算法最終能收斂到全局最佳值。最優保存策略可保證當前的最優個體不會被交叉、變異等遺傳運算破壞，這是本文改進的自適應遺傳算法收斂性的一個重要保證條件。

3 適應度函數的設計

適應函數的優劣將直接影響遺傳算法解決問題的效率。好的評價函數應該更好地體現背景知識，從而更有利于引導算法朝向更優的解空間搜索。在用遺傳算法生成測試數據這一問題上 ，我們的目標是構造一個能更好地評價所生成的測試數據的優劣，并能引導算法最終找到覆蓋指定路徑的測試數據的函數。

利用海明距離來做評價函數的方法，在被測函數單元內部的各個分支點前和分支內部，通過函數插裝的方法分別插入一個分支函數。該函數通過一個boolean型數組path來記錄執行過程中是否執行過此分支。如果程序執行過此分支，則數組path中相應位置的值為T，否則為F。這樣對不同的路徑，數組path有不同的值。這樣如果事先選定一條目標路徑，求能滿足它的測試數據。則可以有一組有序的T、F符號集合唯一標識它，假定其為α；用某組測試數據執行被測函數，可以得到一個boolean型數組path標識其執行的實際路徑，假定其為 β，則實際路徑和目標路徑之間的差異可如下表示：

fit=

same（α，β）：數組α，β中對應位置為T的個數。

getlarge（α，β）：數組α，β中值為T的個數。

fit稱為相似度，表示目標路徑和實際路徑之間的相似程度，越接近 1，表示測試數據越滿足要求，故把fit作為適應度函數。

4 對比分析

為了對比客觀，分別采用基本遺傳算法、控制突變位置法和自適應遺傳算法生成測試數據，基本參數指標如表1所示。

對于等邊三角形問題，我們令控制突變位置參數p=0.8，a=3；改進的自適應遺傳算法中Pc為0.8，Pm為0.08，Pc2為0.1，Pm2為0.01。

我們分別用基本遺傳算法（BGA）、控制突變位置法（CGA）和自適應遺傳算法（AGA）生成10次等邊三角形用例，記錄其產生目標用例的代數和執行時間，三種方法的平均代數和每代的平均執行時間如表2。

從表2數據可以看出，控制變異位置法和改進的自適應遺傳算法由于包含了較多的計算過程，因此產生新一代群體時用的時間比基本遺傳算法要長；控制變異位置法搜索到目標值所經歷的群體代數最少，提高了搜索效率。

5 小結

本文對遺傳算法用于生成測試用例的方式進行了改進。為了提高初始種群的適應度，引入了局部加速方法；針對用例生成的大空間搜索問題，引入了變長染色體編碼策略；針對測試程序的參數個數和編碼長度不同，對遺傳算子進行了改進；介紹了控制變異位置法和改進的自適應遺傳算法，來提高遺傳算法的搜索效率。通過經典三角形問題實驗證明改進方法有效，有利于提高種群的搜索效率。

參考文獻

[1]莢偉，高仲儀.基于遺傳算法的軟件結構測試數據生成技術研究[J].北京航天航空大學學報，1997，23（1）.

[2]王小平，曹立明.遺傳算法——理論、應用與軟件實現[J].西安：西安交通大學出版社，2001.

作者單位

1.中國電波傳播研究所 山東省青島市 266071

2.青島理工大學琴島學院 山東省青島市 266106