蟻群遺傳混合優(yōu)化算法在面向路徑測試數(shù)據(jù)自動生成中的應(yīng)用

摘 要：探討一種有效的面向路徑的測試數(shù)據(jù)自動生成的方法，有著很現(xiàn)實(shí)的研究意義。試探法是測試數(shù)據(jù)自動生成的重要方法，遺傳算法和蟻群算法等現(xiàn)代優(yōu)化算法是試探法的代表。遺傳算法在實(shí)際應(yīng)用中，容易產(chǎn)生早熟收斂的問題，切在進(jìn)化后期搜索效率較低；蟻群算法卻可以擺脫局部最優(yōu)點(diǎn)，抑制遺傳算法的早熟現(xiàn)象，但由于初期信息素匱乏，導(dǎo)致搜索效率較低，遺傳算法的變異操作能夠增加搜索的隨機(jī)性、快速性和全局收斂性。

關(guān)鍵詞：軟件測試；蟻群算法；遺傳算法；信息素

中圖分類號：TP311.52；TP18

作為軟件質(zhì)量保證的重要手段，軟件測試在這方面越來越發(fā)揮著其他方法不可替代的作用。

從是否需要執(zhí)行被測軟件的角度出發(fā)，可以將軟件測試分為靜態(tài)測試和動態(tài)測試兩種。動態(tài)測試在軟件測試實(shí)際中占比例較大，是軟件測試的重要環(huán)節(jié)，其關(guān)鍵是測試數(shù)據(jù)的生成。動態(tài)測試又可根據(jù)是否針對系統(tǒng)的內(nèi)部結(jié)構(gòu)和具體算法進(jìn)行測試而劃分為黑盒測試和白盒測試兩種。白盒測試要求對被測程序的結(jié)構(gòu)特性做到一定程度的覆蓋。其中，路徑覆蓋是一種相對比較強(qiáng)的覆蓋標(biāo)準(zhǔn)，即要求生成的測試數(shù)據(jù)盡可能地覆蓋所有程序路徑。但是，實(shí)際中往往會出現(xiàn)這樣的情況：多個測試用例執(zhí)行的是同一條程序路徑，而有的程序路徑則從未被執(zhí)行過。因此，探討一種有效的面向路徑的測試數(shù)據(jù)自動生成的方法，有著很現(xiàn)實(shí)的意義。

目前，常見的面向路徑的測試數(shù)據(jù)生成方法可以分為四類：隨機(jī)法、試探法、靜態(tài)法和動態(tài)法。由于試探法和動態(tài)法具有極大的優(yōu)越性，因此，目前己經(jīng)成為人們的研究熱點(diǎn)。遺傳算法是試探法的一種，作為一種強(qiáng)健的搜索方法，它在解決大空間、多峰、非線性、全局優(yōu)化等高復(fù)雜度問題時顯示了獨(dú)特的優(yōu)勢和高效性，受到軟件測試研究人員的重視。

遺傳算法在實(shí)際應(yīng)用中，容易產(chǎn)生早熟收斂的問題，切在進(jìn)化后期搜索效率較低。蟻群算法卻可以擺脫局部最優(yōu)點(diǎn)，抑制遺傳算法的早熟現(xiàn)象，但由于初期信息素匱乏，導(dǎo)致搜索效率較低，遺傳算法的變異操作能夠增加搜索的隨機(jī)性、快速性和全局收斂性。為了研究其適應(yīng)性，選擇三角形類別判定程序作為測試實(shí)例予以仿真實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果證明本文提出的算法可以在一定程度上提高測試數(shù)據(jù)生成的效率和質(zhì)量。

1 混合算法分析與設(shè)計

遺傳算法（Genetic Algorithm）是模擬達(dá)爾文生物進(jìn)化論的自然選擇和遺傳學(xué)機(jī)理的生物進(jìn)化過程的計算模型，是一種通過模擬自然進(jìn)化過程搜索最優(yōu)解的方法。其主要缺陷是容易產(chǎn)生早熟收斂問題。蟻群算法是一種基于群體的啟發(fā)式算法，可以抑制遺傳算法的早熟現(xiàn)象，缺少初始信息素是其主要缺點(diǎn)。近年來，一些學(xué)者嘗試將遺傳算法與蟻群算法相融合，提出混合遺傳蟻群算法（Genetic Algorithm and Ant Algorithm，GAAA）。GAAA算法針對蟻群算法初始信息素缺乏的缺點(diǎn)，采用遺傳算法生成初始信息素分布，利用蟻群算法求得精確解。然而，該算法需要進(jìn)行多次實(shí)驗(yàn)以確定以何規(guī)則將遺傳算法的求解結(jié)果轉(zhuǎn)換為蟻群算法的信息素初值。GAAA應(yīng)用于面向路徑的測試數(shù)據(jù)生成有一定限制。

蟻群系統(tǒng)算法是蟻群算法的改進(jìn)。在蟻群算法中加入局部信息素的更新，可以對信息素產(chǎn)生一種負(fù)反饋機(jī)制，即螞蟻所走的路徑上，信息素反而在衰減，這樣就增加了其他路徑在下一次循環(huán)中被選擇的機(jī)會，有效的避免算法進(jìn)入局部最優(yōu)。將遺傳算法引入蟻群系統(tǒng)算法，形成混合蟻群遺傳算法（Ant Colony System-Genetic Algorithm，ACSGA），可以兼顧兩個算法的優(yōu)缺點(diǎn)，提高優(yōu)化時間效率和精確度。

本研究將混合蟻群遺傳算法應(yīng)用到面向路徑測試數(shù)據(jù)自動生成領(lǐng)域。算法流程如如圖1所示：

ACSGA模型描述如下：

（1）遺傳算法一般采用二進(jìn)制編碼規(guī)則，但由于測試數(shù)據(jù)經(jīng)常是多個輸入值，因此采用基于二進(jìn)制規(guī)則改進(jìn)的多參數(shù)級聯(lián)編碼規(guī)則，即：

解碼時，只需將原始總碼切為n段、長度為m的碼組，然后再進(jìn)行反算即可。

（2）狀態(tài)轉(zhuǎn)移規(guī)則如式（1）所示： （1）

2 模擬實(shí)驗(yàn)

勾股定理判斷三角形問題是一個經(jīng)典的路徑判別實(shí)例，描述如下：

該實(shí)例很容易改造成路徑測試程序，如圖2所示：

該程序的控制流圖如圖3所示：

ACSGA算法中，根據(jù)經(jīng)驗(yàn)，遺傳參數(shù)均勻雜交率設(shè)定為0.8，每個參數(shù)的變異率為0.1，種群規(guī)模設(shè)為60，遺傳最大代數(shù)20000，螞蟻數(shù)m=30，其他參數(shù)：α=1，β=2，ρloaclupdate=0.1，為了進(jìn)行對比，采用同樣的參數(shù)，用遺傳算法和蟻群算法進(jìn)行迭代計算。由結(jié)果可知，蟻群算法要比遺傳算法優(yōu)秀很多，混合遺傳算法的平均迭代次數(shù)最少，但是混合遺傳算法并不比蟻群算法優(yōu)秀太多，這可能跟參數(shù)設(shè)置有關(guān)。進(jìn)一步研究中，可以分析參數(shù)設(shè)置對于結(jié)果的影響。

3 小結(jié)

本研究將蟻群算法引入遺傳算法，混合成遺傳蟻群算法。進(jìn)行必要的改造后，將遺傳蟻群算法用于面向路徑的測試數(shù)據(jù)生成。以經(jīng)典的勾股定理判別三角形問題作為測試程序，檢驗(yàn)算法的優(yōu)劣。

仿真實(shí)驗(yàn)中，通過限制迭代次數(shù)的方式，觀察混合遺傳蟻群算法在生成測試數(shù)據(jù)時，與普通遺傳算法和蟻群算法的對比，結(jié)果表明混合遺傳蟻群算法平均迭代次數(shù)最少，并能夠較早的生成目標(biāo)路徑測試數(shù)據(jù)，但可能由于參數(shù)設(shè)置的問題，并不比蟻群算法優(yōu)秀太多。進(jìn)一步研究中，可以分析參數(shù)設(shè)置對于結(jié)果的影響。

參考文獻(xiàn)：

[1]Holland J. Adaptation in Natural and Artificial Systems[M].Michigan：University of Michigan Press，1975.

[2]Berndt D， Fisher J， Johnson L. Breeding Software Test Cases with Genetic Algorithms[C].（Proceedings of the 36th Hawaii International Conference on System Sciences，2003）.

[3]單錦輝，王戟，齊治昌.面向路徑的測試數(shù)據(jù)自動生成方法述評[J].電子學(xué)報，2004，32（1）：109-113.

[4]汪浩，謝軍凱，高仲儀.遺傳算法及其在軟件測試數(shù)據(jù)生成中的應(yīng)用研究[J].計算機(jī)工程與應(yīng)用，2001，37（12）：64-68.

作者簡介：易敏捷（1981.11-），女，江蘇海門人，碩士，工程師，研究方向：軟件測試。

作者單位：江蘇自動化研究所，江蘇連云港 222000