基于多態蟻群算法的測試用例自動生成

摘 要：提出了一種基于多態蟻群算法的測試數據自動生成方法。該方法使用二進制編碼將輸入數據轉換為位串；然后在蟻群算法的基礎上將蟻群分為三類，據其信息素的不同采用不同的移動準則，重點對偵察蟻和搜索蟻進行功能分析。將局部搜索與全局搜索結合起來，結合路徑的相似度，縮小搜索空間；根據適應度函數確定最好路徑，既解決局部最優化問題，又提高收斂效率。與基本蟻群算法對比，其結果顯示該方法效率優于基本蟻群算法。

關鍵詞：多態蟻群算法； 測試數據； 相似度； 適應度； 信息素

中圖分類號：TP311文獻標志碼：A

文章編號：1001-3695(2009)06-2347-02

doi:10.3969/j.issn.1001-3695.2009.06.104

Automated software test-data generationbased on polymorphic ant colonies algorithm

CHEN Ming-shi， LIU Xiao-jie， LI Tao

(College of Computer Science， Sichuan University，Chengdu 610065，China)

Abstract:

This paper drawled a polymorphic ant colonies algorithm method to generate test-data automatically. This method transferred the data input to bit string in binary coding approach. Based on the ant colonies algorithm， divided the ants into three categories. Different pheromones with different criteria to move， focused the analysis of exploring ant and searching ant. combined local search and global search to explore the optimal solution. With the similarity of the route， it could narrow the search space and increase the convergence rate; with the fitness function， it could find the optimal routes. This method could solve the local optimal problems and improve the efficiency of convergence. Comparing and studying the ant colony algorithm， show that the approach is feasible and superior to the previous in efficiency.

Key words：polymorphic ant colony algorithm; test data; similarity; fitness; pheromone

目前解決網絡安全的方法是計算機免疫^[1]，通過軟件測試可提高軟件安全性。測試用例的自動生成至關重要，若能自動生成測試用例則可以節省整個軟件開發費用的4%。國內外面向路徑的測試數據有隨機法、試探法、靜態法和動態法。鑒于爬山算法、遺傳算法(GA)、模擬退火算法(SA)和模擬退火遺傳算法(SAGA)的局限性^[2]，蟻群中個體間可進行信息交流，故蟻群算法(ACA) [3，4]應用于自動產生測試數據^[5]，能夠解決局部最優，較大程度提高了收斂效率，但蟻群單一、信息素單一、搜索空間龐大、效率仍然不高。本文提出了多態蟻群算法^[6]，利用信息素多態性，不同蟻群進行分工協作。這里蟻群有三類，即偵察蟻、搜索蟻和工蟻。偵察蟻負責局部搜索；搜索蟻對偵察蟻的結果進行統計，縮小了搜索空間；增強蟻群間協作，從而提高了搜索效率，加快收斂速度。工蟻只從已知路徑取得食物并回巢即可，故不對工蟻作討論。

1 測試數據模型

1.1 螞蟻路徑的描述

設輸入Xi(i=1，2，…，n)為二進制編碼，螞蟻路徑有向圖G=(V，E)，節點集V={v1，v2，…，v2N}，有向邊集E = {e1，e2，…，e4N}，其中e1=(v1，v2)，e2=(v1，vN+2)，…，e4N=(v2n，vn+1)。一個含有N條有向邊的序列構成一條路徑，用含有N個節點的序列表示為P(vs，vt)={v1′，v2′，…，vj′，…，vN′}。其中起點vs和終點vt均為v1′(s=t=1，2，…， 2N; j=1， 2，…， N)^[5] 。螞蟻路徑網絡由N層節點組成的有向圖，每層兩個節點分別表示二進制位串取值為0和1的狀態。

1.2 螞蟻移動規則

將蟻群分為偵察和搜索兩類，數量分別為m和n。

針對偵察蟻群：將m個偵察蟻分別放在m個節點上，每個偵察蟻以所在節點(設為vj)為中心，偵察過的x個節點加入禁忌表，在剩下min{m-x，MAXPC}個節點上選擇一個。MAXPC是以節點Vj為中心，以R為半徑，找到的鄰近節點，可通過實驗來選擇MAXPC較優值。以s[i][j](i，j=0，1，2，…，m-1;i≠j)標記在從節點i到j的路徑上^[7]。

s[i][j]=d~ij/dij若節點j在i的MAXPC之內0 否則(1)

其中：d~ij表示以節點i為中心，到其他(m-1)個節點的最小距離，并據此結果，由式(2) (3)分別初始化和更新偵察路徑上的偵察素：

τij（0）=c*s[i][j]若s[i][j]≠0c*d~ij/dij 否則(2)

τ（vk，vk+1）←ατ（vk，vk+1）+（1-α）τ0(3)

這一步為下面的搜索蟻群在進行轉移概率的計算、各路徑上信息素的濃度調整奠定基礎。α為偵察素殘留因子，其值越大，則該螞蟻越傾向于選擇其他螞蟻經過的路徑，螞蟻之間協作性越強。

針對搜索蟻群：螞蟻數目為n，對螞蟻k(k=1，2，…，n)在運動過程中的t時刻，從節點i轉移到節點j的概率pijk（t）為^[8]

pkij=ταij(t)ηβij(t)/∑stabukταij(t)ηβis(t) 若jtabuk，且s[i][j]≠00 否則(4)

其中：β為期望偵察素殘留因子，表示能見度的相對重要性，其值越大，則該狀態轉移概率越接近于貪心規則; 用禁忌表tabuk (k=1，2，3，…，m)來記錄螞蟻k當前所走過的測試路徑，集合隨著tabuk進化過程作動態調整；ηij(t)為啟發函數，其表達式為ηij(t)=1/dij，對螞蟻k而言，dij越小，則ηij(t)越大，pijk(t)也越大。由式(4)，搜索蟻每經過一個節點，結合偵察素，僅需在較小范圍內搜索，大大縮小了搜索規模。每經過一次迭代后，各路徑上信息素的濃度：

τij(t+1)=ρ*τij(t)+(1－ρ)*Δτij若s[i][j]≠0ρ*τij(t)否則(5)

1.3 適應度函數

適應度函數引導算法最終找到覆蓋指定路徑的測試數據。采用Lin等人提出的適應度函數SIMILARITY，這個適應度函數在Hamming距離的基礎上進行展開，能夠很好地衡量兩條給定路徑之間的距離及相似度，從而判斷是否為所選路徑。SIMILARITY（ST）定義如下：

STi-j=M11－j×W1+M21－j×W2+…+Mn1－j×Wn(6)

其中：Mn1－j=1－Sni⊕Snj/Sni∪Snj；Wn=Wn-1×Sn－1i。

定義1 Sni={r | r 是路徑pathi中的一個有序n-級聯分支}。

定義2 pathi與pathj一階距離：Nmi-j=Dmi-j/Smi∪Smj。

定義3 pathi與pathj 的m階相似度：Mmi-j=1-Nmi-j。

定義4 式（6）中的權值Wn定義如下：W1=1，W2=W1*S1i，W3=W2*S1i，…，Wn=Wn－1*Sn－1i。

2 生成測試數據實現步驟

a）初始化各參數。蟻群總數為m+n，節點數m+n；最大迭代數NC，賦初值NC=0。

b）將m只偵察蟻分別放在m個節點中，每只偵察蟻以所在節點i為中心，偵察其他(m-1)個節點，按式(1)計算偵察素，按式(2)初始化相關節點偵察素，更新S[i][j]值。

c）偵察素更新。每只螞蟻對經過的有向邊后按式(3)進行偵察素更新。

d）計算最佳路徑。當每只螞蟻選擇m個節點并完成偵察素更新時，則該螞蟻構造了一條路徑， m只螞蟻構造m條路徑，計算路徑長度， 計算適應度保留最佳路徑。

e）隨機選擇每只搜索蟻的初始位置，并將該位置放入每個搜索蟻對應的tabu表中。

f）按式(4)計算每只搜索蟻k將要轉移的位置，假設為j，上一個位置假設為i，并將j放入搜索蟻k對應的tabu表中，直至每只搜索蟻完成一個循環，得到一個解。

g）計算各搜索蟻的目標函數值Lk(k=1，2，…，n)和適應度函數f(p1，p2，…，pn)，并記錄當前最優解。

h）若達到NC代數或者所求解在最近若干代中無明顯改進，轉步驟k)。

i）按式(5)修改各路徑上的信息素濃度。

j）置Δτij為0，置tabu表為空，NC←NC+1，轉步驟e)。

k）輸出最優解。

3 實驗比較

本文分別用蟻群算法和多態蟻群算法生成DRC災難與恢復系統中的空間管理程序測試數據，記錄產生900個測試數據，所需的時間（s）如圖1所示。



4 結束語

蟻群算法是一種新興的算法，廣泛應用于作業調度^[8]，車輛路徑和大規模集成電路等領域，其應用前景廣泛。本文的創新點在于對基本蟻群算法進行改進，利用信息素的多樣性，對不同的蟻群進行分工，即分別進行局部搜索和全局搜索，縮小了搜索空間，從而提高生成測試數據的效率。

參考文獻：

[1]李濤. 計算機免疫學[M].北京:電子工業出版社，2004.

[2]馬亮，張剛.測試用例自動生成方法的現狀及研究[J].現代電子技術，2008， 31(6):126-132.

[3]DORIGO M， MEMBER S， GAMBARDELLALM. Ant colony system: a cooperative learning approach to the travelling salesman problem [J]. IEEE Trans on Evolutionary Computation，1997，1(1):53-66.

[4]MICHAEL C C，McGRAWG. Generating software test data by evolution [J]. IEEE Translations on Software Engineering， 2001， 27(12):1085-1110.

[5]傅博．基于蟻群算法的軟件測試數據自動生成[J].計算機工程與應用，2007，43(12):97-99.

[6]徐精明，曹先彬，王煦法.多態蟻群算法[J].中國科學技術大學學報，2005， 35(1):59-65.

[7]龔本燦，李臘元，蔣廷耀，等.基于局部優化策略求解TSP的蟻群算法[J].計算機應用研究，2008，25(7)：1974-1976.

[8]楊劍峰.蟻群算法及其應用研究[D].杭州:浙江大學，2007.