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

2、文給出了基于算法的測試用例生成的模型。最后以三角形分類程序為例應用算法進行測試用例生成的模擬，結果顯示，應用算法進行測試用例生成可行。關鍵詞：軟件測試 測試用例 算法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 process , it nee

3、ds 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 cost . And then

4、，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 genetic algorithm

5、, 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 includes three parts w

6、hice.KEY WORDS: software test , test case , genetic algorithm目錄摘要2ABSTRACT3目錄4第一章 緒論61.1 問題的提出61.2 國內外研究現狀71.3 論文研究內容9第二章 軟件測試及算法基本概念102.1 軟件測試基本概念102.1.1 軟件測試的目的102.1.2 軟件測試的原則102.2 軟件測試的難點112.3 算法122.3.1 算法的思想及流程122.3.2 算法的特點142.4本章小結15第三章 基于算法的測試用例生成163.1基于算法的測試用例生成基本內涵163.1.1 軟件測試用例的基本內涵163.1.2

7、基于算法的測試用例生成的基本內涵173.2 基于算法的測試用例生成框架173.3 基于算法的測試用例生成算法實現193.3.1 編碼策略193.3.2 適應度函數及程序插樁203.3.3 策略213.3.4 參數控制233.4 本章小結23第四章 實驗及結果分析244.1 待測程序分析244.1.1 待測程序引入244.1.2 程序流程分析244.1.3 路徑分析254.2 程序插樁254.3 參數設定及程序實現264.3.1 參數設定264.3.2 部分程序實現264.4 結果分析294.5 本章小結31第五章 總結與展望32致謝語33參考文獻34第一章 緒論1.1 問題的提出在信息化普及的

8、今天，計算機在人們的生活和工作中占據著重要地位，使人們的工作效率提高，也使生活更豐富多彩。而作為計算機的重要組成部分，軟件的重要性不言而喻。隨著計算機技術的日益發展，計算機軟件的規模越來越龐大，復雜性越來越高，這就為軟件質量的保證帶來了困難。因為軟件的開發過程大部分是由人的智力活動構成，不可能完美無缺。而軟件缺陷如果不能及時發現，帶來的損失可能是巨大的，有的甚至會危及人的生命。在歷史上臭名昭著的軟件缺陷案例有1：1999年12月3日，美國航天局的火星基地登陸飛船在試圖登陸火星表面時失蹤，原因僅僅是一個數據位的意外更改；美國愛國者導彈防御系統曾在幾次對抗導彈戰役中失利，其中一次竟然誤使28名美國

9、士兵喪生，原因是一個很小的系統時鐘錯誤導致系統累計拖延了100多個小時使跟蹤系統失去準確度；還有就是大名鼎鼎的“千年蟲”問題，起因是在20世紀70年代，為了節省硬盤空間，美國某位程序員在編寫工資系統時將4位數日期（如1975）改成了2位數日期（如75），該缺陷一直拖到1995年都沒有修復，最終給全球帶來了高達數億美元的損失等等。作為提高軟件質量的重要手段，軟件測試越來越受到重視。在美國的微軟公司，測試人員和開發人員的比例達到了2：12。軟件測試伴隨著整個開發過程，是一個非常復雜的過程，其消耗的人力和資金一般占整個項目的一半左右。而在某些特別重要的軟件開發過程中，為保證軟件的質量，測試的費用甚至

10、是其它各階段之和的3到5倍3。測試過程中，測試人員通常需要分析、設計和執行大量的測試用例，從而耗費了大量資源，因此找出合理的測試用例生成方法可以有效縮短測試時間，減少損耗，一般可以有效降低整個項目的4%費用4。然而，目前生成測試用例的方法主要是向前核查法和逆向回溯法，測試人員根據自己的項目經驗手工為指定的程序路徑生成測試數據5。向前核查法是指沿預期的路徑向前檢查，確定到每一個判斷點時變量所能提供的最寬數值區間，然后繼續前行，從而將多個變量的可能取值范圍逐漸縮小，到達程序出口后，就能找到覆蓋這條路徑所需的輸入數據。逆向回溯法正好相反，是指從期望執行的程序位置出發，逆向回溯，在每個判斷點處逐漸調整

11、各變量取值，直到退到程序入口，即獲得所需的輸入數據。向前核查法和逆向回溯法的局限性是，對某些條件要求苛刻的路徑使用時非常困難，同時由于大多數程序中包含的路徑數非常多，如果按每條路徑手工測試，顯然帶來的工作量是非常巨大的。由于測試的工作量大、測試過程的重復性高等特點，自動化測試正逐漸得到廣泛的應用。很多測試工具的使用大大提高了測試人員的工作效率，有效減少了項目開支。然而這些工具主要為測試的執行、管理和度量工具，在測試用例自動生成方面還不完善。而在軟件測試過程中，動態測試作為測試的重要環節占了很大比例，動態測試的關鍵正是測試用例的生成問題。因此，尋找一種有效的測試用例生成方法是提高測試自動化的重中

12、之重。1.2 國內外研究現狀自上世紀60年代起，國內外的學者專家對測試用例的自動生成提出了很多方法，應用較為廣泛的有隨機法、靜態法、動態法以及試探法5 6 7 8 9 10 11 12。D.Bird13等提出了采用隨機法生成測試用例，其思想是不受限制地隨機產生大量的測試用例。該方法產生測試用例的成本很低，在某些抽樣測試中效果較好，但是該方法的針對性較弱，在輸入空間為無窮大時產生的測試用例集非常龐大，測試效率低，現在的很多工具都是采用的該方法。靜態法的典型代表是符號執行法，由14和C.Ramanmoorthy 15 16等人提出。該方法的主要思想是把符號值作為程序輸入，靜態“執行”指定路徑的語句

13、，從而得到變量的值。這里所謂的執行，是指按照程序執行的順序將相應的變量用符號表達式代換。該方法的缺點為需要進行復雜的代數運算，難以處理依賴于輸入變量的循環條件、數組元素下標和模塊調用的情況，特別對于動態的面向對象程序不適合使用。與靜態法相對應的是動態法，該方法的基本思想是從輸入空間中任取一個假設解作為初始輸入，通過實際運行程序不斷調整輸入，使得程序實際執行路徑向指定路徑不斷逼近，直到與指定路徑完全一致。Korel17法是動態法的典型代表：其采用的是步進的方式執行程序，即一次只前進一個分支謂詞；Korel還提出了“謂詞函數”的概念，用來度量分支謂詞的接近滿足程度。然而，由于Korel法一次只考慮

14、一個分支謂詞，使用回溯技術，所以要進行大量的迭代，浪費了大量的資源。而且由于對于非線性路徑約束，該方法只能找到局部極小值，當謂詞函數有多個局部極小值時顯然將難以找到目標路徑的解。除此之外，動態法還包括程序插裝的方法和迭代松弛法，M.Gallagher和Neelam Guptal18分別對這兩種方法進行了全面的闡述。第四種算法是試探法，該方法的基本思想是從輸入數據空間中選擇輸入數據，運行程序，將運行結果結合概率論的思想產生新的數據繼續進行試探。其受搜索空間限制條件的約束小，且不需要其它輔助性信息，對于很多高復雜度問題（如大空間、多峰、非線性、全局優化等）具有獨特的優勢和高效性。試探法主要包括算法

15、、模擬退火算法、禁忌搜索算法、混合策略的算法等。自20世紀90年代起，算法因其獨特的優點而開始被廣泛的用于測試用例的生成領域，并取得了良好的研究成果。算法模擬生物學中的變異原理，采用編碼技術將待求數據映射到基因空間，并通過選擇、交叉、變異等操作和優勝劣汰的自然選擇確定搜索方向，從而找到最優解。實驗證明，該算法具有隱性并行性和全局尋優能力，可以自動獲取搜索過程中的有關信息并用于指導優化。Jones 等人19的實驗表明，為使三角形分類等程序達到分支覆蓋，算法生成的測試數據比隨機法小一到兩個數量級。Jin-Cherng Lin等人 20 等人對適應度函數進行了研究，提出了使用廣義海明距離來構建適應度

16、函數。莢偉21分析了算法在測試用例產生這一問題上的可行性，提出了要有效解決該問題，必須從以下幾個角度進行研究：參數的編碼方法、適應度函數的構造、算子的設計以及算法參數的選擇等。Berndt等人 22將輸入空間劃分成多個區間，根據待選輸入的多種特性創建了一個最小化函數,使用簡單算法進行求解,并使用了求解過程中的化石記錄來指導求解過程。景志遠23則從數學的角度分析了將MGA和K均值等改進的算法應用于測試用例的自動生成。蔡立志等人24提出了一種基于算法的成對測試生成方法,該方法用于選擇當前局部優化覆蓋的測試用例，以此構建滿足成對測試基準的測試用例套，有效降低了相同覆蓋率下的測試用例數量。陳雨等人25

17、將自適應算子和禁忌搜索思想融入到算法中， 充分發揮算法的全局搜索和禁忌搜索算法局部搜索優勢, 提高了測試數據的生成能力。全君林等人26提出了一種應用于軟件回歸測試過程中的基于算法的最小化測試用例集算法模型，該算法較一般的優化算法具有更高算法性能與效率。1.3 論文研究內容本文主要做了以下方面的研究：（1）廣泛閱讀了國內外相關文獻資料，對軟件測試和算法的應用現狀進行了概述，認為使用算法進行測試用例生成可行。（2）分析了使用算法進行測試用例生成的基本內涵，提出了算法框架及對算法進行實現的具體策略。（3）以三角形分類程序為例進行試驗，分析了試驗結果，證實了算法的優越性。第二章 軟件測試及算法基本概念

18、2.1 軟件測試基本概念2.1.1 軟件測試的目的1983年IEEE在“軟件工程標準術語”中將軟件測試定義為：“使用人工或自動手段來運行或測定某個軟件系統的過程，其目的在于檢驗該被測軟件是否滿足規定的需求或是衡量預期結果和實際結果之間的差別?！倍x中指出軟件測試的目的是“檢驗該被測軟件是否滿足規定的需求或是衡量預期結果和實際結果之間的差別”Grenford. J. Myers在其著作The Art Of Software Testing中提出了與軟件測試相關的三個重要觀點，指明了軟件測試的目的為：軟件測試是程序的執行過程，目的在于發現錯誤；一個好的測試用例是指很可能找到迄今為止尚未發現的錯誤的

19、用例;一個成功的測試是指發現了迄今為止尚未發現的錯誤的測試。由此可見，軟件測試的目的可以概括為：首先，軟件測試要以最少的人力、物力，盡快找出軟件中潛在的各種缺陷，通過修正這些缺陷，提高軟件產品質量，盡量減少軟件產品發布后由潛在的軟件缺陷帶來的可能的商業風險。其次，通過分析軟件缺陷產生的原因，可以幫助發現當前開發開發過程中的軟件過程缺陷，以便進行軟件過程的改進。同時，通過對測試結果的分析整理，還可以修正軟件開發規則，并為軟件可靠性分析提供依據。 軟件測試的原則軟件測試作為一門獨立的計算機軟件技術，在執行過程中必須遵守一定的原則，以保證測試效果。軟件測試的專家們經過長期的實踐，總結出了軟件測試的原

20、則應如下：應把“盡早和不斷地進行軟件測試”作為軟件開發者的座右銘。實踐證明單元測試能夠盡早發現問題,減少后期測試的錯誤量。單元測試過程中可以使用相應白盒測試工具（如Junit，Jtest等）進行輔助測試，以提高測試效率。測試用例應由測試輸入數據、測試執行步驟和與之對應的預期輸出結果三部分組成。應當避免由程序員檢查自己的程序。特別在后期的性能測試及系統測試中，應避免程序員測試自己的程序。這其中除了某些心理因素外，該原則還可避免由于程序員個人的慣性思維而導致的某些理解錯誤。測試用例的設計要確保能覆蓋所有可能路徑。在設計測試用例時，應當包括合理的輸入條件和不合理的輸入條件。不合理的輸入條件是指異常的

21、、臨界的、可能引起問題的輸入條件。充分注意測試中的群集現象。經驗表明，測試后程序殘存的錯誤數目與該程序中已發現的錯誤數目或檢錯率成正比。應該對錯誤群集的程序段進行重點測試。嚴格執行測試計劃，排除測試的隨意性。軟件測試是有組織、有計劃、有步驟的活動。測試計劃應包括：所測軟件的功能，輸入和輸出，測試內容，各項測試的進度安排，資源要求，測試資料，測試工具，測試用例的選擇，測試的控制方法和過程，系統的配置方式，跟蹤規則，調試規則，以及回歸測試的規定等等以及評價標準。應當對每一個測試結果做全面的檢查。妥善保存測試計劃，測試用例，出錯統計和最終分析報告，為維護提供方便。2.2 軟件測試的難點（1）測試用例

22、設計測試用例及測試例程是其設計者對被測對象實現原理和外部需求的理解，能否正確反映對被測對象的質量要求，很大程度上取決于其設計者的分析、理解和設計能力。這是一種缺乏指導性方法的、不易制訂標準或規范的、需要“技巧”的設計活動。（2）測試管理目前缺乏測試管理方面的資料，幾乎沒有可供參考的、已實現的、完整的測試管理與測試實施模式。（3）測試的組織軟件測試的有效實施需要開發組織與測試組織充分配合。雖然測試活動看似是對開發人員勞動成果的不斷“挑剔”，但測試工作的出發點是：確保開發人員的勞動成果成為可被接收的、更高品質的軟件產品。因此，測試人員應向開發人員謙虛求教，在測試工作中真正發揮作用，為保證軟件產品的

23、高質量起盡可能大的作用。測試的組織者應在促進上級組織協調各組織工作方面發揮作用。（4）測試的估計有效的測試工作需要投入足夠的人力和物力，需要對工作的難度和消耗有充分的估計。測試的組織者也應在促進上級組織對資源的統一調度方面發揮作用。2.3 算法 算法的思想及流程算法（genetic algorithm）是模擬達爾文的選擇和自然淘汰的生物進化過程的計算模型。該算法最先于1975年由美國的J.Holland教授提出。其主要特點是直接對結構對象進行操作，不存在求導和函數連續性的限定；具有內在的隱并行性和更好的全局尋優能力；采用概率化的尋優方法，能自動獲取和指導優化的搜索空間，自適應地調整搜索方向，不

24、需要確定的規則。算法作為一種不依賴具體問題的直接搜索方法受到廣泛關注，它是現代有關智能計算的關鍵技術之一。算法的思想源于生物學和適者生存的自然選擇規律，因此是具有“生存+檢測”的迭代過程的搜索算法。它以一個群體中的所有個體為對象，并利用隨機化技術指導對一個被編碼的參數空間進行高效搜索。算法將問題的解空間映射為空間，對解空間進行編碼，即將每個可能的解用一串二進制或十進制數字串表示，稱為一個染色體，解的每個分量稱為一個基因。算法開始時先隨機給出一群染色體，即候選解，由預先設定的某個評價指標計算每個染色體的適應值，將適應度低的染色體淘汰掉，而保留適應度高的優良染色體，然后對這些染色體進行選擇復制、交

25、叉和變異等操作，從而產生新的一代染色體群體。這樣一代一代的“進化”，直至找到算法的最優解，即適應值滿足條件的解。由于算法產生的“后代”是由優秀的“父代”和“母代”產生的，因此繼承了上代的優良性態而優于上代，從而使算法向著最優解的方向進行，直到滿足預先設定的條件。算法過程包括了編碼、產生初始群體、計算適應值、選擇、交叉、變異等操作。其一般流程圖如圖2-1所示：j:=0選擇變異個體執行變異將變異結果添加到新群體中j:=j+1j=PmM？YN執行交換j:=j+1根據適應度選擇兩個交換個體j:=0將交換后的兩個新個體添加到新群體中j=PcM？NYj:=0根據適應度選擇復制個體執行復制將復制結果添加到新

26、群體中j:=j+1j=PsM？Y開始Gen:=0自左向右執行一次遺傳算子計算群體中各個體適應度終止輸出結果隨機產生M個初始群體確定字符串長度L滿足終止條件？YNNPsPcPmGen:=Gen+1圖2-1 算法流程圖 算法的特點算法是一類可用于復雜系統優化計算的搜索算法，與其他一些優化算法相比，它的主要特點有如下幾點27：（1）算法以決策變量的編碼作為運算對象，而傳統優化算法往往直接利用變量的實際值來進行優化計算。這種對決策變量的編碼處理方式，使得我們在優化計算過程中可以借鑒生物學中染色體和基因等概念以及和進化機理。特別是對些無數值概念或很難有數值概念，而只有代碼概念的優化問題，編碼處理方式更顯

27、示出了其獨待的優越性。（2）算法直接以目標函數值作為搜索信息，而不需要目標函數的導數值等其他輔助信息。這個特性對很多目標函數難以求導的優化問題，以及組合優化問題等，應用算法時就顯得比較方便。而且，直接利用目標函數值或個體適應度，也可使得我們可以把搜索范圍集中到適應度較高的部分搜索空間中，從而提高了搜索效率。（3）算法同時使用多個搜索點的搜索信息，而傳統的優化算法往往是從解空間中的一個初始點開始最優解的迭代搜索過程。單個搜索點的搜索效率不高，甚至可能使搜索過程陷于局部最優解而停滯不前。算法通過對個體組成的群體進行操作運算，產生新的群體，其中包含的群體信息可以避免搜索一些不必搜索的點，所以實際上相

28、當于搜索了更多的點，這是算法所特有的一種隱性并行性。（4）算法使用概率搜索技術，而很多傳統的優化算法往往使用的是確定性的搜索方法。確定性的方法由于固定了點與點之間的轉移方法和轉移關系，往往可能使得搜索永遠達不到最優點，因而也限制了算法的應用范圍。而算法屬于一種自適應的概率搜索技術，其選擇、交叉、變異等運算都是以一種概率的方式來進行的，從而增加了算法搜索過程的靈活性和搜索效率。2.4本章小結本章首先介紹了軟件測試的一些基本概念，對軟件測試的知識做了系統的介紹，包括軟件測試的目的、原則、過程，介紹了了軟件測試的主要技術難點，其中包括了測試用例的設計。本章后半部分介紹了算法的基本概念，包括算法的思想

29、、流程及特點。第三章 基于算法的測試用例生成3.1基于算法的測試用例生成基本內涵 軟件測試用例的基本內涵測試用例是為某個特殊目標而編制的一組測試輸入、執行條件以及預期結果，以便測試某個程序路徑或核實是否滿足某個特定需求，包含輸入和輸出兩部分。構造測試用例的目的是為了檢查被測軟件的操作結果是否與預期的需求相吻合，確定應用程序的某些特性是否正常的工作等。測試用例的質量可以用以下四個標準來描述:（1）有效性:是否能夠發現缺陷，或者至少可能發現缺陷；（2）仿效性:可仿效的測試用例能夠測試多項內容，從而減少測試用例的數量；（3）經濟性:測試用例的執行、分析和調試是否經濟；（4）修改性:軟件修改后測試用例

30、的維護成本。實踐中，設計測試用例需遵守一定的原則，這些原則主要有：（1）全面性包括：應盡可能覆蓋程序的各種路徑；應考慮存在跨年、跨月的數據；大量數據并發測試的準備等。 （2）正確性輸入界面后的數據應與測試文檔所記錄的數據一致且預期結果應與測試數據發生的業務吻合。 （3）符合正常業務慣例測試數據應符合用戶實際工作業務流程且兼顧各種業務變化的可能。 （4）仿真性 人名、地名、電話號碼等應具有模擬功能，符合一般的命名慣例；不允許出現與知名人士、小說中人物名等雷同情況。 （5）可操作性 測試用例中應寫清測試的操作步驟，不同的操作步驟相對應的操作結果。 基于算法的測試用例生成的基本內涵使用算法實現測試用

31、例的自動生成可描述為12：應用算法來求解一組優化的測試用例。在每一步進化計算過程中，測試用例自動生成器使用當前群體（測試用例）驅動被測試程序的執行，每一個測試用例的執行路徑被跟蹤和記錄，以最大化程序執行路徑的覆蓋為適應性目標函數進行計算，產生出下一代群體。在多代進化之后，得到最優種群或超過特定的循環限制條件而結束。因為測試用例的自動生成是在一個數據域中尋找滿足給定的測試標準的一組測試輸入數據的過程，所以近年來出現了把測試用例的生成問題轉化成路徑搜索問題的思想。由于一般情況下，測試數據的產生是一個不可判定性問題，再加上被測程序的規模和復雜性，一般的搜索算法受到了極大的限制。算法在處理不確定搜索問

32、題時有著非常明顯的優勢。算法能針對程序路徑生成大量有效測試用例，因此符合測試用例設計的全面性、正確性等原則。生成的測試用例符合上節中的測試用例設計標準，特別是有效性和經濟性等，由此可見算法應用于測試用例生成是可行的。3.2 基于算法的測試用例生成框架本文基于算法的測試用例生成基本流程如下所示：（1）分析源程序代碼，獲得程序控制流程圖；（2）由程序控制流程圖得到程序分支路徑集合，選擇目標路徑；（3）根據各謂詞條件給程序插樁并制定適應度函數；（4）設定算法參數，包括群體大小、變異率等，隨機產生初始測試數據集合；（5）使用測試數據執行經過插裝的源代碼，獲得適應度值，根據適應度值判斷，若滿足程序終止條

33、件則輸出結果并退出程序，若不滿足條件則進入步驟（6）；（6）根據得到的適應度值，使用算法的選擇、交叉、變異等操作，生成新的測試數據，并回到步驟（5），重復執行；Y靜態分析路徑選擇程序插樁變異GA初始化測試環境構造選擇交叉解碼評估結束N遺傳算法驅動模塊待測程序樁模塊測試運行環境程序框架如圖3-1所示，包含測試環境構造、算法和測試運行環境三部分。圖3-1 程序框架圖測試環境構造部分是整個系統的基礎，它主要利用靜態分析提供的基本信息并借助于各種插裝技術來構造相應的測試運行環境。算法部分是系統的核心，它主要按照第一部分生成的編碼參數格式構造相應的染色體串，并生成初始種群，然后通過對該種群進行反復的GA

34、運算（選擇、交叉和變異）從而引導種群不斷地向目標值進化直到最終找到解或達到限定的運行代數為止。最后部分是測試運行環境。算法第二部分需要對種群中每一個個體的優劣進行評估，它主要是通過實時地調用并運行插裝后的測試系統來返回適應度值，從而來指導算法的搜索。3.3 基于算法的測試用例生成算法實現 編碼策略使用算法求解問題時，必須將目標問題的實際表示與算法的染色體位串結構之間建立映射關系，這一過程即為編碼。編碼就是將目標問題的解用一種特定字符串來表示，從而將問題的解空間（有效的候選解，即表現型個體）與算法的碼空間（基因型個體）相對應。編碼過程是算法的基礎，編碼方法除了決定了個體的染色體排列形式之外，還決

35、定了個體從GA空間的基因型變換到問題空間的表現型時的解碼方法（即為編碼方法的逆方法）。同時，編碼方法也影響到交叉算子、變異算子等算子的運算方法。由此可見，編碼方法的好壞是影響算法性能及效率的重要因素。一個好的編碼方法，有可能會使得交叉運算、變異運算等操作可以簡單地實現和執行。相反，選擇了不當的編碼方法有可能會使得交叉運算、變異運算等操作難以實現，甚至可能會產生很多不屬于可行解集合內的無效解。因此Goldberg提出了三條編碼評估規范：完備性（Completeness）：問題空間中的所有點都能作為GA空間中的點(染色體)表現。健全性（Soundness）：GA空間中的染色體能對應所有問題空間中的

36、候選解。非冗余性（Nonredundancy）：染色體和候選解一一對應。常見的編碼方法有二進制編碼方法、格雷碼編碼方法、浮點數編碼方法、符號編碼方法等，在應用中具體使用何種編碼方法應根據問題的實際情況而定，這里我們使用二進制編碼方法。二進制編碼方法是算法中使用最多的編碼方法，不光是由于其編碼解碼操作簡單，便于實現交叉、變異等操作，而且該編碼方法符合最小字符集編碼原則，能使染色體與候選解一一對應。使用二進制編碼方法進行編碼時，先根據問題所要求的求解精度確定符號串的長度，假設某一參數的取值范圍為Xmin,Xmax，可用長度為L的二進制編碼符號來表示該參數，則能產生2L個不同的編碼，設編碼精度為，則

37、：Xmin 表示為 0000.000=0 Xmax 表示為 1111.111=2L -1= （3-1）若某個體編碼為X：aLaL-1aL-2.a2a1 ，則其解碼公式為：x= （3-2） 適應度函數及程序插樁（1）適應度函數在算法中，不需要用到搜索空間的知識，而使用適應度函數對染色體進行評價，一般來說，適應度高的染色體的評價較高，適應度低的染色體評價較低而可能被淘汰，因此，適應度函數直接決定了種群的進化方向，對算法的好壞具有很大影響。同時，適應度函數的復雜度是算法復雜度的主要組成部分，因此適應度函數要求盡可能簡單。適應度函數通?？梢詮哪繕撕瘮缔D化而來。一般來說，要求適應度的取值越大越好。但在實

38、際問題中，有的目標函數是求最大值（如利潤問題），也有的目標函數是求最小值（如費用問題）。因此在很多場合需要將目標函數轉換為最大值形式并且函數值為非負的適應度函數。（2）程序插樁在程序流程圖中，每個分支都可以用一個判斷表達式來表示，該判斷表達式稱為分支謂詞，其作用是描述了程序遍歷該分支的條件，如判斷語句“if(a>b).”中分支謂詞為“a>b”。分支謂詞的一般形式為：E1 op E2，E1和E2是算數表達式，關系運算符。每個分支謂詞都可以轉換成等價形式為：F rel 0，其中F為分支函數，其構造方法如表3-1所示。表3-1 分支函數的構造分支謂詞分支函數relE1>E2E2-E

39、1<E1>=E2E2-E1<=E1<E2E1-E2<E1<=E2E1-E2<=E1=E2abs(E1-E2)=E1!=E2-abs(E1-E2)<由表可知，當分支謂詞為假時，分支函數為正；當分支謂詞為真時，分支函數為負。而要使某條路徑被覆蓋時，該路徑上的所有分支謂詞應取真值，則分支函數應為負。由于分支函數直接構成了適應度函數，不能為負值，故而將分支函數修改為：當分支謂詞為真時，分支函數取0；當分支謂詞取假時，分支函數依然取真值。因此如果某條路徑的所有分支函數都為0時表示該路徑被全部覆蓋。在本文中，使用的適應度函數為： （3-3）其中，f(xi)為

40、各分支插樁后的分支函數值。 策略（1）選擇策略選擇運算也叫復制運算，模擬了生物界優勝劣汰的自然選擇現象。通過選擇將優勝的個體直接到下一代或通過配對交叉產生新一代個體再到下一代。選擇運算的依據是個體的適應度，適應度高的個體被選擇到下一代的概率就大，甚至可能被多次復制，而適應度低的個體則可能一次都沒被選中而淘汰。選擇的概率一般取Ps 為0.1至0.2 。常用的選擇運算的方法有輪盤賭轉法、隨機遍歷抽樣、錦標賽選擇等，其中以輪盤賭轉法最為常用。該算法將所有染色體的適應度總和看做一個輪子的圓周，而各染色體按其適應度占適應度總和的比例值大小占據一個扇區。每次進行選擇時相當于輪盤的一次轉動，轉到哪個扇區則該

41、扇區的染色體被選中。這樣適應度越高的染色體被選中的概率就越大。若某染色體的適應度為f(xi)，則被選中的概率為： （3-4）圖3-2是一個簡單的賭輪的例子：13%              35%         15%    0.67     37%|-|-|-|-*-|個體1    &

42、#160;        個體2              個體3         個體4圖3-2 輪盤賭轉法示意圖3-2中隨機數為0.67落在了個體4的段內，本次選擇了個體4。（2）交叉策略交叉運算是算法中產生新個體的主要手段，其模擬的是生物學中的雜交現象。交叉運算通過使兩個體的局部交換而使雙方的優點有可能結合產生更好的新個體

43、。一般控制產生交叉運算的概率Pc 為0.5至0.8 。在二進制編碼中，根據交叉點的不同可以分為單點交叉、兩點交叉、均勻交叉等。在本文中采用的是單點交叉的方法，即首先在親代中隨機選取一個交叉點（染色體的某個碼位），然后將兩個親代在該點及之后的染色體部分進行交換。（3）變異策略變異運算模擬的是生物中的基因突變現象。通過變異操作可以增強算法中群體的多樣性，防止未成熟收斂現象，同時也使算法具備了局部隨機搜索能力，是實現全局優化性能的重要算子之一。通常，變異的控制概率較小，Pm 一般取值為0.001至0. 1。在二進制編碼方式中，變異運算即是將某些基因位上的基因值取反，即0變1或1變0。一般變異個體的選

44、擇及變異位置都是隨機確定的。二進制編碼中的變異方法有基本位變異、均勻變異、高斯變異和二元變異等。本文采用的是基本位變異方法，即先隨機選擇某變異個體，再隨機確定染色體的一個變異點將該碼位置反。 參數控制除了上面提到的選擇、交叉、變異的概率外，在算法中還有一些參數主要如下：種群規模 群體規模較大可以增加算法的多樣性，提高GA搜索的質量，防止算法未成熟收斂。但是群體規模大使個體適應度的計算量大大增加，影響了算法的效率。因此應根據不同的實際情況確定不同的種群規模。Goldberg證明了在二進制編碼的前提下，若個體長度為L，則種群規模的最優值為2L/2。染色體長度染色體長度即是編碼長度，也即是表示個體的

45、字符串的長度。染色體的長度由具體問題決定，當解的取值范圍越大、求值精度越大則染色體長度越大，帶來的計算時間也相應越長。算法終止條件一般來說，算法的終止條件為預先設定的最大進化代數，通常取100到500 。也可以為某一特定條件，事具體問題而定。以上參數為通常情況下的取值，當然并非是固定不變的。在不同的算法中可以根據實際情況作相應的調整，只要能提高算法的運行效率就是可行的。3.4 本章小結本章是論文的核心章節，對算法應用于測試用例的生產方法進行了系統的介紹。首先介紹了算法生成測試用例的基本內含，然后提出了基本框架，最后對本文中算法實現的相關操作進行了描述，包括編碼策略、適應度函數構造、選擇策略、交

46、叉策略、變異策略等。第四章 實驗及結果分析4.1 待測程序分析 待測程序引入本章中將以三角形分類程序為例來驗證算法。三角形分類程序在許多軟件測試研究中被作為基準程序來使用，因為其包含清晰而又復雜的邏輯，并且即使將一個較大范圍的整數作為輸入，也只有少量的輸入組合能滿足代碼的某些特定分支。例如當輸入為1到10 的整數時，1000組輸入只有10組能滿足判斷為“等邊三角形”的分支。三角形源程序為：String tri_type(int a,int b,int c) string type; if(a>b) change(a,b); if(a>c) change(a,c); if(b>

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

48、析通過對程序流程分析可知，該程序對三角形進行分類的語句為圖4-2中標有“”至“”號的分支，對這些分支進行路徑分析如表4-1所示：表4-1 路徑分析路徑號分支結果w1不是三角形W2-普通三角形W3-等腰三角形W4-等邊三角形4.2 程序插樁根據，對待測程序插樁：String tri_type(int a,int b,int c) string type; if(a>b) change(a,b); if(a>c) change(a,c); if(b>c) change(b,c); f1=c-(a+b) ; /插樁1 if(a+b>c) f2=min(abs(a-b),abs

49、(b-c); /插樁2 if(a=b|b=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); /適應度函數 return F; 4.3 參數設定及程序實現 參數設定（1）編碼（2）操作參數在本實驗中，設定操作的參數如表4-2所示：表4-2 操作參數設定種群大小選擇策略及概率交叉策略及概率變異策略及概率最大進化代數100輪盤賭轉法，0.1單點交叉，0.8基本位變異，

50、0.1100（3）算法終止條件本實驗中設定算法終止條件為滿足以下兩個條件之一：找到最優解，即適應度為100的解；達到最大進化代數，當程序進化滿100代后，不管有沒找到最優解都將退出。 部分程序實現本文中的三角形分類程序是在Microsoft Visual Studio2005的環境下采用C+語言實現的。以下為該程序的主要算法模塊：（1）染色體定義模塊，該模塊完成了染色體的編碼：struct sides int a;int b;int c; /測試的三個數據bitset<3*BIT> chromosome; /該組的染色體int sufficiency; /該組數的適應度bool i

51、sOp ; /標記是否操作過（2）計算適應度，采用插樁法：int getSufficiency(int a, int b, int c) int f, f1, f2, f3;if(a>b) change(a,b); if(a>c) change(a,c); if(b>c) change(b,c);f1 = c - (a + b); /if(a+b>c)f2 = min<int>(abs(a-b), abs(b-c); /if(a=b|b=c)f3 = abs(a-c); /if(a=c) type=“等邊三角形”; /else type=“等腰三角形”; /

52、else type=“普通三角形”; /else type=“不是三角形”; /return type; if (f1 < 0) f1 = 0; f = ( 100/(1+f1) + 100/(1+f2)+ 100/(1+f3)/3;return f; （3）選擇操作，使用了輪盤賭轉法：void select(sides newGroup, sides oldGroup) resetFlag(oldGroup);int aPosGROUP; /存儲每組數據在轉盤中的位置aPos0 = oldGroup0.sufficiency;for (int i = 1; i < GROUP;

53、i+) aPosi = oldGroupi.sufficiency;aPosi += aPosi - 1; for(int i = 0; i < SELECTION; ) int random = rand()%aPosGROUP - 1; /產生隨即數,0到群體中的最后一組數據所在的位置找到該隨機數所在位置,如果位置重復了就重新選擇for (int j = 0; j < GROUP; j+) if(random <= aPosj) if(!oldGroupj.isOp) newGroupi = oldGroupj; oldGroupj.isOp = true;i+;break; else break; （4）交叉操作，先用輪盤賭轉法選擇，再用單點交叉法進行交叉：void cross(sides newGroup, sides oldGroup) int aPosGROUP; aPos0 = oldGroup