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

（1.北華航天工業(yè)學(xué)院，河北 廊坊 065000；2.北華航天工業(yè)學(xué)院航天軟件聯(lián)合創(chuàng)新中心，河北 廊坊 065000）

0 引言

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

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

1 標(biāo)準(zhǔn)遺傳算法的應(yīng)用

遺傳算法是由美國科學(xué)家于1975 年提出的一種全局尋優(yōu)算法，其思想源于達(dá)爾文的生物進(jìn)化論。與其他群體智能優(yōu)化算法相比，遺傳算法具有較強(qiáng)的全局搜索能力和魯棒性，因此廣泛應(yīng)用于用例數(shù)據(jù)生成。

使用遺傳算法生成測試數(shù)據(jù)的主要原理是，通過構(gòu)造適應(yīng)度函數(shù)，使得算法不斷對編碼后的參數(shù)進(jìn)行搜索尋優(yōu)，直到找到最優(yōu)解或達(dá)到最大進(jìn)化代數(shù)。首先對待測程序進(jìn)行靜態(tài)分析，獲取程序所需參數(shù)的類型、數(shù)量以及范圍等信息，根據(jù)控制流程圖，確定要進(jìn)行測試的目標(biāo)分支路徑。然后，根據(jù)測試要求構(gòu)造適應(yīng)度函數(shù)，利用插樁技術(shù)對程序進(jìn)行插樁操作，生成樁程序。最后，通過遺傳算法生成覆蓋目標(biāo)路徑的測試數(shù)據(jù)?；谶z傳算法的測試用例自動生成系統(tǒng)模型主要分為三個模塊：測試環(huán)境構(gòu)造、算法模塊以及測試運(yùn)行，系統(tǒng)結(jié)構(gòu)如圖1所示。

圖1 基于遺傳算法的測試用例生成系統(tǒng)結(jié)構(gòu)圖

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

2 改進(jìn)遺傳算法的應(yīng)用

2.1 改進(jìn)遺傳算子

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

2.2 改善適應(yīng)度函數(shù)

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

2.3 融合其他算法

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

2.4 GA并行化

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

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

表1 遺傳算法改進(jìn)策略

3 關(guān)鍵問題

隨著研究人員的不斷改進(jìn)，遺傳算法在自動化測試領(lǐng)域發(fā)揮了更加重要的作用，但在用例數(shù)據(jù)生成方面，遺傳算法的應(yīng)用依然存在三個關(guān)鍵問題。

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

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

第三，衡量算法優(yōu)劣沒有統(tǒng)一標(biāo)準(zhǔn)。在已有文獻(xiàn)中，學(xué)者們?yōu)樽C實(shí)研究的有效性做了大量實(shí)驗，但大家選取的測試評價函數(shù)不盡相同，有些人選擇基準(zhǔn)程序作為待測程序，而有些人選擇的是工業(yè)程序，對實(shí)驗結(jié)果的評判因素大多選擇產(chǎn)生最優(yōu)解所用時間、迭代次數(shù)或覆蓋率等。目前還沒有形成一個統(tǒng)一的標(biāo)準(zhǔn)來衡量不同算法在解決問題時的表現(xiàn)以及對比實(shí)驗環(huán)境與實(shí)際工業(yè)應(yīng)用之間的差異。

4 結(jié)語

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