基于改進(jìn)遺傳算法的軟件測(cè)試數(shù)據(jù)自動(dòng)生成系統(tǒng)研究

摘? 要：隨著軟件測(cè)試自動(dòng)化水平的進(jìn)一步提升，其對(duì)自動(dòng)準(zhǔn)確生成軟件測(cè)試數(shù)據(jù)的要求也逐漸提高。但由于以往常用的遺傳算法存在一定的局限性，難以令軟件測(cè)試數(shù)據(jù)始終保持較快的自動(dòng)生成速度與數(shù)據(jù)高質(zhì)量。因此需要對(duì)該遺傳算法進(jìn)行優(yōu)化改進(jìn)，在這一背景下，本文將從闡明改進(jìn)遺傳算法的必要性入手，分別從算法設(shè)計(jì)與系統(tǒng)設(shè)計(jì)兩方面，重點(diǎn)針對(duì)基于改進(jìn)遺傳算法的軟件測(cè)試數(shù)據(jù)自動(dòng)生成系統(tǒng)進(jìn)行簡(jiǎn)要分析研究。

關(guān)鍵詞：改進(jìn)遺傳算法;軟件測(cè)試數(shù)據(jù);自動(dòng)生成系統(tǒng)

中圖分類號(hào)：TP311.53;TP18? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：2096-4706（2020）01-0023-02

Abstract：With the further improvement of the level of software test automation，its requirements for automatically and accurately generating software test data have gradually increased. However，due to the limitations of the commonly used genetic algorithms in the past，it is difficult to keep the software test data always at a relatively fast automatic generation speed and high quality. Therefore，the genetic algorithm needs to be optimized and improved. In this context，this article will start by clarifying the necessity of improving the genetic algorithm，from the aspects of algorithm design and system design，this paper focuses on the automatic generation system of software test data based on improved genetic algorithm.

Keywords：improved genetic algorithm;software test data;automatic generation system

0? 引? 言

雖然國(guó)內(nèi)外目前有許多研究人員加入到遺傳算法及其優(yōu)化改進(jìn)的研究隊(duì)伍中，并經(jīng)過多年努力也取得了一定研究成果。但有關(guān)改進(jìn)遺傳算法在軟件測(cè)試數(shù)據(jù)自動(dòng)生成中的實(shí)際應(yīng)用等，相關(guān)研究還相對(duì)較少。因此本研究不僅能夠有效豐富該領(lǐng)域的理論研究，同時(shí)也可以為實(shí)現(xiàn)軟件測(cè)試數(shù)據(jù)自動(dòng)生成系統(tǒng)的優(yōu)化設(shè)計(jì)提供相應(yīng)的實(shí)踐依據(jù)。

1? 改進(jìn)遺傳算法設(shè)計(jì)軟件測(cè)試數(shù)據(jù)自動(dòng)生成系統(tǒng)的必要性

標(biāo)準(zhǔn)遺傳算法中，對(duì)于群體p（t）一般需要運(yùn)用遺傳算子，經(jīng)過選擇、交叉以及變異運(yùn)算，生成群體p（t+1）并在此基礎(chǔ)上依次進(jìn)行解碼與解集合處理，最后進(jìn)入個(gè)體評(píng)價(jià)環(huán)節(jié)，當(dāng)T即遺傳算法終止迭代次數(shù)比t值小時(shí)，直接選取當(dāng)前群體當(dāng)中的最優(yōu)個(gè)體作為最終解即可[1]。因此采用遺傳算法實(shí)現(xiàn)軟件測(cè)試數(shù)據(jù)自動(dòng)生成，即便無任何外界信息，也無需確定規(guī)則，只憑借迭代次數(shù)最大值開展循環(huán)搜索，便能夠達(dá)到并行搜索的效果，進(jìn)而使得數(shù)據(jù)自動(dòng)生成具有較高靈活性。但由于在標(biāo)準(zhǔn)遺傳算法當(dāng)中，交叉與變異概率完全固定，在算法執(zhí)行的整個(gè)過程中，無論是交叉還是變異算法執(zhí)行次數(shù)期望值并不發(fā)生變化，但種群進(jìn)化后期，如果交叉與變異算法多次被執(zhí)行，將會(huì)破壞優(yōu)秀的測(cè)試用例。且在算法中止時(shí)，其有可能產(chǎn)生早熟現(xiàn)象，并直接將局部最優(yōu)解作為全局最優(yōu)解，由此難以保障軟件測(cè)試數(shù)據(jù)是自動(dòng)生成的穩(wěn)定性以及數(shù)據(jù)生成質(zhì)量，故而有必要對(duì)標(biāo)準(zhǔn)遺傳算法進(jìn)行優(yōu)化改進(jìn)。

2? 改進(jìn)遺傳算法下的軟件測(cè)試數(shù)據(jù)自動(dòng)生成系統(tǒng)設(shè)計(jì)分析

2.1? 算法設(shè)計(jì)

2.1.1? 算法流程

針對(duì)傳統(tǒng)遺傳算法存在的局限性，本文在繼續(xù)使用遺傳算法的基礎(chǔ)上，設(shè)計(jì)采用模擬退火算法對(duì)遺傳算法進(jìn)行有效改進(jìn)。改進(jìn)后的遺傳算法在自動(dòng)生成軟件測(cè)試數(shù)據(jù)時(shí)，首先將在個(gè)體編碼中使用二級(jí)制，由此形成個(gè)體集后再運(yùn)用二級(jí)制編碼對(duì)多參數(shù)級(jí)聯(lián)編碼問題進(jìn)行有效解決。然后在完成參數(shù)初始化操作后，直接將初始測(cè)試數(shù)據(jù)準(zhǔn)確輸入其中，自動(dòng)計(jì)算適應(yīng)值，此時(shí)需要根據(jù)初始輸入測(cè)試數(shù)據(jù)反饋，運(yùn)用遺傳算法中的選擇、交叉與變異運(yùn)算生成新的種群。對(duì)生成的新種群使用模擬退火算法進(jìn)行最優(yōu)迭代，直至其出現(xiàn)迭代次數(shù)最大值，即需要降低初始設(shè)定穩(wěn)定，令T初=aT初，此時(shí)如果達(dá)到終止條件，則通過比較分析新種群以及初始種群的適應(yīng)值，結(jié)合最終得到的比較結(jié)果自動(dòng)輸出最優(yōu)數(shù)據(jù)集即可結(jié)束算法。否則需要持續(xù)進(jìn)行模擬退火降溫操作，直至其與終止條件相符合。

2.1.2? 優(yōu)化用例

一般情況下，采用代價(jià)測(cè)試覆蓋率的最小值優(yōu)化數(shù)據(jù)測(cè)試用例?？紤]到代價(jià)和覆蓋率相互制約，因此本文提出在使用改進(jìn)的遺傳算法下優(yōu)化軟件測(cè)試數(shù)據(jù)用例，如果用ti代表各測(cè)試用例，用代表軟件測(cè)試數(shù)據(jù)集Test ={t1，t2，…，tn}，用取值為正數(shù)的Costj代表和各測(cè)試用例一一對(duì)應(yīng)的測(cè)試代價(jià)。且測(cè)試代價(jià)主要由系統(tǒng)運(yùn)行所需內(nèi)存空間、CPU時(shí)間等共同構(gòu)成。通過轉(zhuǎn)化軟件測(cè)試數(shù)據(jù)是指成為一個(gè)Tests的真子集MinTS，其測(cè)試覆蓋與Tests測(cè)試覆蓋度相一致。利用改進(jìn)后的遺傳算法，在最優(yōu)化測(cè)試集合當(dāng)中加入測(cè)試代價(jià)最下用例，隨后直接刪除覆蓋測(cè)試需求，對(duì)該過程進(jìn)行多次重復(fù)操作直至同時(shí)出現(xiàn)完全一樣的兩個(gè)測(cè)試用例[2]。此時(shí)將同樣的兩個(gè)測(cè)試用例加入最優(yōu)測(cè)試結(jié)合當(dāng)中，在用例與全部測(cè)試需求相符合的情況下即可終止算法。此時(shí)所得到的即為最優(yōu)軟件測(cè)試數(shù)據(jù)用例。但值得注意的是，在優(yōu)化測(cè)試數(shù)據(jù)用例時(shí)，其數(shù)據(jù)庫(kù)及測(cè)試數(shù)據(jù)均需要對(duì)左右執(zhí)行程序當(dāng)中，任意一個(gè)分支及其所使用的數(shù)據(jù)進(jìn)行全覆蓋，每一個(gè)數(shù)據(jù)測(cè)試用例均能夠?qū)Ω鱾€(gè)CPU運(yùn)行進(jìn)行全程完整記錄。

2.2? 系統(tǒng)設(shè)計(jì)

2.2.1? 新建算法動(dòng)態(tài)鏈接庫(kù)

為使運(yùn)用改進(jìn)后的遺傳算法能夠有效增強(qiáng)軟件測(cè)試數(shù)據(jù)自動(dòng)生成算法的適用性，使其具有更高的移植性，首先，本文通過將改進(jìn)后的遺傳算法封裝成動(dòng)態(tài)鏈接庫(kù)，便于系統(tǒng)根據(jù)自身實(shí)際需要隨時(shí)進(jìn)行調(diào)取使用。為提升算法封裝的有效性，本文首先直接利用專業(yè)的工具軟件，應(yīng)用其中自動(dòng)的應(yīng)用程序新建一個(gè)空算法動(dòng)態(tài)鏈接庫(kù)，在對(duì)其進(jìn)行重新命名后直接存儲(chǔ)至和主程序一致的目錄下[3]。其次，新建有關(guān)于算法的類，主要添加包括bianmadll.h與bainmadll.cpp以及yichuanxiliedll.cpp等在內(nèi)的各種頭文件，根據(jù)被添加的各頭文件，完成定義遺傳算法二進(jìn)制編碼、初始化改進(jìn)后遺傳算法的參數(shù)定義等操作。例如使用bianmadll.h定義遺傳算法二進(jìn)制編碼，使用bainmadll.cpp這一頭文件進(jìn)行編碼化執(zhí)行操作。頭文件diedaicaozuodll.h被用于定義迭代操作，其編碼化執(zhí)行操作時(shí)需要使用的頭文件為diedaicaozuodll.cpp。最后，自動(dòng)生成Gaijin.dll即對(duì)應(yīng)的解決方案，由主程序根據(jù)其實(shí)際需要隨時(shí)進(jìn)行調(diào)取使用，完成單元測(cè)試用例的自動(dòng)生成與準(zhǔn)確移植。

2.2.2? 系統(tǒng)層次架構(gòu)的設(shè)計(jì)

在完成遺傳算法的優(yōu)化改進(jìn)后，本文通過充分考慮軟件測(cè)試數(shù)據(jù)自動(dòng)生成需求，在積極參考其他相關(guān)研究資料的基礎(chǔ)上，選擇使用分層設(shè)計(jì)理念，將整個(gè)軟件測(cè)試數(shù)據(jù)自動(dòng)生成系統(tǒng)分成三大層，分別為數(shù)據(jù)訪問層、業(yè)務(wù)邏輯層、頁面顯示層。數(shù)據(jù)訪問層作為整個(gè)基于改進(jìn)遺傳算法的軟件測(cè)試數(shù)據(jù)自動(dòng)生成系統(tǒng)最底層，占據(jù)著絕對(duì)的基礎(chǔ)性地位，該層中通過運(yùn)用專業(yè)的數(shù)據(jù)庫(kù)，并采用具有良好通用性的ADO.NET數(shù)據(jù)接口，負(fù)責(zé)完成各項(xiàng)軟件測(cè)試數(shù)據(jù)的采集與傳輸。業(yè)務(wù)邏輯層作為系統(tǒng)中間層，分別與數(shù)據(jù)訪問層和頁面顯示層相互連接，發(fā)揮著承上啟下的重要作用。數(shù)據(jù)訪問層中的ADO.NET數(shù)據(jù)接口與業(yè)務(wù)邏輯層當(dāng)中由各個(gè)業(yè)務(wù)組件共同構(gòu)成的工作流組件中的數(shù)據(jù)接口相互連接，實(shí)現(xiàn)軟件測(cè)試數(shù)據(jù)的高效共享傳輸。所有采集得到的有關(guān)工作流組件的數(shù)據(jù)，將統(tǒng)一傳輸至業(yè)務(wù)邏輯層中的ASPX當(dāng)中，而ASPX則直接與頁面顯示層當(dāng)中的工作流客戶端，即.aspx網(wǎng)頁相互連接，負(fù)責(zé)在該頁面中直接自動(dòng)顯示獲取的各項(xiàng)軟件測(cè)試數(shù)據(jù)，最終達(dá)到軟件測(cè)試數(shù)據(jù)快速、準(zhǔn)確自動(dòng)生成的目的。

2.3? 運(yùn)行成效

在改進(jìn)遺傳算法中，將種群設(shè)定為300，將終止迭代次數(shù)統(tǒng)一設(shè)定為25，將交叉概率分布設(shè)定為0.7與0.4，將變異概率分別設(shè)定為0.04和0.02。在標(biāo)準(zhǔn)遺傳算法中，其他參數(shù)不變，只將交叉概率與變異概率固定設(shè)置為0.8與0.02，分別各自運(yùn)行標(biāo)準(zhǔn)遺傳算法與改進(jìn)遺傳算法下的軟件測(cè)試數(shù)據(jù)自動(dòng)生成系統(tǒng)共計(jì)50次，每五次為一組取均值。根據(jù)最終的運(yùn)行結(jié)果可知，改進(jìn)遺傳算法的執(zhí)行速度更快，具有更好的收斂性。如同樣在系統(tǒng)運(yùn)行10次的情況下，標(biāo)準(zhǔn)遺傳算法中，系統(tǒng)每組平均執(zhí)行時(shí)間不足80 ms，但改進(jìn)遺傳算法中系統(tǒng)每組平均執(zhí)行時(shí)間仍然保持90 ms以上。除此之外，基于標(biāo)準(zhǔn)遺傳算法的軟件測(cè)試數(shù)據(jù)自動(dòng)生成系統(tǒng)每次生成的數(shù)據(jù)結(jié)果并不完全相同，但改進(jìn)遺傳算法下系統(tǒng)運(yùn)行具有較高的穩(wěn)定性，生成測(cè)試數(shù)據(jù)范圍較大，具有較高的數(shù)據(jù)生成效率。

3? 結(jié)? 論

根據(jù)本文的分析研究，可知運(yùn)用深入融合模擬退火算法，與自適應(yīng)交叉與變異算子的方式，對(duì)遺傳算法進(jìn)行優(yōu)化改進(jìn)。并運(yùn)用改進(jìn)后的遺傳算法設(shè)計(jì)軟件測(cè)試數(shù)據(jù)自動(dòng)生成系統(tǒng)，能夠在保障軟件測(cè)試數(shù)據(jù)具有更廣闊的搜索生成范圍的基礎(chǔ)上，進(jìn)一步提升數(shù)據(jù)生成速度，并確保數(shù)據(jù)始終具有較高的質(zhì)量水平。因此證明，改進(jìn)遺傳算法在軟件測(cè)試數(shù)據(jù)自動(dòng)生成系統(tǒng)中具有較高的應(yīng)用價(jià)值。

參考文獻(xiàn)：

[1] 姬峰.基于改進(jìn)遺傳算法的軟件測(cè)試自動(dòng)化機(jī)制研究 [J].信息技術(shù)，2019（10）：88-93.

[2] 韓霄漢，葉方彬，竇健，等.基于改進(jìn)遺傳算法的接口測(cè)試數(shù)據(jù)集的生成方法 [J].濟(jì)南大學(xué)學(xué)報(bào)（自然科學(xué)版），2019，33（1）：56-60.

[3] 王佩佩.基于自適應(yīng)遺傳算法的測(cè)試數(shù)據(jù)自動(dòng)生成理論與方法 [D].徐州：中國(guó)礦業(yè)大學(xué)，2018.

作者簡(jiǎn)介：孫德剛（1978.04-），男，漢族，山東德州人，高級(jí)工程師，學(xué)士學(xué)位，研究方向：教育信息化、軟件開發(fā)。