一種面向對象測試用例自動生成的混合算法

摘要：遺傳算法(GA)在測試用例生成方面是一種實用的算法，但是其自身也存在的局限性，如過早收斂、優化效率低等問題。通過引入粒子群算法(PSO)，使每一個測試用例在局部區域中再次尋找最優值，以此改進整體算法搜索最佳值的能力，避免過早收斂、優化效率低的問題。與此同時，針對面向對象測試的特點，如封裝性等，將混合算法進行適當的改進，滿足在不同環境中重復使用類的要求。

關鍵詞：軟件測試；測試數據；遺傳算法；粒子群優化

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

文章編號：1001－3695(2008)03－0786－03

0引言

軟件測試是一個非常耗費資源的活動，其中比較重要的工作就是找一組合適的測試集合進行測試，以此達到測試目的。由于當前軟件系統的不斷擴大，手工生成測試案例既不科學、也不可能，這就需要計算機進行測試用例的自動生成。關于這方面的研究，早在20世紀80年代D. Bird等人[1]采用隨機法自動生成測試用例，可以不受限制地迅速隨機生成大量的測試數據。但生成的測試數據集，仍然是一個龐大的集合，沒有針對性。隨著人工智能技術的不斷發展，遺傳算法的優越性不斷地體現，在文獻[2~5]中提出了如何將遺傳算法應用到生成最小測試集合中，并在文獻[4]中提及如何將目標轉換為覆蓋的規則；在文獻[5]中提及如何在遺傳算法中設計一個較合適的適應度函數。但是，由于遺傳算法本身存在的局限性，如過早收斂、優化效率低等問題，該遺傳算法只能在短時間內找到接近全局最優解的近似解，而不能保證收斂到全局最優解。解決這一問題的有效方法就是將其他優化算法融入到遺傳算法中，以此來改進其不足。粒子群算法就是一種有效的算法。

粒子群算法(PSO)是基于群體智能理論的優化算法，通過群體中粒子間的合作與競爭產生的群體智能指導優化搜索。其優勢是算法收斂速度快，設置參數少。粒子群算法(PSO)最早是由美國的Eberhart等人[6]在1995年提出的。文獻[7]對ω因子所起的作用進行研究，發現較大的ω有利于跳出局部最小點，而較小的ω值有利于算法收斂，因此提出了自適應調整的策略APSO(adaptive particle swarm optimization)，即隨著算法迭代的進行，線性遞減ω的值。該算法的缺點是易于陷入局部最優，搜索精度不高。之后，Eberhart等人[8]對粒子群算法加權ω作了進一步的優化。

遺傳算法已經廣泛地應用到在面向過程程序的測試中[1~8]，但是如何將遺傳算法更合理地應用到面向對象程序的測試中，還需要進行研究。本文就如何將遺傳算法應用到面向對象程序的測試中進行了討論。相對于以往的程序設計，面向對象程序具有封裝性、多態性和繼承性三大特點，它對測試的要求也不同。雖然在面向對象程序的測試中它與面向過程的程序有許多不同之處，但是同樣存在測試集選取的問題。文獻[9]分析了面向對象程序與面向過程程序的異同點，將遺傳算法應用到面向對象的類測試中，提出了一個有效的算法。

本文針對上述兩種算法各自的優勢和劣勢，對文獻[9]中的算法進行了改進，并在其基礎上加入粒子群的算法。具體工作如下：

a)在對粒子群算法的研究中，發現粒子群算法通過群體的合作提高了搜索的效率，但也正是由于其群體搜索的高效率，而導致算法易陷入局部最優。所以粒子群算法是局部搜索最高效的搜索算法。由于這一特性，與遺傳算法相結合，將遺傳算法的篩選、變異、交叉和粒子群算法的自更新的特性結合在一起，提高混合算法的特性。

b)對于文獻[9]提出的算法，本文分析了其優缺點，并針對它的不足提出了改進方法，結合到算法中。

c)由于在面向對象的程序中，許多情況與一般測試不同，本文運用上述混合算法的思想，在面向對象的類測試中提出了切實可行的應用設想。

1相關算法

1．1遺傳算法

遺傳算法(GA)開始時首先隨機地產生一些染色體(欲求解的問題的候選解)，計算其適應度；然后根據適應度對諸染色體進行選擇、交換、變異等遺傳操作，剔除適應度低(性能不佳)的染色體，留下適應度高(性能優良)的染色體，從而得到新的群體。新群體的成員是上一代群體的優秀者，繼承了上一代的優秀基因，因而明顯優于上一代。GA就這樣反復迭代，向著更優解的方向進化，直至滿足某種預定的收斂條件。

算法的大致步驟如下：

a)初始化。設置進化代數計數器t=0；設置最大進化代數T，計算精度；隨機生成M個個體作為初始群體P(0)。

b)個體評價。計算群體中各個個體的適應度。

c)選擇運算。將選擇算子作用于群體。

d)交叉運算。將交叉算子作用于群體。

e)變異運算。將變異算子作用于群體。群體經過選擇、交叉、變異運算之后得到下一代群體。

f)終止條件判斷。若t≤T沒有達到計算精度，則t=t+1，轉到步驟b)；否則，以進化過程中所得到的具有最大適應度的個體作為最優解輸出，終止計算。

幾個主要操作如下：

a)選擇運算。選擇操作是根據染色體的適應度，在群體中按一定概率選取可作為父體的染色體。具體地說，就是根據各個個體的適應度，按照一定的規則或方法，從第t代群體P(t)中選擇出一些優良的個體遺傳到下一代P(t+1)中。選擇操作一般有輪盤賭選擇、錦標賽選擇、排序選擇等。

b）交叉運算。交叉操作是按一定概率隨機地選擇染色體對，然后對染色體對按一定概率隨機地交換基因，以形成新的子染色體。交叉操作一般有簡單交叉、啟發式交叉、算術交叉等。

c)變異運算。變異操作是按一定概率隨機地改變某個染色體的基因值。具體地說，就是對群體內的每一個個體，以某一概率(mutation rate，變異概率)改變某一個或某一些基因座上的基因值。變異操作主要有邊界變異、均勻變異、基于染色體的非均勻變異。

1．2粒子群算法

粒子群優化(particle swarm optimization，PSO)算法是由Eberhart等人[6，8]于1995年提出的一種隨機全局優化算法。PSO算法不是依靠個體的自然進化規律，而是對整個生物群體的社會行為進行模擬，即利用信息共享機制，使得個體間可以相互借鑒經驗，從而促進整個群體的發展。

在PSO算法中，每個優化問題的潛在解均可以想象成D維空間上的一個點，稱之為粒子(particle)。 粒子在搜索空間中以一定的速度飛行，這個速度根據它本身的飛行經驗和同伴的飛行經驗來動態調整。所有的粒子均有一個被優化的函數決定的適應值(fitness value)。粒子在飛行過程中所經歷過的最好位置，就是粒子本身找到的最優解，稱為個體極值(pbest)。這個可以看做是粒子自己的飛行經驗。除此之外，每個粒子還知道到目前為止整個種群中所有粒子發現的最好位置，稱為全局極值(gbest)。這個可以看做是粒子同伴的飛行經驗。每個粒子均通過上述兩個極值不斷更新自己，從而產生新一代群體。實際操作中通過由優化問題所決定的適應值(fitness value)來評價粒子的“好壞”程度。顯然，每個粒子的行為就是種群追隨著當前的最優粒子在解空間中搜索。

Eberhart和Kennedy[6]最早提出的PSO算法采用式（1）所示的更新粒子狀態:

vid=vid+c1r1(pid-xid)+c2r2(pgd-xid)(1)

xid=xid+vid(2)

其中:學習因子c1和c2是非負常數；r1和r2是介于[0，1]之間的隨機數。

vid∈[-vmax，Vmax]；vmax是常數，根據問題人為設定。迭代終止條件根據具體問題一般選為最大迭代次數或(和)粒子群迄今為止搜索到的最優位置滿足預定最小適應值。

文獻[8]對基本粒子群算法提出改進，即將式(1)修改為

vid=ωvid+c1r1(pid-xid)+c2r2(pgd-xid)(3)

其中：ω稱為慣性因子。

PSO算法是一種全局優化算法。其計算步驟如下：

選定PSO種群規模m；

設x[i]為種群中第i個粒子的位置；

設fitness[i]為第i個粒子的適應值；

設v[i]為第i個粒子的速度；

設gbest為種群最好粒子的標號；

設pbest[i]為第i個粒子自身搜索到的最好點位置；

設pbestfitness[i]為第i個粒子自身搜索到的最好適應值，即pbest[i]處的適應函數值。

a）(初始化) 對于每一個種群中的粒子i，i =1，2 ，…，m

(a)隨機初始化x[i];

（b）隨機初始化v[i];

（c）計算fitness[i]，并以此初始化Pbestestfitness[i];

(d)以種群中 最好適應值的粒子標號初始化gbest;

(e)以x[i]初始化Pbest[i]。

b）循環迭代，直到滿足PSO終止條件

(a)選擇算法控制參數ω;

(b)對每個粒子，計算其適應值fitness[i];

若fitness[i]

(c)搜索gbest值;

若pbestestfitness[i]

(d)對每個粒子，依據式(2)(3)更新v[i]和x[i]的值。

2現有混合算法分析

GA算法和PSO算法都是基于種群的算法，它們在解決不同領域的問題中均被證明是有效的。但是，上述兩種模型都有各自的優勢與不足。在GA算法，基因將通過不斷的篩選，通過優質基因不斷變異和交叉來提升自己的品質。但是一旦一個基因的適應度不高，那么它將不會被選中，它會被舍棄，它的一些有用的經驗也將同時失去。而在學習以往經驗這方面，PSO算法可以在不斷地尋求最佳解的過程中積累經驗，可以不斷學習。但是，由于PSO沒有基因篩選的過程，PSO算法也很有可能將資源浪費在一些品質不佳的基因上。正由于PSO算法的相互影響，增強了尋找最優解的能力，而GA卻缺乏精確找到最優解的能力，擅長于尋找一個次優解。如果能將兩種算法融合在一起，用自己的長處來彌補對方的不足，這樣將會有更好的表現[10，11]。

在以往的文獻中，也提到利用混合算法來提升算法性能。簡單的混合算法如用GA算法來初始化PSO算法的初始種群，或者用PSO算法來初始GA的初始種群。但文獻[12]證明，前者的策略只能獲得一點性能的提升，后者則沒有一點性能的提升。

文獻[11]中提出一種新的混合算法。該算法從PSO算法中結合了標準的速度和位置更新，同時它又從GA算法中繼承了選擇、交叉和變異等操作，增加了一個參數Ψ來決定測試集合中能進行選擇、交叉和變異操作的比例。Ψ的取值為0~1。

設每一代的種群總數為N，在每一代的集合中，在進行適應值的計算之后，在N×Ψ之后的將被舍棄，余下（N×(1-Ψ)）的將對自己的速度和位置進行更新，成為新一代集合的成員。同時被保留的成員通過自身的選擇、交叉和變異來生成另外的成員。兩者共同成為新的一代成員，如圖1所示。

3混合算法在面向對象類測試中的應用

3．1遺傳算法的改進

文獻[6]提出了將遺傳算法引入類測試的方法，認為類測試的難點是由于編寫的類將在以后各種不同的環境中，因此，在測試中要模擬足夠的環境來進行測試。這里的環境是指，通過不同順序調用類成員方法來形成不同類成員變量的情況，被測試的類將在不同的環境中執行。由于在面向對象的程序中，采用成員方法的調用，在面向對象類測試中，遺傳算法中的基因是指類成員方法不同的調用序列。

文獻[9]中的算法存在以下兩個不足：

a)在編碼操作中，將遺傳算法中的染色體分成三個部分，即類的構造、類狀態的設置、類的測試。這三者的順序是固定的。但正是由于這三個組成部分的順序是固定的，這就會遺漏以下一種情況：

*a=A()， a.f()， *b=B(a)， b.f()…b.underTest()

A和B是兩個類，B的方法underTest()為待測試的方法。從上述式子可以看出，在b進行構造函數之前，a先調用了f方法，在a的屬性發生變化后再進行B類的構造，這不能完全滿足順序是固定的。

b)在選擇操作中，根據適應度函數計算出每一個染色體，選出分界點，適應度大的保留，適應度小的去除。這樣做的缺陷是選擇操作過于簡單，無法避免遺傳算法早熟的現象，很難找到全局最優解。

針對上述問題，本文將從以下幾個方面對文獻[6]中的算法進行改進:

a)不在全局范圍內固定染色體三大部分的順序，而是針對某一個類規定它的順序，即每個類在使用前先構造，而不規定只有將所有的類構造好后才能進行后續方式，這樣就避免上述所說的遺漏情況。

b）在選擇操作時，考慮到會出現精英基因的情況，在算法中加入精英策略，即不改變當前一代中的精英基因，讓其保留到下一代。

c)同時，在面向對象類測試中應用第三部分中提出的混合算法的思想，對上述思想進行修改，使之能適應類的測試。

3．2遺傳—粒子群混合算法

根據上述存在的缺陷以及改進的方法，本文提出以下算法。為了更清晰地解釋算法，先提出以下定義：

定義1適應度高的基因中存在較好的基因片斷（較好的類調用順序），即較好的經驗，可以供自己或其他基因學習。

定義2基因的速度是指較好的基因片斷，每次的更新可以向其他基因學習或自學習，形成新的基因片斷。基因速度的更新主要分為兩步，即速度的更新和速度的精簡。速度的更新是指將適應度高的基因的速度與自己融合在一起，組成新的速度。但是，由于是兩者相互融合的，可能新的速度比較長，這就需要進行下一步——速度的精簡。速度的精簡是指在不降低適應度的條件下，刪除基因中的片斷。具體算法是依次刪除基因中的每一個元素，然后計算它的適應值。如果適應值沒有降低，就舍棄該元素，直到最精簡的調用序列。

定義3基因的位置即指類成員方法調用序列，每次的更新可以重新生成類成員方法調用的序列。基因位置的更新可以是將自己更新后的速度作為自己基因的位置。

定義4基因的融合指將兩段不同的基因片斷結合在一起形成新的基因，即新的類成員方法調用序列。結合的方式可以是順序拼接，也可以用隨機插入的方式進行拼接。在隨機插入時應注意方法調用的順序，應當先構造，后使用。

算法如下：

a）初始化目標覆蓋路徑；

b）初始化初始種群集合，定義為Q，種群數為N；

c）初始化種群中每個基因的速度；

d）如果目標路徑全部覆蓋或測試超出時限，則跳轉至p）；

e）確定子目標覆蓋路徑；

f）設置測試次數為0；

g）如果子目標路徑全部覆蓋或測試次數超出，則跳轉至d）；

h）計算種群中每個基因的適應度；

i）如果子目標路徑全部覆蓋，則跳轉至d）；

j）篩除出適應度較好的基因，定義為集合T；

k）對T進行選擇、交叉、變異，補充到Q中；

l）更新T中每一個基因的速度值；

m）更新T中每一個基因的位置；

n）測試次數自增；

o）跳轉至d）；

p）輸出種群Q。

上述算法結合了遺傳算法和粒子群算法，主要改進在于使算法適應面向對象測試的特性。在b）和c）中，可以采取隨機生成初始的種群，以及每個基因的速度值。在j）中，算法將根據設置的參數Ψ，舍棄基因中后N×Ψ個，其余的保留到集合T中。這樣可以避免PSO算法中可能將資源浪費到品質差的基因中。k）中采用傳統的GA算法，通過篩選、變異和交叉產生新的基因，補充到Q中。l）和m）是采用了PSO算法的思想，讓基因自學習，自己改進自己的基因。但由于算法是用于面向對象的測試，這里只是引用PSO的思想。

4結束語

遺傳算法作為一種測試集生成策略在許多文章中被提及，但是對于面向對象程序測試集生成中現有文章沒有很好地解決遺傳算法自身的缺陷，如過早收斂、優化效率低等問題。本文通過引入粒子群算法（PSO），在遺傳算法生成測試結果后繼續采用粒子群算法來加強每個測試用例的區域搜索能力，力圖獲得最優解，以此彌補遺傳算法自身的缺陷。與此同時，本文在提出的混合算法中，又根據面向對象程序的特點，在類測試的這一層，改進了上述的混合算法，明確提出了自己的算法，使之能應用到類測試中。在今后的工作中，實現上述算法，應用到實踐中去將是工作的重點。

參考文獻：

［1］BIRD D，MUNOZ C.Automatic generation of random selfchecking test cases[J].IBM System J，1983，22(3):229－245.

[2]STHAMER H.The automatic generation of software test data using genetic algorithms[D].Pontyprid， Wales， Great Britain:University of Glamorgan，1996.

[3]MICHAEL C，McGRAW G.Automated software test data generation for complex programs[C]//Proc of the 13th IEEE International Conference on Automated Software Engineering (ASE’98).Washington DC:IEEE Computer Society，1998:136146.

[4]PARGAS R，HARROLD M J，PECK R.Testdata generation using genetic algorithms[J].Journal of Software Testing， Verifications， and Reliability，1999(9):263－282.

[5]BARESEL A，STHAMER H，SCHMIDT M.Fitness function design to improve evolutionary structural testing[C]//Proc ofGenetic and Evolutionary Computation Conference(GECCO2002).San Francisco:Morgan Kaufmann Publishers，2002:13291336.

[6]KENNEDY J，EBERHART R.Particle swarm optimization[C]//Proc ofIEEE Int Conference Neural Networks.Perth:[s.n.]，1995:19421948.

[7]ARTHUR W B，HOLLAND J H，LEBANON B，et al.Asset pricing under endogenous expectations in an artificial stock market[C]//Proc of Santa Fe Stadies in the Sciences of Complexing，1996:14－44.

[8]EBERHART R C，SHI Y.Particle swarm optimization developments， applications and resources[C]// Proc of Congress on Evolutionary Computation.Piscataway，Seoul， Korea:IEEE Service Center，2001:81－86.

[9]TONELLA P.Evolutionary testing of classes[C]//Proc of ISSTA’04.New York:ACM Press，2004:119128.

[10]ANGELINE P J.Evolutionary optimization versus particle swarm optimization:philosophy and performance differences[C]//Proc of the 7th Internation Conference on Evolutianary Programming VII.London，VK:Springer，1998:601－610.

[11]EBERHART R C，SHI Y.Comparison between genetic algorithms and particle swarm optimization[C]//

Proc of the 7th Annual Conference on Evolutionary Programming.Berlin:Springer，1998:611－616.

[12]ROBINSON J，SINTON S，RAHMATSAMII Y.Particle swarm， genetic algorithm，and their hybrids:optimization of a profiled corrugated horn antenna[C]//Proc of IEEE Antennas and Propagation Society International Symposium and URSI National Radio Science Meeting.San Antonio， TX:IEEE，2002:314－317.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”