智能優(yōu)化算法在回歸測試關(guān)鍵技術(shù)中的應(yīng)用現(xiàn)狀研究

馬寶英 楊禹軍 范書平

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

關(guān)鍵詞： 回歸測試;智能優(yōu)化算法;關(guān)鍵技術(shù);應(yīng)用

中圖分類號(hào)： TP311.52 ? ?文獻(xiàn)標(biāo)識(shí)碼： A ? ?DOI：10.3969/j.issn.1003-6970.2020.01.004

本文著錄格式：馬寶英，楊禹軍，范書平，等. 智能優(yōu)化算法在回歸測試關(guān)鍵技術(shù)中的應(yīng)用現(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 ?引言

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

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

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

1.1 ?遺傳算法

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

1.2 ?爬山算法

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

1.3 ?粒子群算法

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

1.4 ?蟻群算法

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

2 ?智能優(yōu)化算法在回歸測試關(guān)鍵技術(shù)中的應(yīng)用

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

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

2.2 ?在測試用例選擇中的應(yīng)用

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

2.3 ?在測試用例排序中的應(yīng)用

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

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

3 ?總結(jié)

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

參考文獻(xiàn)

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

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

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

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

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

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

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

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

[12] 張巖， 鞏敦衛(wèi). 基于稀有數(shù)據(jù)撲捉的路徑覆蓋測試數(shù)據(jù)進(jìn)化生成方法[J]. 電子學(xué)報(bào)， 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]. 軟件學(xué)報(bào)， 2007， 18（4）： 821-831.

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

[16] 李澤雪， 薛亮， 李相民. 基于改進(jìn)蟻群算法的軟件測試方法[J]. 兵工自動(dòng)化， 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)祥， 魏波， 杜會(huì)森. 一種基于遺傳算法的測試用例優(yōu)先排序方法[J]. 小型微型計(jì)算機(jī)系統(tǒng). 2015， 36（9）： 1999-2000.