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

《基于遺傳算法的路徑測(cè)試數(shù)據(jù)自動(dòng)生成研究》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

1、基于遺傳算法的路徑測(cè)試數(shù)據(jù)自動(dòng)生成研究摘要：針對(duì)遺傳算法在運(yùn)算過程中產(chǎn)生的早熟問題，提出一種自適應(yīng)動(dòng)態(tài)優(yōu)化策略（SAOGO），用以自動(dòng)生成測(cè)試數(shù)據(jù)。通過優(yōu)化變異概率等手段，實(shí)現(xiàn)了路徑測(cè)試數(shù)據(jù)的自動(dòng)生成。將Triangle（三角形判別問題）作為被檢測(cè)程序進(jìn)行性能測(cè)試，實(shí)驗(yàn)結(jié)果表明，基于該策略的測(cè)試數(shù)據(jù)自動(dòng)生成系統(tǒng)能自動(dòng)調(diào)整變異概率和保持優(yōu)秀個(gè)體，有效的解決了早熟問題，同時(shí)也提高了自動(dòng)生成測(cè)試數(shù)據(jù)的效率。關(guān)鍵詞：軟件測(cè)試；路徑測(cè)試數(shù)據(jù)；自適應(yīng)動(dòng)態(tài)優(yōu)化策略中圖分類號(hào)：TP311.526隨著計(jì)算機(jī)技術(shù)的飛速的發(fā)展，在各行各業(yè)中計(jì)算機(jī)都成為了一個(gè)重要的工具。與其相適應(yīng)的的軟件也在飛速發(fā)展，軟件的

2、規(guī)模和復(fù)雜度也提高很快。作為軟件開發(fā)過程中重要的步驟――軟件測(cè)試的規(guī)模和復(fù)雜度也相應(yīng)的提高了很多。軟件測(cè)試是一項(xiàng)昂貴而又耗費(fèi)勞力的工作，往往占軟件開發(fā)總工作量的50%左右[1]。測(cè)試數(shù)據(jù)的自動(dòng)生成由其能提高軟件測(cè)試的效率和減少成本，一直是人們研究的重要對(duì)象。近幾年來，如何生成測(cè)試數(shù)據(jù)的已轉(zhuǎn)化成如何搜索合適測(cè)試數(shù)據(jù)，這使自動(dòng)生成測(cè)試數(shù)據(jù)的成為可能。利用遺傳算法，并根據(jù)測(cè)試數(shù)據(jù)自動(dòng)生成問題的特點(diǎn)，可以生成高效的路徑測(cè)試數(shù)據(jù)自動(dòng)生成算法，具有一定的理論意義和工程實(shí)用價(jià)值。1SAOGO策略的引入遺傳算法的性能受到兩個(gè)重要因素的影響，即“選擇壓力”和“種群多樣性”。在種群今后的過程中，如果選擇壓

3、力太大將會(huì)導(dǎo)致種群很快被少量的個(gè)體占據(jù)，種群的多樣性被破壞，導(dǎo)致算法的結(jié)果為局部最優(yōu)。這樣的情況嚴(yán)重的降低遺傳算法的性能，這被稱為進(jìn)化停滯（evolutionstagnation）問題或種群早熟（population6premahirity）問題。但是，如果選擇較低的選擇壓力，雖然可以加大算法搜索的結(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ā)生算法收斂到局部最

4、優(yōu)的情況的可能性較低。（2）提高變異操作的變異概率。更多的進(jìn)行編譯操作可以增加種群的新基因，提高了種群的多樣性，但較高的變異概率使搜索的隨機(jī)性增強(qiáng)，有可能降低適應(yīng)值函數(shù)的導(dǎo)向性，反而降低了遺傳算法的性能。（3）使用選擇壓力較小的存活操作和選擇操作[2-3]。以上幾種方法都只是對(duì)遺傳算法的優(yōu)化了其靜態(tài)配置，只能預(yù)防種群早熟問題。當(dāng)種群早熟問題發(fā)生時(shí)，它們沒有更好的方法來對(duì)種群恢復(fù)其多樣性。研究表明，對(duì)搜索過程進(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來動(dòng)態(tài)調(diào)整

5、Pm的取值和交叉對(duì)象，以解決進(jìn)化停滯問題和加快最優(yōu)解的產(chǎn)生。2SAOGO策略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)生手段，變異和交叉操作可以給種群帶來新的基因，對(duì)遺傳算法具有非常重要的意義。變異概率pm是遺傳算法中的關(guān)鍵參數(shù)，變異操作的概率由變異概率Pm來決定。使用SAOGO策略定期的對(duì)群體中的染色體進(jìn)行分析，當(dāng)發(fā)現(xiàn)種群有出現(xiàn)早熟的征兆時(shí)，適時(shí)的提高Pm的取值，引入新的基因恢復(fù)染色體多

6、樣性，讓算法從進(jìn)化停滯狀態(tài)中恢復(fù)過來。同時(shí)選擇其中較優(yōu)的個(gè)體進(jìn)行保存，對(duì)其不進(jìn)行交叉和變異操作，提高個(gè)體的適應(yīng)性。染色體的多樣性得到恢復(fù)后，將Pm調(diào)整到正常值，以避免出現(xiàn)遺傳算法的搜索性能退化。6可以把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)超過預(yù)先設(shè)定PRI值，

7、SAOGO將會(huì)把變異概率的值改為預(yù)設(shè)的EMP值。同時(shí)把該染色體保存在EID中，該概率將會(huì)維持PGA輪，然后將變異概率恢復(fù)為正常值。圖14實(shí)驗(yàn)和結(jié)果分析本文將以Triangle作為被檢測(cè)程序，實(shí)際檢驗(yàn)算法的效果。在軟件測(cè)試研究中很多時(shí)候都把Triangle作為一個(gè)基準(zhǔn)程序來使用，如圖2為Triangle程序的流程控制圖。實(shí)驗(yàn)開始前我們對(duì)遺傳算法的參數(shù)做如下設(shè)置：種群大小初始化為M=60，染色體長(zhǎng)度L=21，最大進(jìn)化代數(shù)100，交叉概率pc=0.7