基于遺傳算法的測試用例自動生成方法綜述

赫彥文，劉紫陽*，李建義，彭新宇

（1.北華航天工業學院，河北 廊坊 065000；2.北華航天工業學院航天軟件聯合創新中心，河北 廊坊 065000）

0 引言

軟件測試是軟件整個生命周期中不可或缺的一環，而測試用例生成是軟件測試工作中的關鍵任務和難點之一。對于復雜程序，設計大量測試用例是一項耗時費力的工作。另外，軟件版本的不斷迭代更新對軟件測試的質量與效率提出了更高的要求。倘若用例設計完全依賴人工，一方面導致測試成本高，另一方面用例可靠性難以保證。為應對這些挑戰，自動化測試應運而生。而用例數據的自動生成一直是自動化測試中的難點，它不僅對測試的質量有著重要影響，而且能大幅度提高測試效率，為降低軟件成本、提高軟件可靠性帶來很大幫助。因此，用例數據的自動生成是自動化測試領域非常具有研究價值的問題。

軟件技術的快速發展以及軟件功能的需求細化使得現在軟件的程序結構愈加復雜，代碼量愈加龐大，甚至有些程序的數據類型還由若干個成員組成，這些都給用例數據的自動生成增加了困難。近年來，隨著群體智能優化算法的出現以及在解決非線性復雜問題方面的出色表現，測試用例自動生成問題的研究方向逐漸轉化為通過群體智能優化算法尋優問題，即將用例生成過程轉換為目標路徑的搜索過程。在這方面已經有許多學者進行研究，取得了大量成果，其中，遺傳算法（Genetic Algorithm，GA）解決了一系列的測試用例生成問題［1-4］，應用最多。本文主要針對遺傳算法及其改進算法在軟件測試用例自動生成中的應用進行系統分析總結。

1 標準遺傳算法的應用

遺傳算法是由美國科學家于1975 年提出的一種全局尋優算法，其思想源于達爾文的生物進化論。與其他群體智能優化算法相比，遺傳算法具有較強的全局搜索能力和魯棒性，因此廣泛應用于用例數據生成。

使用遺傳算法生成測試數據的主要原理是，通過構造適應度函數，使得算法不斷對編碼后的參數進行搜索尋優，直到找到最優解或達到最大進化代數。首先對待測程序進行靜態分析，獲取程序所需參數的類型、數量以及范圍等信息，根據控制流程圖，確定要進行測試的目標分支路徑。然后，根據測試要求構造適應度函數，利用插樁技術對程序進行插樁操作，生成樁程序。最后，通過遺傳算法生成覆蓋目標路徑的測試數據。基于遺傳算法的測試用例自動生成系統模型主要分為三個模塊：測試環境構造、算法模塊以及測試運行，系統結構如圖1所示。

圖1 基于遺傳算法的測試用例生成系統結構圖

與人工模式相比，基于遺傳算法的用例數據生成大量削減了測試用例設計所需的時間，節約了人力成本。

2 改進遺傳算法的應用

2.1 改進遺傳算子

遺傳算子是遺傳算法的核心部分，很大程度上決定著GA 的搜索能力和效率。因此，選擇好的遺傳算子對遺傳算法的結果有著舉足輕重的影響。在標準遺傳算法中，交叉概率和變異概率都為固定值，導致后期種群多樣性差、搜索能力差，文獻［5］引入個體環境適應度和個體對種群的貢獻度，通過交叉算子和變異算子的自適應變化，保證了在種群迭代過程中，即使在進化末期仍具有較強的進化能力，豐富了種群多樣性，解決了算法早熟問題。文獻［6］采用單點交叉，不同于標準遺傳算法固定的交叉概率，適應度值未達到種群平均值的個體以一個較大的概率交叉，而達到的個體通過種群多樣性函數動態調整交叉概率，當種群多樣性較低時提高交叉概率，反之，降低交叉概率，在變異操作中，采用二進制基本位變異，變異規則同交叉類似，以保證個體中的優秀基因不被破壞。針對標準遺傳算法的交叉算子只考慮父代的基因編碼形式、卻忽略個體的學習能力以及環境對個體影響的問題，文獻［7］將冪律法則應用到選擇算子改造中，又在交叉算子中引入環境變量，使得個體能夠修復自身環境，還受環境變量的反作用，改進后的算法具有一定的學習能力。于博等人［8］對上一文獻中的環境-基因雙演化交叉算子又進一步修正，更改了環境變量的取值規則，算法不止面向較優個體進行群體進化，還可以在較優個體周圍的空間內進行搜索。固定的遺傳算子取值在后期可能會破壞較優個體或降低種群多樣性，以上方法通過對遺傳算子的動態改進，對算法的搜索能力起到了積極作用。

2.2 改善適應度函數

適應度函數是遺傳算法尋優的關鍵要素，且具有唯一性，是連接算法與測試用例生成問題的橋梁，通過適應度函數可以評估相應啟發式搜索算法輸入參數的性能優劣。因此，對適應度函數的改善可以有效提高算法性能。鄭超群［9］構造適應度函數時，在Tracey 分支距離的計算方法基礎上，將分支函數進行求和，并對函數進行冪指數變換作為適應度函數，轉換為求最大值的問題。夏春艷等人［10］采用分支距離與層接近度結合的方法設計適應度函數，為權衡分支距離與層接近度的大小，統一為最小化運算并做規范化處理。針對具體的測試目標特點，王丹等人［11］設計適應度函數為代碼覆蓋與測試用例觸發的新的源碼行數的和，該設計避免了過早收斂，同時增強了全局搜索能力。對于生成多路徑測試用例問題，孫建華、姜淑娟［12］采用矩陣存儲個體經過的路徑，對適應度函數做出改善，若產生某條路徑的測試用例數量多了，則降低適應度，使種群朝著測試用例數量少的路徑方向進化，由此產生多條路徑的測試用例，但是當程序結構復雜、路徑較多時，矩陣的維數也會增加，不利于維護，該方法在功能上做到了提升，但就效率而言還有很大進步空間。通常來說，適應度函數的改善會結合其他方向的改進共同實現遺傳算法生成測試用例的應用改進。

2.3 融合其他算法

為進一步提升遺傳算法的性能，大量研究人員將其他群體智能優化算法的思想融入到遺傳算法中，以發揮其他算法的優勢，同時克服遺傳算法的不足。吳昊等人［13］在使用差分求個體適應度值的方法基礎上結合禁忌搜索算法，將優先需要遺傳的個體添加到禁忌表中，將種群中最優解以及接近最優解的個體保存下來，提升了收斂性，加快了最優解的搜索、進化速度，彌補了GA局部搜索能力差的劣勢，還強化了全局搜索能力。文獻［14］將混沌序列引入到交叉、變異操作中控制是否進行操作以及操作點，實驗證明，與標準遺傳算法相比，改進的混沌遺傳算法平均迭代次數更低，將GA 的效率提升了10.8%。王文等人［15］分別采用遺傳蟻群算法和標準遺傳算法對被測程序進行20 次實驗，結果表明，無論是在迭代次數上還是在平均搜索時間上，遺傳蟻群算法的測試用例生成效率都要比標準遺傳算法更好。在多路徑測試用例生成問題上，相較于文獻［12］只在功能上做出改進，仲曉敏等人［16］在效率上也做出了改進，將測試路徑、相應用例的中間態以及不同路徑的適應度值存儲到數據庫中，減少了適應度函數的計算次數，從而實現效率的提高，此外，將模擬退火算法引入變異操作，搜索過程中除了接收優化解，還依據Metropolis 準則以一定概率接收非最優解，算法運行一次產生多路徑的測試用例，大大降低了GA陷入局部最優的概率，增強了選擇優化解、跳出局部最優的能力，實驗證明，種群規模越大，所需迭代次數越小，該算法的優勢越明顯。總之，與其他算法的融合發揮了遺傳算法全局搜索能力強的優點，改善了局部搜索能力弱、易早熟收斂的缺點。

2.4 GA并行化

以上都是串行遺傳算法生成測試用例的方法，在問題維度較大的情況下，遺傳算法要對較多個體進行適應度評估，計算開銷較大，花費時間多［17］。而GA并行化是在群體規模較大時，改善算法性能、提高求解質量的強有力的方法之一。該方法對種群規模進行劃分，每個線程負責一個子種群，各子種群并行運行遺傳算法，然后在子種群進化過程中交換信息。針對GA并行化的線程池模型設計只關注線程實際執行過程，而不考慮線程與進程之間交互的問題，王微微等人［18］提出主線程在為個體分配線程的同時，也分配相應瀏覽器進程的GA 并行化測試用例生成方法，該方法與現有Web應用前后端融合的GA 串行化測試用例生成方法相比，種群平均執行時間減少了81.1%。陳清媛［19］等人設計實現了線程級并行遺傳算法，初始化種群后對種群進行分配，每個子種群并行執行遺傳操作進行路徑尋優，此外，若達到指定遷移代數則進行子種群遷移，該操作使得每個核心的種群多樣性增加，能夠更好地全局尋優，實驗證實，多核并行遺傳算法的應用在運行時間、生成滿足覆蓋條件的用例數量方面，比串行遺傳算法具有更好的效果。總而言之，在測試用例生成問題上，GA 并行化利用智能優化算法的并行性和計算資源的并行，相較于GA串行來說，時間成本會大大降低。

綜上所述，遺傳算法的在測試用例生成問題上的改進策略如表1所示。

表1 遺傳算法改進策略

3 關鍵問題

隨著研究人員的不斷改進，遺傳算法在自動化測試領域發揮了更加重要的作用，但在用例數據生成方面，遺傳算法的應用依然存在三個關鍵問題。

第一，非數值型變量的處理。對于軟件結構復雜、變量類型不同的程序，例如：參數為字符型或為類對象成員，如何選擇合適的編碼策略是需要研究的問題。彭葉蘋［20］將字符型變量的每個字符轉化成正整數（ASCII碼），再將ASCII碼表示成二進制的形式編碼，對于類對象測試數據，將其當作包含了參數值的構造函數與成員函數調用的組合，染色體的第一部分由構造函數和一系列成員函數構成，第二部分為輸入值，也就是第一部分中函數對應參數的輸入。未來期待著對于非數值型變量在編碼問題、適應度函數構造等方面有更深入的研究。

第二，初始參數無法確定。在遺傳算法中，初始化時的種群大小、交叉概率及變異概率的設定是隨機的，是否存在其他設置方式使得算法效率更高也是一個需要進一步探討的問題。例如：在種群的迭代更新中，遺傳算子的效率會受到種群規模影響，如何設置最佳初始種群大小可以成為一個探索方向。

第三，衡量算法優劣沒有統一標準。在已有文獻中，學者們為證實研究的有效性做了大量實驗，但大家選取的測試評價函數不盡相同，有些人選擇基準程序作為待測程序，而有些人選擇的是工業程序，對實驗結果的評判因素大多選擇產生最優解所用時間、迭代次數或覆蓋率等。目前還沒有形成一個統一的標準來衡量不同算法在解決問題時的表現以及對比實驗環境與實際工業應用之間的差異。

4 結語

當前，自動化測試領域的一個研究熱點，就是基于遺傳算法的測試用例生成，發展前景可觀。本文對遺傳算法在自動化測試領域測試用例生成方面的應用進行綜述。首先給出標準遺傳算法在測試用例生成中的應用步驟，隨后從改進遺傳算子、改善適應度函數、融合其他算法和GA 并行化四個方面總結了遺傳算法的改進應用。四種改進方向在求解尋優中各有所長，在實際應用中，應根據具體問題靈活選擇改進方向。盡管在自動化測試領域已經有許多研究圍繞遺傳算法的應用進行展開，但該領域仍然存在多個關鍵問題亟待解決。遺傳算法與近年來新型智能算法的有效結合，例如：雞群算法［21］、鯨魚算法［22］以及最新提出的麻雀搜索算法［23］等，有望成為解決這些難題的可行途徑之一。