基于遺傳算法的路徑測(cè)試數(shù)據(jù)自動(dòng)生成研究

摘 要：針對(duì)遺傳算法在運(yùn)算過(guò)程中產(chǎn)生的早熟問(wèn)題，提出一種自適應(yīng)動(dòng)態(tài)優(yōu)化策略（SAOGO），用以自動(dòng)生成測(cè)試數(shù)據(jù)。通過(guò)優(yōu)化變異概率等手段，實(shí)現(xiàn)了路徑測(cè)試數(shù)據(jù)的自動(dòng)生成。將Triangle（三角形判別問(wèn)題）作為被檢測(cè)程序進(jìn)行性能測(cè)試，實(shí)驗(yàn)結(jié)果表明，基于該策略的測(cè)試數(shù)據(jù)自動(dòng)生成系統(tǒng)能自動(dòng)調(diào)整變異概率和保持優(yōu)秀個(gè)體，有效的解決了早熟問(wèn)題，同時(shí)也提高了自動(dòng)生成測(cè)試數(shù)據(jù)的效率。

關(guān)鍵詞：軟件測(cè)試；路徑測(cè)試數(shù)據(jù)；自適應(yīng)動(dòng)態(tài)優(yōu)化策略

中圖分類號(hào)：TP311.52

隨著計(jì)算機(jī)技術(shù)的飛速的發(fā)展，在各行各業(yè)中計(jì)算機(jī)都成為了一個(gè)重要的工具。與其相適應(yīng)的的軟件也在飛速發(fā)展，軟件的規(guī)模和復(fù)雜度也提高很快。作為軟件開(kāi)發(fā)過(guò)程中重要的步驟——軟件測(cè)試的規(guī)模和復(fù)雜度也相應(yīng)的提高了很多。軟件測(cè)試是一項(xiàng)昂貴而又耗費(fèi)勞力的工作，往往占軟件開(kāi)發(fā)總工作量的50%左右[1]。測(cè)試數(shù)據(jù)的自動(dòng)生成由其能提高軟件測(cè)試的效率和減少成本，一直是人們研究的重要對(duì)象。近幾年來(lái)，如何生成測(cè)試數(shù)據(jù)的已轉(zhuǎn)化成如何搜索合適測(cè)試數(shù)據(jù)，這使自動(dòng)生成測(cè)試數(shù)據(jù)的成為可能。利用遺傳算法，并根據(jù)測(cè)試數(shù)據(jù)自動(dòng)生成問(wèn)題的特點(diǎn)，可以生成高效的路徑測(cè)試數(shù)據(jù)自動(dòng)生成算法，具有一定的理論意義和工程實(shí)用價(jià)值。

1 SAOGO策略的引入

遺傳算法的性能受到兩個(gè)重要因素的影響，即“選擇壓力”和“種群多樣性”。在種群今后的過(guò)程中，如果選擇壓力太大將會(huì)導(dǎo)致種群很快被少量的個(gè)體占據(jù)，種群的多樣性被破壞，導(dǎo)致算法的結(jié)果為局部最優(yōu)。這樣的情況嚴(yán)重的降低遺傳算法的性能，這被稱為進(jìn)化停滯（evolution stagnation）問(wèn)題或種群早熟（population premahirity）問(wèn)題。但是，如果選擇較低的選擇壓力，雖然可以加大算法搜索的結(jié)果為全局最優(yōu)的概率，但是卻會(huì)嚴(yán)重的降低搜索的效率，甚至是算法退化為隨機(jī)算法，這將會(huì)對(duì)遺傳算法的搜索效率產(chǎn)生嚴(yán)重的影響。研究者們提出了一些方法，可以預(yù)防種群早熟現(xiàn)象的出現(xiàn)：（1）對(duì)初始種群的規(guī)模設(shè)置盡量的大。在大規(guī)模的種群中因其含有比較多的個(gè)體，其染色體的性態(tài)也比較多樣，發(fā)生算法收斂到局部最優(yōu)的情況的可能性較低。（2）提高變異操作的變異概率。更多的進(jìn)行編譯操作可以增加種群的新基因，提高了種群的多樣性，但較高的變異概率使搜索的隨機(jī)性增強(qiáng)，有可能降低適應(yīng)值函數(shù)的導(dǎo)向性，反而降低了遺傳算法的性能。（3）使用選擇壓力較小的存活操作和選擇操作[2-3]。以上幾種方法都只是對(duì)遺傳算法的優(yōu)化了其靜態(tài)配置，只能預(yù)防種群早熟問(wèn)題。當(dāng)種群早熟問(wèn)題發(fā)生時(shí)，它們沒(méi)有更好的方法來(lái)對(duì)種群恢復(fù)其多樣性。研究表明，對(duì)搜索過(guò)程進(jìn)行啟發(fā)式的動(dòng)態(tài)優(yōu)化，能改善智能隨機(jī)搜索法的性能[4]。我們認(rèn)為在遺傳算法的搜索中引入啟發(fā)式的動(dòng)態(tài)優(yōu)化方法同樣可能提高搜索的性能。我們提出了一種自適應(yīng)動(dòng)態(tài)優(yōu)化策略SAOGO來(lái)動(dòng)態(tài)調(diào)整Pm的取值和交叉對(duì)象，以解決進(jìn)化停滯問(wèn)題和加快最優(yōu)解的產(chǎn)生。

2 SAOGO策略

SAOGO的基本思想是：對(duì)種群的進(jìn)化情況進(jìn)行監(jiān)視，并根據(jù)監(jiān)控的情況自動(dòng)的調(diào)整算法的部分參數(shù)設(shè)置，以保證進(jìn)化處于良好的狀態(tài)。合適的動(dòng)態(tài)優(yōu)化方法能有效的提高算法的自適應(yīng)性和自動(dòng)生成測(cè)試數(shù)據(jù)的成功率。

在遺傳算法中，變異和交叉操作是非常重要的新個(gè)體產(chǎn)生手段，變異和交叉操作可以給種群帶來(lái)新的基因，對(duì)遺傳算法具有非常重要的意義。變異概率pm是遺傳算法中的關(guān)鍵參數(shù)，變異操作的概率由變異概率Pm來(lái)決定。使用SAOGO策略定期的對(duì)群體中的染色體進(jìn)行分析，當(dāng)發(fā)現(xiàn)種群有出現(xiàn)早熟的征兆時(shí)，適時(shí)的提高Pm的取值，引入新的基因恢復(fù)染色體多樣性，讓算法從進(jìn)化停滯狀態(tài)中恢復(fù)過(guò)來(lái)。同時(shí)選擇其中較優(yōu)的個(gè)體進(jìn)行保存，對(duì)其不進(jìn)行交叉和變異操作，提高個(gè)體的適應(yīng)性。染色體的多樣性得到恢復(fù)后，將Pm調(diào)整到正常值，以避免出現(xiàn)遺傳算法的搜索性能退化。

可以把SAOGO看作為一個(gè)監(jiān)視器，其包含的重要參數(shù)有：監(jiān)測(cè)周期MC表示的間隔多長(zhǎng)的時(shí)間對(duì)種群進(jìn)行檢查、重復(fù)比例PRI指某個(gè)染色體在種群中重復(fù)出現(xiàn)的比例、較優(yōu)個(gè)體集EID指在種群中重復(fù)比例較高的染色體、優(yōu)化持續(xù)時(shí)間PGA指進(jìn)行相應(yīng)的變異和交叉操作的時(shí)間和優(yōu)化強(qiáng)度EMP指將變異概率調(diào)高的比例。

SAOGO每隔MC輪對(duì)種群進(jìn)行一次檢查，如果有染色體在被種群中重復(fù)出現(xiàn)，且其比例已經(jīng)超過(guò)預(yù)先設(shè)定PRI值，SAOGO將會(huì)把變異概率的值改為預(yù)設(shè)的EMP值。同時(shí)把該染色體保存在EID中，該概率將會(huì)維持PGA輪，然后將變異概率恢復(fù)為正常值。

圖1

4 實(shí)驗(yàn)和結(jié)果分析

本文將以Triangle作為被檢測(cè)程序，實(shí)際檢驗(yàn)算法的效果。在軟件測(cè)試研究中很多時(shí)候都把Triangle作為一個(gè)基準(zhǔn)程序來(lái)使用，如圖2為Triangle 程序的流程控制圖。

實(shí)驗(yàn)開(kāi)始前我們對(duì)遺傳算法的參數(shù)做如下設(shè)置：種群大小初始化為M=60，染色體長(zhǎng)度L=21，最大進(jìn)化代數(shù)100，交叉概率pc=0.7，變異概率pm =0.03[5]。SAOGO的參數(shù)設(shè)置：監(jiān)測(cè)周期MC=10，重復(fù)比例PRI=8，優(yōu)化持續(xù)時(shí)間PGA=4，優(yōu)化強(qiáng)度EMP=0.7。

圖2 流程控制圖

圖3

圖4

在實(shí)驗(yàn)過(guò)程中我們發(fā)現(xiàn)SAOGO是否開(kāi)啟和變異次數(shù)有很大的關(guān)系，總的來(lái)說(shuō) SAOGO策略對(duì)遺傳算法的影響有以下三點(diǎn)：（1）當(dāng)SAOGO策略的使用，導(dǎo)致大量新的基因的引入，保證了種群的多樣性，避免了早熟現(xiàn)象的出現(xiàn)。（2）本實(shí)驗(yàn)中在適應(yīng)度最高的個(gè)體父體產(chǎn)生于SAOGO策略開(kāi)啟時(shí)，在后續(xù)進(jìn)行的9次實(shí)驗(yàn)中，其中有7次的最優(yōu)個(gè)體產(chǎn)生于策略開(kāi)啟時(shí)。（3）在實(shí)驗(yàn)過(guò)程中我們?yōu)榱藱z查保護(hù)最優(yōu)個(gè)體是否有利于提高種群適應(yīng)度，我們對(duì)同一組數(shù)據(jù)進(jìn)行了開(kāi)關(guān)保護(hù)最優(yōu)個(gè)體的策略，最終的實(shí)驗(yàn)結(jié)果表明在開(kāi)啟保護(hù)最優(yōu)個(gè)體策略時(shí)，加速了最終結(jié)果的形成。

通過(guò)對(duì)SAOGO策略的參數(shù)不同參數(shù)的設(shè)置，我們得出了圖3和圖4，對(duì)其進(jìn)行研究分析可以發(fā)現(xiàn)不同的參數(shù)設(shè)置對(duì)命中率的提高是有較大的差別的。在我們的實(shí)驗(yàn)中發(fā)現(xiàn)SAOGO策略的參數(shù)較優(yōu)配置為：監(jiān)測(cè)周期MC=10，重復(fù)比例PRI=6，優(yōu)化持續(xù)時(shí)間PGA=4，優(yōu)化強(qiáng)度EMP=0.75。

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

路徑測(cè)試數(shù)據(jù)自動(dòng)生成是程序結(jié)構(gòu)測(cè)試的一個(gè)重要方面。本文針對(duì)遺傳算法中早熟的現(xiàn)象，提出了自適應(yīng)動(dòng)態(tài)優(yōu)化策略SAOGO。通過(guò)實(shí)驗(yàn)驗(yàn)證該策略在路徑測(cè)試數(shù)據(jù)的自動(dòng)生成中的應(yīng)用，同時(shí)給出了相關(guān)參數(shù)的設(shè)定。

參考文獻(xiàn)：

[1]Bogdan.Korel.Automated Software Test Transactions on software engineering，1990（08）Data Generation[J].IEEE：870-879.

[2]律亞楠.基于遺傳算法的測(cè)試數(shù)據(jù)生成研究[D].汕頭大學(xué)，2008.

[3]冷劍.基于遺傳算法的軟件測(cè)試技術(shù)的研究[D].東北大學(xué)，2008.

[4]史亮.測(cè)試數(shù)據(jù)自動(dòng)生成技術(shù)研究[D].東南大學(xué)，2006.

[5]李軍，李艷輝，彭存銀.基于自適應(yīng)遺傳算法的路徑測(cè)試數(shù)據(jù)生成[J].計(jì)算機(jī)工程，2009（01）.

作者簡(jiǎn)介：孫為（1979.09-），男，湖北仙桃人，講師，本科，研究方向：計(jì)算機(jī)科學(xué)。

作者單位：瓊臺(tái)師范高等專科學(xué)校信息技術(shù)系，?？?571100