馬寶英 楊禹軍 范書平

摘 ?要： 近些年，智能優(yōu)化算法在軟件工程領域得到了廣泛的應用，基于搜索的軟件工程技術往往通過設計具體問題的適應值函數(shù)，并基于該函數(shù)在問題的可行解空間中使用優(yōu)化算法尋求最優(yōu)解。本文首先介紹了常用的智能優(yōu)化算法，包括遺傳算法、爬山算法、粒子群算法以及蟻群算法，之后分析并研究這些算法在測試數(shù)據(jù)生成、測試用例選擇以及測試用例優(yōu)先級排序技術中的應用，為有效解決基于搜索的軟件工程問題奠定基礎，促進回歸測試效率的提高。

關鍵詞： 回歸測試;智能優(yōu)化算法;關鍵技術;應用

中圖分類號： TP311.52 ? ?文獻標識碼： A ? ?DOI：10.3969/j.issn.1003-6970.2020.01.004

本文著錄格式：馬寶英，楊禹軍，范書平，等. 智能優(yōu)化算法在回歸測試關鍵技術中的應用現(xiàn)狀研究[J]. 軟件，2020，41（01）：1820

【Abstract】： In recent years， intelligent optimization algorithms have been widely used in the field of software engineering. Search based software engineering technology often designs the fitness function of a specific problem and uses optimization algorithm to find the optimal solution in the feasible solution space of the problem based on the function. This paper first introduces the common intelligent optimization algorithms， including genetic algorithm， hill-climbing algorithm， particle swarm optimization algorithm and ant colony algorithm， then analyzes and studies the application of these algorithms in test data generation， test case selection and test case prioritization technology. It lays a foundation for effectively solving the search based software engineering problems and promotes the efficiency of regression testing.

【Key words】： Regression testing; Intelligent optimization algorithms; Key technologies; Application

0 ?引言

軟件測試是軟件產品質量的重要保證方法，其主要目標是在滿足測試準則的基礎上，用盡可能少的測試數(shù)據(jù)發(fā)現(xiàn)更多的缺陷，以降低軟件開發(fā)的成本[1]?；貧w測試是軟件測試的重要組成部分，尤其是對于大型復雜軟件系統(tǒng)，在每次修改后往往要進行大量的回歸測試，已有研究表明，回歸測試開銷占整個軟件維護預算的50%以上[2]，為了降低回歸測試代價，提高軟件測試效率[3]，近些年國內外學者對高效自動的回歸測試技術展開了深入的研究，測試用例選擇、測試用例的生成以及測試用例的優(yōu)先級排序均是回歸測試的關鍵技術。

近年來，各種基于啟發(fā)式搜索的優(yōu)化技術被應用到軟件測試中，設法將軟件測試問題轉化成一個基于搜索的優(yōu)化問題，遺傳算法、爬山算法、粒子群算法以及蟻群算法是常用的智能優(yōu)化算法，這些優(yōu)化算法已經廣泛應用于基于搜索的回歸測試關鍵技術中，首先介紹這些算法的基本概念。

1 ?常用的智能優(yōu)化算法概述

1.1 ?遺傳算法

遺傳算法[4]模擬了生物在自然環(huán)境中的進化和遺傳，是一種啟發(fā)式的全局優(yōu)化算法。該算法最初是借鑒了進化生物學中的一些現(xiàn)象而發(fā)展起來的，該算法應用群體搜索方式，通過將遺傳算子對當前群體內個體進行交叉、變異、選擇等遺傳運算，產生下一代種群，并通過進化使種群進化到包含或接近最優(yōu)解[5]。遺傳算法由于其計算過程簡單、時間短而得到了廣泛的應用，但與此同時，遺傳算法存在局部搜索能力不強，收斂早等問題。因此，近些年，眾多學者研究將遺傳算法與一些局部搜索算法如梯度法、爬山算法等相結合。

1.2 ?爬山算法

爬山算法是一種簡單的貪心算法[6]，貪心算法在對問題求解時總是做出在當前看來是最好的選擇，也就是說，不從整體最優(yōu)上加以考慮，它所做出的僅是在某種意義上的局部最優(yōu)解，該算法廣泛應用于求解最優(yōu)解或近似最優(yōu)解問題，涉及到測試用例的優(yōu)化問題，主要包括基本貪心算法、額外貪心算法。爬山算法則常用于通過局部搜索來達到某個分支條件。該算法從搜索空間中的一個可行解出發(fā)，將當前節(jié)點與其周圍鄰節(jié)點的值進行比較，返回二者中最大值對應的節(jié)點 （山峰最高點），從而逐漸爬向山峰的高處，該過程通過不斷迭代，直至達到局部最優(yōu)解為止[7]。

1.3 ?粒子群算法

粒子群算法是一種全局隨機搜索算法，該算法模擬鳥群覓食過程中的群體智能行為。該算法的基本思想是：通過隨機選擇粒子，并由這些粒子構成初始種群， 初始化種群，獲得粒子的方向與距離信息，每個粒子均有一個適應值，粒子在每一次迭代過程中，通過比較個體適應值，粒子追尋群體中最優(yōu)的粒子來逐步優(yōu)化候選解，通過多次迭代找到全局最優(yōu)解[8]。

1.4 ?蟻群算法

蟻群算法借鑒了現(xiàn)實中螞蟻集體尋找路徑的行為，螞蟻覓食過程中會分泌出“信息素”[9]，該物質會隨著時間不斷揮發(fā)，螞蟻間利用該信息素進行溝通，一般而言，一條路徑上經過的蟻群數(shù)量越多，該路徑上信息素的濃度越大，結果是后來螞蟻會選擇該路徑的概率就會提高，從而得到最短覓食路 ?徑[10]。蟻群算法參數(shù)少且設置容易，其求解過程無需人工參與，初始路線對搜索結果影響不大，目前，該算法已成為分布式人工智能的熱點研究問題。

2 ?智能優(yōu)化算法在回歸測試關鍵技術中的應用

2.1 ?在測試數(shù)據(jù)自動生成中的應用

近些年，眾多學者研究滿足路徑覆蓋準則的測試數(shù)據(jù)生成方法[11]?；谶z傳算法的測試數(shù)據(jù)生成基本思想是[7]：首先在程序的輸入域中隨機生成一定數(shù)量（即：種群大?。┑臏y試數(shù)據(jù)，對這些數(shù)據(jù)進行編碼，成為初始種群;然后循環(huán)執(zhí)行以下操作：將解碼后的進化個體作為程序的輸入，執(zhí)行插裝后的待測程序，通過適應度函數(shù)評價個體的優(yōu)劣，采用選擇、變異、交叉等遺傳算子以生成新的進化種群。重復上述操作，直到達到終止條件（一般是最大迭代次數(shù)或者是達到適應度函數(shù)的目標值），解碼后的優(yōu)化解可能即為滿足覆蓋準則的測試數(shù)據(jù)。如張巖等[12]通過統(tǒng)計個體穿越目標路徑上節(jié)點數(shù)目，計算個體對生成穿越目標路徑測試數(shù)據(jù)的影響，進而提出“個體貢獻度”，之后將貢獻度進行量化為個體適應值的一部分，保證了穿越難覆蓋節(jié)點的個體有更高概率被保留下來，該方法通過設計實驗驗證了所提出方法在測試數(shù)據(jù)生成的成功率與運行時間等方面的優(yōu)勢。Deepak等[13]則應用遺傳算法與爬山算法來進化生成測試數(shù)據(jù)，該方法的適應值函數(shù)計算考慮了分支距離與層接近度，并通過將層接近度乘以一個常數(shù)來提高其在適應值計算中的比重。

2.2 ?在測試用例選擇中的應用

截止到目前，許多學者已經提出多種方法來解決測試用例的選擇問題，其基本思想是：首先根據(jù)測試目標中的每個測試需求確定出相應的測試用例，所有這些測試用例組成初步的、滿足測試目標的測試用例集;然后針對這個測試用例集采用貪心算法、一些啟發(fā)式算法或整數(shù)規(guī)劃等方法來進行精簡，去掉一些冗余的測試用例。章曉芳等[14]提出應用貪心算法進行測試用例的約簡與優(yōu)化方法，依次選擇能最大限度地滿足測試需求集中尚未被滿足的測試需求，然后將已滿足的測試需求進行刪除，直到滿足所有的測試需求為止;也有一些學者研究應用優(yōu)化算法進化選擇用例子集，主要思想是應用一些優(yōu)化算法及交互策略在測試用例集中搜索符合既定覆蓋標準的極小化的測試用例子集，構造優(yōu)化模型，以剔除冗余測試用例，縮減待執(zhí)行的測試用例集規(guī)模[15]，李澤雪等[16]將Markov決策模型應用到軟件測試過程當中，采用測試用例約簡技術對測試用例集進行簡化，利用貪心算法求得的較優(yōu)解增強蟻群算法初始時刻信息素，通過改進的蟻群算法求得最優(yōu)解。

2.3 ?在測試用例排序中的應用

測試用例優(yōu)先排序技術對測試過程中用例執(zhí)行的先后進行排序，目標是盡早的檢測出程序中的缺陷。智能優(yōu)化算法常用于基于代碼覆蓋的排序技術中，這類方法對測試用例重新排序來盡可能早的實現(xiàn)代碼覆蓋，這些算法中有的應用貪心算法和附加貪心算法來實現(xiàn)基于覆蓋的排序，然而這可能會產生次優(yōu)解，因為結果會在局部較小的搜索空間內產生。為了解決這個問題，目前常用的優(yōu)化技術包括遺傳算法與爬山算法等[17]。

近年來，許多智能優(yōu)化算法均被用于測試用例的優(yōu)先級排序中，如有的方法應用蟻群優(yōu)化技術進行測試用例排序，方法中分別建立了缺陷-測試用例矩陣，執(zhí)行時間-測試用例矩陣，使用率矩陣等，并通過優(yōu)先選擇覆蓋最大缺陷的用例，再選擇覆蓋剩余缺陷的其他用例進行排序，結果表明該方法能減少時間，降低測試代價，與此同時能揭露軟件中的最大缺陷[18]。 也有的方法提出了針對測試點覆蓋的測試用例優(yōu)先排序技術評價指標，并以此為基礎提出一種基于遺傳算法的測試用例排序方法，該方法通過設置遺傳算法的操作算子，并進行了實驗驗證，結果表明該方法可以有效提高軟件測試效率[19]。

3 ?總結

本文在介紹常用的智能優(yōu)化算法基礎上，給出了智能優(yōu)化算法在回歸測試數(shù)據(jù)生成、測試用例選擇及排序中應用的一般過程，分析并研究了優(yōu)化算法在回歸測試關鍵技術中的應用情況，不難得出，智能優(yōu)化算法適應值設置是實現(xiàn)回歸測試關鍵技術的重點，今后將進一步研究如何設置適應值函數(shù)，以提高回歸測試的效率。

參考文獻

[1] 顏樂鳴. 基于工作流的軟件測試過程模型研究[J]. 軟件， 2018， 39（5）： 160-165.

[2] Panigrahi Chhabi Rani， Mall Rajib. A heuristic-based regression test case prioritization approach for object-oriented programs[J]. Innovations in Systems & Software Engineering， 2014， 10（3）： 155-163.

[3] 張琪. 大數(shù)據(jù)背景下軟件測試的挑戰(zhàn)與展望[J]. 軟件， 2018， 39（6）： 181-183.

[4] 聶敬云， 李春青， 李威威， 等. 關于遺傳算法優(yōu)化的最小二乘支持向量機在MBR仿真預測中的研究[J]. 軟件， 2015， 36（5）： 40-44.

[5] 周明， 孫樹棟. 遺傳算法原理及應用[M]. 北京：國防工業(yè)出版社， 2002， 1-20.

[6] 黃玉涵， 曾凡平， 潘能剛等. 基于搜索算法的測試用例優(yōu)化問題研究[J]. 小型微型計算機系統(tǒng). 2011， 32（5） ： 840-844.

[7] 薛猛， 姜淑娟， 王榮存. 基于智能優(yōu)化算法的測試數(shù)據(jù)生成綜述[J]. 計算機工程與應用. 2018， 54（17）： 16-23.

[8] 陳曉文. 基于粒子群算法的FIR濾波器的優(yōu)化設計[J]. 寧德師范學院學報（自然科學版） ， 2019， 31（3）： 257-262.

[9] 丁順， 陳世平. 云計算中基于包簇映射的多目標蟻群資源分配算法[J]. 軟件， 2018， 39（11）： 01-06.

[10] 朱俚治. 基于相似性算法與蟻群算法的聚類算法[J]. 計算機測量與控制. 2018， 26（6） ： 149-151.

[11] 楊子健， 趙逢禹. 基于數(shù)據(jù)流約簡的測試用例生成策略研究[J]. 軟件， 2018， 39（4）： 191-195.

[12] 張巖， 鞏敦衛(wèi). 基于稀有數(shù)據(jù)撲捉的路徑覆蓋測試數(shù)據(jù)進化生成方法[J]. 電子學報， 2013， 36（12）： 2429-2440.

[13] Deepak Garg， Pallvi Garg. Basis Path Testing Using SGC&HGA with ExLB Fitness Function[C]. 4th International Conference on Eco-friendly Computing and Communication Systems， 2015： 593-602.

[14] 章曉芳， 徐寶文， 聶長海等. 一種基于測試需求約簡的測試用例集優(yōu)化方法[J]. 軟件學報， 2007， 18（4）： 821-831.

[15] 成亞玲， 李健， 彭湘華. 基于傳統(tǒng)H算法改進的回歸測試用例優(yōu)化算法.湖南工業(yè)職業(yè)技術學院學報， 2015， 15（2）： 13-20.

[16] 李澤雪， 薛亮， 李相民. 基于改進蟻群算法的軟件測試方法[J]. 兵工自動化， 2017， 36（2）： 70-74.

[17] Chunrong Fang， Zhenyu Chen， Kun Wu， et al. Similarity- based test case prioritization using ordered sequences of program entities[J]. Software Quality Journal， 2014， 22（2）： 335-361.

[18] Ahlam Ansari， Anam Khan， Alisha Khan， etal. Optimized Regression Test using Test Case Prioritization[J]. Procedia Computer Science， 2016， 79： 152-160.

[19] 張衛(wèi)祥， 魏波， 杜會森. 一種基于遺傳算法的測試用例優(yōu)先排序方法[J]. 小型微型計算機系統(tǒng). 2015， 36（9）： 1999-2000.