基于遺傳算法的測試用例生成方法

1、摘要軟件測試是保證軟件質(zhì)量和可靠性重要手段，在這方面發(fā)揮著其它方法不可替代的作用。然而，軟件測試是一個(gè)復(fù)雜的過程，需要耗費(fèi)巨大的人力、物力和時(shí)間，約占整個(gè)軟件開發(fā)成本的40%50%。因此，提高軟件測試工具的自動(dòng)化程度對于確保軟件開發(fā)質(zhì)量、降低軟件開發(fā)成本非常重要。而提高測試用例生成的自動(dòng)化程度又是提高測試工具乃至整個(gè)測試過程自動(dòng)化程度的關(guān)鍵所在，本文主要針對這一問題進(jìn)行了研究和設(shè)計(jì)。本文在分析軟件測試和遺傳算法基本概念的基礎(chǔ)上，提出軟件測試用例的設(shè)計(jì)是軟件測試的難點(diǎn)之一。論文提出了基于遺傳算法的測試用例生成的內(nèi)含是應(yīng)用遺傳算法來求解一組優(yōu)化的測試用例，其框架包括了測試環(huán)境構(gòu)造、遺傳算法及測試運(yùn)

2、行環(huán)境三部分，論文給出了基于遺傳算法的測試用例生成的模型。最后以三角形分類程序?yàn)槔龖?yīng)用遺傳算法進(jìn)行測試用例生成的模擬，結(jié)果顯示，應(yīng)用遺傳算法進(jìn)行測試用例生成可行。關(guān)鍵詞：軟件測試 測試用例 遺傳算法ABSTRACTSoftware test is the important means that guarantee software quality and reliability， and in this respect，it plays the role that other method cannot replace. However software test is a complex

3、process , it needs to consume huge manpower，material resources and time，which takes the 40%50% of entire software development cost approximately . Therefore，raising the automation level of software test tool is very important for ensure software development quality and reduction software development

4、 cost . And then，the most important is raising the automation level of the test case generation for raising the automation level of test tool and even entire test process，so this paper study and design mainly according to this problem.Based on the analysis of basic concepts of software testing and g

5、enetic algorithm, this article proposes that software test case design is one of the difficulties of software testing. Paper presents the inherent in software test case designing based on genetic algorithm is using genetic algorithm to solve a set of optimization test cases, and the framework includ

6、es three parts which are test environment construction, genetic algorithm and the environment for test . Paper presents the model of software test case generation based on genetic algorithm. Finally, we take the triangle categorizer as an example, simulate software test case generation based on gene

7、tic algorithm. The results display that software test case generation basing on genetic algorithm is possible.KEY WORDS: software test , test case , genetic algorithm目錄摘要1ABSTRACT2目錄3第一章 緒論51.1 問題的提出5第二章 遺傳算法基本概念62.1 遺傳算法62.1.1 遺傳算法的思想及流程62.1.2 遺傳算法的特點(diǎn)72.2本章小結(jié)8第三章 基于遺傳算法的測試用例生成93.1基于遺傳算法的測試用例生成基本內(nèi)涵9

8、3.1.1 軟件測試用例的基本內(nèi)涵93.1.2 基于遺傳算法的測試用例生成的基本內(nèi)涵93.2 基于遺傳算法的測試用例生成框架103.3 基于遺傳算法的測試用例生成算法實(shí)現(xiàn)113.3.1 編碼策略113.3.2 適應(yīng)度函數(shù)及程序插樁113.3.3 遺傳策略123.3.4 參數(shù)控制133.4 本章小結(jié)14第四章 實(shí)驗(yàn)及結(jié)果分析154.1 待測程序分析154.1.1 待測程序引入154.1.2 程序流程分析154.1.3 路徑分析164.2 程序插樁164.3 參數(shù)設(shè)定及程序?qū)崿F(xiàn)174.3.1 參數(shù)設(shè)定174.4 本章小結(jié)18第五章 總結(jié)與展望19致謝語20參考文獻(xiàn)21第一章 緒論1.1 問題的提出

9、在信息化普及的今天，計(jì)算機(jī)在人們的生活和工作中占據(jù)著重要地位，使人們的工作效率提高，也使生活更豐富多彩。而作為計(jì)算機(jī)的重要組成部分，軟件的重要性不言而喻。隨著計(jì)算機(jī)技術(shù)的日益發(fā)展，計(jì)算機(jī)軟件的規(guī)模越來越龐大，復(fù)雜性越來越高，這就為軟件質(zhì)量的保證帶來了困難。因?yàn)檐浖拈_發(fā)過程大部分是由人的智力活動(dòng)構(gòu)成，不可能完美無缺。而軟件缺陷如果不能及時(shí)發(fā)現(xiàn)，帶來的損失可能是巨大的，有的甚至?xí)＜叭说纳?。然而，目前生成測試用例的方法主要是向前核查法和逆向回溯法，測試人員根據(jù)自己的項(xiàng)目經(jīng)驗(yàn)手工為指定的程序路徑生成測試數(shù)據(jù)5。向前核查法是指沿預(yù)期的路徑向前檢查，確定到每一個(gè)判斷點(diǎn)時(shí)變量所能提供的最寬數(shù)值區(qū)間，然

10、后繼續(xù)前行，從而將多個(gè)變量的可能取值范圍逐漸縮小，到達(dá)程序出口后，就能找到覆蓋這條路徑所需的輸入數(shù)據(jù)。逆向回溯法正好相反，是指從期望執(zhí)行的程序位置出發(fā)，逆向回溯，在每個(gè)判斷點(diǎn)處逐漸調(diào)整各變量取值，直到退到程序入口，即獲得所需的輸入數(shù)據(jù)。向前核查法和逆向回溯法的局限性是，對某些條件要求苛刻的路徑使用時(shí)非常困難，同時(shí)由于大多數(shù)程序中包含的路徑數(shù)非常多，如果按每條路徑手工測試，顯然帶來的工作量是非常巨大的。由于測試的工作量大、測試過程的重復(fù)性高等特點(diǎn)，自動(dòng)化測試正逐漸得到廣泛的應(yīng)用。很多測試工具的使用大大提高了測試人員的工作效率，有效減少了項(xiàng)目開支。然而這些工具主要為測試的執(zhí)行、管理和度量工具，在測

11、試用例自動(dòng)生成方面還不完善。而在軟件測試過程中，動(dòng)態(tài)測試作為測試的重要環(huán)節(jié)占了很大比例，動(dòng)態(tài)測試的關(guān)鍵正是測試用例的生成問題。因此，尋找一種有效的測試用例生成方法是提高測試自動(dòng)化的重中之重。第二章 遺傳算法基本概念2.1 遺傳算法2.1.1 遺傳算法的思想及流程遺傳算法（genetic algorithm）是模擬達(dá)爾文的遺傳選擇和自然淘汰的生物進(jìn)化過程的計(jì)算模型。遺傳算法作為一種不依賴具體問題的直接搜索方法受到廣泛關(guān)注，它是現(xiàn)代有關(guān)智能計(jì)算的關(guān)鍵技術(shù)之一。遺傳算法的思想源于生物遺傳學(xué)和適者生存的自然選擇規(guī)律，因此是具有“生存+檢測”的迭代過程的搜索算法。它以一個(gè)群體中的所有個(gè)體為對象，并利用隨

12、機(jī)化技術(shù)指導(dǎo)對一個(gè)被編碼的參數(shù)空間進(jìn)行高效搜索。遺傳算法將問題的解空間映射為遺傳空間，對解空間進(jìn)行編碼，即將每個(gè)可能的解用一串二進(jìn)制或十進(jìn)制數(shù)字串表示，稱為一個(gè)染色體，解的每個(gè)分量稱為一個(gè)基因。算法開始時(shí)先隨機(jī)給出一群染色體，即候選解，由預(yù)先設(shè)定的某個(gè)評價(jià)指標(biāo)計(jì)算每個(gè)染色體的適應(yīng)值，將適應(yīng)度低的染色體淘汰掉，而保留適應(yīng)度高的優(yōu)良染色體，然后對這些染色體進(jìn)行選擇復(fù)制、交叉和變異等遺傳操作，從而產(chǎn)生新的一代染色體群體。這樣一代一代的“進(jìn)化”，直至找到算法的最優(yōu)解，即適應(yīng)值滿足條件的解。由于算法產(chǎn)生的“后代”是由優(yōu)秀的“父代”和“母代”產(chǎn)生的，因此繼承了上代的優(yōu)良性態(tài)而優(yōu)于上代，從而使算法向著最優(yōu)解

13、的方向進(jìn)行，直到滿足預(yù)先設(shè)定的條件。遺傳算法過程包括了編碼、產(chǎn)生初始群體、計(jì)算適應(yīng)值、選擇、交叉、變異等操作。其一般流程圖如圖2-1所示：j:=0選擇變異個(gè)體執(zhí)行變異將變異結(jié)果添加到新群體中j:=j+1j=PmM？YN執(zhí)行交換j:=j+1根據(jù)適應(yīng)度選擇兩個(gè)交換個(gè)體j:=0將交換后的兩個(gè)新個(gè)體添加到新群體中j=PcM？NYj:=0根據(jù)適應(yīng)度選擇復(fù)制個(gè)體執(zhí)行復(fù)制將復(fù)制結(jié)果添加到新群體中j:=j+1j=PsM？Y開始Gen:=0自左向右執(zhí)行一次遺傳算子計(jì)算群體中各個(gè)體適應(yīng)度終止輸出結(jié)果隨機(jī)產(chǎn)生M個(gè)初始群體確定字符串長度L滿足終止條件？YNNPsPcPmGen:=Gen+1圖2-1 遺傳算法流程圖2.

14、1.2 遺傳算法的特點(diǎn)遺傳算法是一類可用于復(fù)雜系統(tǒng)優(yōu)化計(jì)算的搜索算法，與其他一些優(yōu)化算法相比，它的主要特點(diǎn)有如下幾點(diǎn)27：（1）遺傳算法以決策變量的編碼作為運(yùn)算對象，而傳統(tǒng)優(yōu)化算法往往直接利用變量的實(shí)際值來進(jìn)行優(yōu)化計(jì)算。這種對決策變量的編碼處理方式，使得我們在優(yōu)化計(jì)算過程中可以借鑒生物學(xué)中染色體和基因等概念以及遺傳和進(jìn)化機(jī)理。特別是對些無數(shù)值概念或很難有數(shù)值概念，而只有代碼概念的優(yōu)化問題，編碼處理方式更顯示出了其獨(dú)待的優(yōu)越性。（2）遺傳算法直接以目標(biāo)函數(shù)值作為搜索信息，而不需要目標(biāo)函數(shù)的導(dǎo)數(shù)值等其他輔助信息。這個(gè)特性對很多目標(biāo)函數(shù)難以求導(dǎo)的優(yōu)化問題，以及組合優(yōu)化問題等，應(yīng)用遺傳算法時(shí)就顯得比較

15、方便。而且，直接利用目標(biāo)函數(shù)值或個(gè)體適應(yīng)度，也可使得我們可以把搜索范圍集中到適應(yīng)度較高的部分搜索空間中，從而提高了搜索效率。（3）遺傳算法同時(shí)使用多個(gè)搜索點(diǎn)的搜索信息，而傳統(tǒng)的優(yōu)化算法往往是從解空間中的一個(gè)初始點(diǎn)開始最優(yōu)解的迭代搜索過程。單個(gè)搜索點(diǎn)的搜索效率不高，甚至可能使搜索過程陷于局部最優(yōu)解而停滯不前。遺傳算法通過對個(gè)體組成的群體進(jìn)行操作運(yùn)算，產(chǎn)生新的群體，其中包含的群體信息可以避免搜索一些不必搜索的點(diǎn)，所以實(shí)際上相當(dāng)于搜索了更多的點(diǎn)，這是遺傳算法所特有的一種隱性并行性。（4）遺傳算法使用概率搜索技術(shù)，而很多傳統(tǒng)的優(yōu)化算法往往使用的是確定性的搜索方法。確定性的方法由于固定了點(diǎn)與點(diǎn)之間的轉(zhuǎn)移

16、方法和轉(zhuǎn)移關(guān)系，往往可能使得搜索永遠(yuǎn)達(dá)不到最優(yōu)點(diǎn)，因而也限制了算法的應(yīng)用范圍。而遺傳算法屬于一種自適應(yīng)的概率搜索技術(shù)，其選擇、交叉、變異等運(yùn)算都是以一種概率的方式來進(jìn)行的，從而增加了算法搜索過程的靈活性和搜索效率。2.2本章小結(jié)本章首先介紹了軟件測試的一些基本概念，介紹了遺傳算法的基本概念，包括遺傳算法的思想、流程及特點(diǎn)。第三章 基于遺傳算法的測試用例生成3.1基于遺傳算法的測試用例生成基本內(nèi)涵3.1.1 軟件測試用例的基本內(nèi)涵測試用例是為某個(gè)特殊目標(biāo)而編制的一組測試輸入、執(zhí)行條件以及預(yù)期結(jié)果，以便測試某個(gè)程序路徑或核實(shí)是否滿足某個(gè)特定需求，包含輸入和輸出兩部分。構(gòu)造測試用例的目的是為了檢查被

17、測軟件的操作結(jié)果是否與預(yù)期的需求相吻合，確定應(yīng)用程序的某些特性是否正常的工作等。測試用例的質(zhì)量可以用以下四個(gè)標(biāo)準(zhǔn)來描述:（1）有效性:是否能夠發(fā)現(xiàn)缺陷，或者至少可能發(fā)現(xiàn)缺陷；（2）仿效性:可仿效的測試用例能夠測試多項(xiàng)內(nèi)容，從而減少測試用例的數(shù)量；（3）經(jīng)濟(jì)性:測試用例的執(zhí)行、分析和調(diào)試是否經(jīng)濟(jì)；（4）修改性:軟件修改后測試用例的維護(hù)成本。3.1.2 基于遺傳算法的測試用例生成的基本內(nèi)涵使用遺傳算法實(shí)現(xiàn)測試用例的自動(dòng)生成可描述為12：應(yīng)用遺傳算法來求解一組優(yōu)化的測試用例。在每一步進(jìn)化計(jì)算過程中，測試用例自動(dòng)生成器使用當(dāng)前群體（測試用例）驅(qū)動(dòng)被測試程序的執(zhí)行，每一個(gè)測試用例的執(zhí)行路徑被跟蹤和記錄，

18、以最大化程序執(zhí)行路徑的覆蓋為適應(yīng)性目標(biāo)函數(shù)進(jìn)行計(jì)算，產(chǎn)生出下一代群體。在多代進(jìn)化之后，得到最優(yōu)種群或超過特定的循環(huán)限制條件而結(jié)束。因?yàn)闇y試用例的自動(dòng)生成是在一個(gè)數(shù)據(jù)域中尋找滿足給定的測試標(biāo)準(zhǔn)的一組測試輸入數(shù)據(jù)的過程，所以近年來出現(xiàn)了把測試用例的生成問題轉(zhuǎn)化成路徑搜索問題的思想。由于一般情況下，測試數(shù)據(jù)的產(chǎn)生是一個(gè)不可判定性問題，再加上被測程序的規(guī)模和復(fù)雜性，一般的搜索算法受到了極大的限制。遺傳算法在處理不確定搜索問題時(shí)有著非常明顯的優(yōu)勢。遺傳算法能針對程序路徑生成大量有效測試用例，因此符合測試用例設(shè)計(jì)的全面性、正確性等原則。生成的測試用例符合上節(jié)中的測試用例設(shè)計(jì)標(biāo)準(zhǔn)，特別是有效性和經(jīng)濟(jì)性等，由

19、此可見遺傳算法應(yīng)用于測試用例生成是可行的。3.2 基于遺傳算法的測試用例生成框架本文基于遺傳算法的測試用例生成基本流程如下所示：（1）分析源程序代碼，獲得程序控制流程圖；（2）由程序控制流程圖得到程序分支路徑集合，選擇目標(biāo)路徑；（3）根據(jù)各謂詞條件給程序插樁并制定適應(yīng)度函數(shù)；（4）設(shè)定算法參數(shù)，包括群體大小、變異率等，隨機(jī)產(chǎn)生初始測試數(shù)據(jù)集合；（5）使用測試數(shù)據(jù)執(zhí)行經(jīng)過插裝的源代碼，獲得適應(yīng)度值，根據(jù)適應(yīng)度值判斷，若滿足程序終止條件則輸出結(jié)果并退出程序，若不滿足條件則進(jìn)入步驟（6）；（6）根據(jù)得到的適應(yīng)度值，使用遺傳算法的選擇、交叉、變異等操作，生成新的測試數(shù)據(jù)，并回到步驟（5），重復(fù)執(zhí)行；測

20、試環(huán)境構(gòu)造部分是整個(gè)系統(tǒng)的基礎(chǔ)，它主要利用靜態(tài)分析提供的基本信息并借助于各種插裝技術(shù)來構(gòu)造相應(yīng)的測試運(yùn)行環(huán)境。遺傳算法部分是系統(tǒng)的核心，它主要按照第一部分生成的編碼參數(shù)格式構(gòu)造相應(yīng)的染色體串，并生成初始種群，然后通過對該種群進(jìn)行反復(fù)的GA運(yùn)算（選擇、交叉和變異）從而引導(dǎo)種群不斷地向目標(biāo)值進(jìn)化直到最終找到解或達(dá)到限定的運(yùn)行代數(shù)為止。最后部分是測試運(yùn)行環(huán)境。遺傳算法第二部分需要對種群中每一個(gè)個(gè)體的優(yōu)劣進(jìn)行評估，它主要是通過實(shí)時(shí)地調(diào)用并運(yùn)行插裝后的測試系統(tǒng)來返回適應(yīng)度值，從而來指導(dǎo)遺傳算法的搜索。3.3 基于遺傳算法的測試用例生成算法實(shí)現(xiàn)3.3.1 編碼策略使用遺傳算法求解問題時(shí)，必須將目標(biāo)問題的實(shí)

21、際表示與遺傳算法的染色體位串結(jié)構(gòu)之間建立映射關(guān)系，這一過程即為編碼。編碼就是將目標(biāo)問題的解用一種特定字符串來表示，從而將問題的解空間（有效的候選解，即表現(xiàn)型個(gè)體）與遺傳算法的碼空間（基因型個(gè)體）相對應(yīng)。編碼過程是遺傳算法的基礎(chǔ)，編碼方法除了決定了個(gè)體的染色體排列形式之外，還決定了個(gè)體從GA空間的基因型變換到問題空間的表現(xiàn)型時(shí)的解碼方法（即為編碼方法的逆方法）。同時(shí)，編碼方法也影響到交叉算子、變異算子等遺傳算子的運(yùn)算方法。常見的編碼方法有二進(jìn)制編碼方法、格雷碼編碼方法、浮點(diǎn)數(shù)編碼方法、符號(hào)編碼方法等，在應(yīng)用中具體使用何種編碼方法應(yīng)根據(jù)問題的實(shí)際情況而定，這里我們使用二進(jìn)制編碼方法。3.3.2 適

22、應(yīng)度函數(shù)及程序插樁（1）適應(yīng)度函數(shù)在遺傳算法中，不需要用到搜索空間的知識(shí)，而使用適應(yīng)度函數(shù)對染色體進(jìn)行評價(jià)，一般來說，適應(yīng)度高的染色體的評價(jià)較高，適應(yīng)度低的染色體評價(jià)較低而可能被淘汰，因此，適應(yīng)度函數(shù)直接決定了種群的進(jìn)化方向，對算法的好壞具有很大影響。同時(shí)，適應(yīng)度函數(shù)的復(fù)雜度是遺傳算法復(fù)雜度的主要組成部分，因此適應(yīng)度函數(shù)要求盡可能簡單。適應(yīng)度函數(shù)通常可以從目標(biāo)函數(shù)轉(zhuǎn)化而來。一般來說，要求適應(yīng)度的取值越大越好。但在實(shí)際問題中，有的目標(biāo)函數(shù)是求最大值（如利潤問題），也有的目標(biāo)函數(shù)是求最小值（如費(fèi)用問題）。因此在很多場合需要將目標(biāo)函數(shù)轉(zhuǎn)換為最大值形式并且函數(shù)值為非負(fù)的適應(yīng)度函數(shù)。（2）程序插樁在程序

23、流程圖中，每個(gè)分支都可以用一個(gè)判斷表達(dá)式來表示，該判斷表達(dá)式稱為分支謂詞，其作用是描述了程序遍歷該分支的條件，如判斷語句“if(ab).”中分支謂詞為“ab”。分支謂詞的一般形式為：E1 op E2，E1和E2是算數(shù)表達(dá)式，關(guān)系運(yùn)算符。每個(gè)分支謂詞都可以轉(zhuǎn)換成等價(jià)形式為：F rel 0，其中F為分支函數(shù)，其構(gòu)造方法如表3-1所示。表3-1 分支函數(shù)的構(gòu)造分支謂詞分支函數(shù)relE1E2E2-E1=E2E2-E1=E1E2E1-E2E1=E2E1-E2=E1=E2abs(E1-E2)=E1!=E2-abs(E1-E2)b) change(a,b); if(ac) change(a,c); if(b

24、c) change(b,c); if(a+bc) if(a=b|b=c) if(a=c) type=“等邊三角形”; else type=“等腰三角形”; else type=“普通三角形”; else type=“不是三角形”; return type; 4.1.2 程序流程分析該程序流程圖如圖4-1所示，程序分為兩部分，先將輸入值由小到大排序，再將三角形進(jìn)行分類。輸入a,b,c交換a,b不是三角形ab?ac?bc?a=b|b=c?a+bc?交換a,c交換b,ca=c?等腰三角形普通三角形等邊三角形結(jié)束YYYYYYNNNNNN圖4-1 三角形分類程序流程圖4.1.3 路徑分析通過對程序流程分

25、析可知，該程序?qū)θ切芜M(jìn)行分類的語句為圖4-2中標(biāo)有“”至“”號(hào)的分支，對這些分支進(jìn)行路徑分析如表4-1所示：表4-1 路徑分析路徑號(hào)分支結(jié)果w1不是三角形W2-普通三角形W3-等腰三角形W4-等邊三角形4.2 程序插樁根據(jù)3.3.2，對待測程序插樁：String tri_type(int a,int b,int c) string type; if(ab) change(a,b); if(ac) change(a,c); if(bc) change(b,c); f1=c-(a+b) ; /插樁1 if(a+bc) f2=min(abs(a-b),abs(b-c); /插樁2 if(a=b|b

26、=c) f3=abs(a-c); /插樁3 if(a=c) type=“等邊三角形”; else type=“等腰三角形”; else type=“普通三角形”; else type=“不是三角形”; return type; F=1/(1+f1)+1/(1+f2)+1/(1+f3); /適應(yīng)度函數(shù) return F; 4.3 參數(shù)設(shè)定及程序?qū)崿F(xiàn)4.3.1 參數(shù)設(shè)定（1）編碼在本例子中，由于程序輸入為三角形的三條邊的長度，因此設(shè)定輸入值類型為063的整數(shù)，采用二進(jìn)制級(jí)聯(lián)編碼方法，每個(gè)參數(shù)編碼長度為6位，精度為1，并將三個(gè)參數(shù)進(jìn)行級(jí)聯(lián)（如參數(shù)、級(jí)聯(lián)后為），級(jí)聯(lián)后染色體長度為18位。（2）遺傳操作

27、參數(shù)在本實(shí)驗(yàn)中，設(shè)定遺傳操作的參數(shù)如表4-2所示：表4-2 遺傳操作參數(shù)設(shè)定種群大小選擇策略及概率交叉策略及概率變異策略及概率最大進(jìn)化代數(shù)100輪盤賭轉(zhuǎn)法，0.1單點(diǎn)交叉，0.8基本位變異，0.1100（3）算法終止條件本實(shí)驗(yàn)中設(shè)定算法終止條件為滿足以下兩個(gè)條件之一：找到最優(yōu)解，即適應(yīng)度為100的解；達(dá)到最大進(jìn)化代數(shù)，當(dāng)程序進(jìn)化滿100代后，不管有沒找到最優(yōu)解都將退出。4.4 本章小結(jié)本章以三角形分類程序?yàn)槔褂眠z傳算法進(jìn)行測試用例的生成，是前幾章內(nèi)容的結(jié)晶。文中先對待測程序的流程和路徑等進(jìn)行了分析，然后對程序進(jìn)行插樁，并對相關(guān)參數(shù)進(jìn)行了設(shè)定，然后展示了程序主要模塊的代碼，最后通過分析程序的運(yùn)

28、行結(jié)果，并和隨機(jī)法作了比較，顯示了遺傳算法的優(yōu)越性。第五章 總結(jié)與展望軟件測試是軟件工程中的重要環(huán)節(jié)，隨著軟件技術(shù)的發(fā)展和軟件規(guī)模的擴(kuò)大，軟件測試日益凸顯其重要性。而測試數(shù)據(jù)是軟件測試的基礎(chǔ)。傳統(tǒng)的手工構(gòu)建測試數(shù)據(jù)工作量大，浪費(fèi)了大量的人力、物力資源，且測試效率低。因此測試用例的自動(dòng)生成成為了國內(nèi)外學(xué)者研究的熱點(diǎn)。遺傳算法作為一種優(yōu)化的搜索算法，在軟件測試中得到了廣泛的應(yīng)用和研究。本文作者通過對大量文獻(xiàn)中測試用例生成方法和遺傳算法的學(xué)習(xí)，將遺傳算法應(yīng)用到測試用例的生成上。文中首先介紹了軟件測試及遺傳算法的國內(nèi)外研究現(xiàn)狀，然后介紹了軟件測試和遺傳算法的基本概念，接著提出了基于遺傳算法生成測試用例

29、的內(nèi)含、框架及模型，最后以三角形分類程序?yàn)槔?yàn)證了基于遺傳生成測試用例的可行性。由于時(shí)間問題，本文還存在許多問題和不足，將作為進(jìn)一步研究的主要內(nèi)容和方向：第一，本文只用到了遺傳算法，并沒有將其它算法與之混合使用以改進(jìn)性能。第二，本文中遺傳算法所使用的適應(yīng)度函數(shù)及遺傳算子均采用的是比較簡單且使用廣泛的算法，并沒有將這些算法做進(jìn)一步的研究和改進(jìn)。第三，本文最后實(shí)現(xiàn)的程序只是一個(gè)產(chǎn)生測試數(shù)據(jù)的原始工具模型，特別在用戶界面方面還很欠缺，需要進(jìn)一步完善。致謝語本學(xué)期的學(xué)習(xí)很快就要過去了，在本論文完成之際，我首先要感謝孫承福老師，孫老師在我從論文選題至今給了我不少建議，使我受益良多，是我能順利完成論文的關(guān)

30、鍵所在。孫老師治學(xué)嚴(yán)謹(jǐn)，待人和藹，使我以后工作、學(xué)習(xí)中為人處事的榜樣。同時(shí)還要衷心感謝孫承福老師。孫老師在擔(dān)任班導(dǎo)師期間時(shí)常給我們教授學(xué)習(xí)和工作的實(shí)際經(jīng)驗(yàn)，使我對于日后的工作方向有了明確的定位，也將在我日后的工作中繼續(xù)產(chǎn)生良好的作用。感謝我的家人以及所有在生活中、學(xué)習(xí)中幫助過我或給予過我良好啟發(fā)的人。參考文獻(xiàn)1 Ron Patton.軟件測試(第二版)M.北京:機(jī)械工業(yè)出版社，2006:4-52趙曉華，計(jì)算機(jī)軟件可靠性與質(zhì)量管理M.北京:中國經(jīng)濟(jì)出版社,19923徐仁佐.軟件可靠性工程M.清華大學(xué)出版社，2007.54王小平，曹立明.遺傳算法理論、應(yīng)用與軟件實(shí)現(xiàn)M.西安:西安交通大學(xué)出版社,2

31、001.5許秀梅.基于退火免疫遺傳算法的測試數(shù)據(jù)生成方法研究D.北京：北京交通大學(xué)，20076樂鑫喜.基于退火遺傳算法的測試用例自動(dòng)生成D.武漢：武漢理工大學(xué), 20057律亞楠.基于遺傳算法的測試數(shù)據(jù)生成研究D.汕頭：汕頭大學(xué)，20088錢肖英.基于遺傳算法的測試數(shù)據(jù)自動(dòng)生成方法的研究D.杭州：浙江工商大學(xué)，20089馬志兵.基于遺傳算法的測試數(shù)據(jù)自動(dòng)生成技術(shù)研究D.青島：青島大學(xué)，200910顧鵬.基于遺傳算法的測試用例產(chǎn)生系統(tǒng)關(guān)鍵技術(shù)研究D.武漢：華中科技大學(xué)，200611陳雨.基于遺傳算法的測試用例生成D.上海：東華大學(xué)，200912林惠娟.基于遺傳算法的測試用例自動(dòng)生成技術(shù)研究D.成

32、都：四川大學(xué)，200613 D.Bird and C.Munoz. Automatic generation of random self-checking test casesJ. IBM System J. vol.22, NO.3. 1983:229-24514 P.D.Coward. Symbolic execution and testingJ. Information and Software Teehnology. 1991, 2: 53-6415 C.V.Ramamoorthy, S. Ho. And W.Chen. On the automated generation of Program test dataJ. IEEE Trans. Software Eng. Vol.SE