面向多目標(biāo)測試用例優(yōu)先排序的蟻群算法信息素更新策略

邢行　尚穎　趙瑞蓮　李征

摘要：

針對蟻群算法在求解多目標(biāo)測試用例優(yōu)先排序（MOTCP）時收斂速度緩慢、易陷入局部最優(yōu)的問題，提出一種基于上位基因段（ETS）的信息素更新策略。利用測試用例序列中ETS可以決定適應(yīng)度值的變化，選取ETS作為信息素更新范圍，再根據(jù)ETS中測試用例間的適應(yīng)度增量和測試用例的執(zhí)行時間更新路徑上的信息素值。為進(jìn)一步提升蟻群算法求解效率、節(jié)省螞蟻依次訪問測試用例序列的時間，優(yōu)化的蟻群算法還通過估算ETS長度重新設(shè)置螞蟻遍歷測試用例的搜索終點。實驗結(jié)果表明，與優(yōu)化前的蟻群算法及NSGAⅡ相比，優(yōu)化后的蟻群算法能提升求解MOTCP問題時的收斂速度，獲得更優(yōu)的Pareto解集。

關(guān)鍵詞：

蟻群算法； 信息素更新； 多目標(biāo)的測試用例優(yōu)先排序； 回歸測試； 上位基因段

中圖分類號：

TP311.5

文獻(xiàn)標(biāo)志碼：A

Abstract：

The Ant Colony Optimization （ACO） has slow convergence and is easily trapped in local optimum when solving MultiObjective Test Case Prioritization （MOTCP）. Thus， a pheromone updating strategy based on Epistaticdomain Test case Segment （ETS） was proposed. In the scheme， ETS existed in the test case sequence was selected as a pheromone updating scope， because ETS can determine the fitness value. Then， according to the fitness value increment between test cases and execution time of test cases in ETS， the pheromone on the trail was updated. In order to further improve the efficiency of ACO and reduce time consumption when ants visited test cases one by one， the end of ants visiting was reset by estimating the length of ETS using optimized ACO. The experimental results show that compared with the original ACO and NSGAⅡ， the optimized ACO has faster convergence and obtains better Pareto optimal solution sets in MOTCP.

英文關(guān)鍵詞Key words：

Ant Colony Optimization （ACO）； pheromone updating； MultiObjective Test Case Prioritization （MOTCP）； regression testing； EpistaticDomain Test Case Segment （ETS）

0引言

測試用例優(yōu)先排序（Test Case Prioritization， TCP）[1]是提升回歸測試效率的重要方法，通過設(shè)定的測試目標(biāo)對測試用例重新排序，優(yōu)化其執(zhí)行次序，提高回歸測試效率。Rothermel等[2]首先提出了平均錯誤檢測率（Average Percentage of Fault Detection， APFD）作為評價最終排序效率的重要標(biāo)準(zhǔn)，但在實際的軟件測試過程中，測試人員無法提前預(yù)知測試用例錯誤檢測信息。Li等[3]提出了平均語句塊覆蓋率（Average Percentage of Block Coverage， APBC）、平均分支覆蓋率（Average Percentage of Decision Coverage， APDC）、平均語句覆蓋率（Average Percentage of Segment Coverage， APSC）等多種測試目標(biāo)來代替APFD測試目標(biāo)。隨著工業(yè)測試要求的不斷提高[4]，只針對單一測試目標(biāo)對測試用例序列進(jìn)行優(yōu)化已不能夠滿足相關(guān)測試需求，因為實際測試過程中需考慮多種因素對軟件質(zhì)量的影響，例如測試成本、時間和代碼修改等因素，所以多目標(biāo)的測試用例優(yōu)先排序問題（MultiObjective Test Cases Prioritization， MOTCP） [5]開始被廣泛研究。在MOTCP中多個目標(biāo)一般存在沖突關(guān)系，為了搜索到基于多個目標(biāo)的最優(yōu)解集，可以將MOTCP問題轉(zhuǎn)化為組合優(yōu)化問題采用進(jìn)化算法解決。其中NSGAⅡ算法[6]具有運行速度快，解集收斂性好的優(yōu)點，近幾年來在多目標(biāo)優(yōu)化問題中得到廣泛的運用[5，7] 。

粒子群算法（Particle Swarm Optimization， PSO）、蟻群算法（Ant Colony Optimization， ACO） [8]等基于搜索的優(yōu)化算法也被應(yīng)用于解決MOTCP問題。由于蟻群算法具有良好的魯棒性、信息素的正反饋機(jī)制等優(yōu)點[9-10]，之前被廣泛應(yīng)用于多目標(biāo)分配問題、路徑規(guī)劃問題、電力系統(tǒng)優(yōu)化問題、數(shù)據(jù)挖掘、參數(shù)識別等問題上，表現(xiàn)出在求解復(fù)雜優(yōu)化問題方面的優(yōu)越性。顧聰慧等[11]提出一種面向MOTCP的蟻群算法，將螞蟻依

次訪問測試用例的次序作為測試用例的執(zhí)行次序。研究發(fā)現(xiàn)，蟻群算法的信息素更新方式是影響算法性能的重要因素之一，也是螞蟻傳遞信息的唯一渠道。其通過收集螞蟻遍歷的測試用例得到的有效信息指導(dǎo)下次迭代中螞蟻遍歷測試用例的過程。文獻(xiàn)[11]在更新螞蟻訪問路徑上的信息素時缺乏考慮測試用例之間的關(guān)系，使路徑上積累的信息素值誤導(dǎo)了螞蟻下次迭代時的搜索方向，致使蟻群算法收斂緩慢且易陷入局部最優(yōu)。蟻群算法最早應(yīng)用于經(jīng)典旅行商問題（Traveling Salesman Problem， TSP）時也出現(xiàn)同樣的問題，不少學(xué)者在信息素更新上提出了很多優(yōu)化方案改進(jìn)蟻群算法[12]。例如：最大最小蟻群算法（Maxmin Ant System， MMAS） [13]通過對信息素設(shè)置最大、最小值、初始值等措施，避免算法陷入局部最優(yōu)；蟻群系統(tǒng)（Ant Colony System， ACS） [14]分別采取了信息素的全局和局部更新方式來提升算法搜索性能。但是現(xiàn)有的優(yōu)化方法對于解決MOTCP中收斂過慢問題的效果并不是特別明顯，本文針對該問題進(jìn)行了研究。

上位性最初在生物遺傳學(xué)中提出，是指某一基因受別的基因抑制而不能表達(dá)出原本性狀的現(xiàn)象。2015年，Yuan等[15]首次提出了基于遺傳算法的測試用例序列中存在上位基因段（EpistaticDomain Test Case Segment， ETS），即測試序列中從第一個測試用例開始到達(dá)到最大適應(yīng)度值的測試用例為止的測試用例序列段。在TCP中，ETS對適應(yīng)度值的影響有決定性作用，位于ETS后的測試用例被ETS抑制。本文針對該特點提出一種基于ETS的信息素更新策略，構(gòu)造適用于MOTCP問題的啟發(fā)式蟻群算法。對于平均語句覆蓋率和有效執(zhí)行時間兩個優(yōu)化目標(biāo)，新策略分析ETS中不同測試用例的語句覆蓋能力，采用局部信息素更新策略更新路徑上的信息素值，引導(dǎo)螞蟻優(yōu)先訪問剩余未訪問的測試用例中具有額外語句覆蓋（Additional Statement Coverage）的測試用例。其次，本文在螞蟻搜索解的過程中通過估算ETS長度設(shè)置搜索終點，相比螞蟻依次訪問全部測試用例節(jié)省了時間，有效提升了算法效率。最后，本文實驗采用SIR（Softwareartifact Infrastructure Repository）庫中的程序及V8開源程序，先比較了不同的信息素更新策略對蟻群算法測試用例排序能力和算法收斂速度的影響，然后將優(yōu)化后的蟻群算法與NSGAⅡ進(jìn)行實驗對比分析，結(jié)果表明，優(yōu)化后的蟻群算法能避免陷入局部最優(yōu)，收斂速度也大幅度提高。

本文的主要工作如下：針對MOTCP問題，深入研究ETS中測試用例間的關(guān)系，提出基于ETS的信息素更新策略，累積每次迭代中非支配解的信息素指導(dǎo)下一次迭代時的搜索。為進(jìn)一步提升蟻群算法的效率，在螞蟻構(gòu)造解的過程中重新設(shè)置搜索終點，以減少螞蟻構(gòu)造解時的時間消耗。優(yōu)化后的蟻群算法在MOTCP問題的求解能力和收斂速度上都有大幅度提升。在有限的迭代次數(shù)內(nèi)，該方法的執(zhí)行效率明顯優(yōu)于NSGAⅡ算法的測試用例優(yōu)先排序方法。

1相關(guān)研究

1.1MOTCP相關(guān)問題描述

MOTCP是在測試用例集中尋找同時滿足多個優(yōu)化目標(biāo)的最優(yōu)測試用例執(zhí)行序列的過程。通常使用非支配排序技術(shù)對測試用例進(jìn)行多目標(biāo)排序，其中對于兩個優(yōu)化目標(biāo)的非支配排序規(guī)則定義如下：

定義1已知一個測試用例集合T，T的所有測試用例排列PT以及評價測試用例序列優(yōu)劣的目標(biāo)函數(shù)向量F=[f1， f2]， f1和f2是兩個優(yōu)化目標(biāo)函數(shù)f：PT→R，其中R是實數(shù)。T′和T ″是測試用例集合T中的兩個測試用例執(zhí)行序列，T′，T ″∈PT。

1）當(dāng)f1 （T′） ≥ f1 （T ″）且f2 （T′） ≥ f2（T ″）或者f1 （T′） ≤ f1 （T ″）且f2 （T′） ≤ f2 （T ″）時，稱T′對于兩個優(yōu)化目標(biāo)能支配T ″或者被T ″支配。

2）當(dāng)f1 （T′） ≥ f1 （T ″）且f2 （T′） ≤ f2 （T ″）或者f1 （T′） ≤f1 （T ″）且f2 （T′） ≥ f2 （T ″）時，稱T′和T ″互不支配。

若測試用例序列集合PT′（PT′PT）中的元素互不支配且不被其他測試用例序列所支配時，則稱PT′是Pareto最優(yōu)解集（非支配解集）。MOTCP的目的就是在測試用例序列集合中尋找最優(yōu)解集的過程。為了評價MOTCP在回歸測試中的效率，本文采用平均語句覆蓋率（Average Percentage of Segment Coverage， APSC）和有效執(zhí)行時間（Effective Execution Time， EET）作為MOTCP的兩個優(yōu)化目標(biāo)，分別對應(yīng)兩個優(yōu)化目標(biāo)函數(shù)。APSC表示測試用例序列覆蓋被測程序的語句的速度；EET表示測試用例序列首次達(dá)到語句全覆蓋時執(zhí)行測試用例的時間消耗。測試用例序列的APSC值越高且EET值越小表示其回歸測試的效率越高。APSC和EET的計算公式分別如（1）、（2）所示：

APSC=1-TS1+TS2+…+TSNNM+12N （1）

EET=∑M′i=1ETi（2）

其中：M為測試用例的數(shù)量，N為被測程序中的語句數(shù)，TSi表示第一個覆蓋程序語句i的測試用例T在執(zhí)行序列中的位置。當(dāng)執(zhí)行到M′個測試用例時達(dá)到被測語句全覆蓋，ETi表示執(zhí)行第i個測試用例的執(zhí)行時間。

1.2面向MOTCP的蟻群算法

蟻群算法是受螞蟻覓食行為啟發(fā)提出的一種群體智能算法。螞蟻在覓食的過程中會在經(jīng)過的路徑上分泌一種叫作信息素的分泌物，并且螞蟻能感知路徑上信息素的存在和強(qiáng)度，指導(dǎo)自己前進(jìn)的方向，傾向于朝著信息素濃度高的方向移動。所以大量螞蟻覓食的過程形成一種信息的正反饋機(jī)制：路徑越短，路徑上經(jīng)過的螞蟻越多，路徑上的信息素濃度越大，該路徑被螞蟻選擇的概率也就越大。螞蟻之間通過這種信息交流，實現(xiàn)相互協(xié)作找到通往食物的最短路徑。蟻群算法就是模擬螞蟻覓食行為的優(yōu)化算法。

基于對MOTCP相關(guān)問題的定義，采用APSC和EET作為適應(yīng)度函數(shù)并用蟻群算法實現(xiàn)MOTCP。由于測試用例優(yōu)先排序是一個排序問題，蟻群算法將螞蟻依次訪問所有測試用例形成的訪問序列作為測試用例執(zhí)行序列。通過不斷累積非支配解路徑上的信息素，引導(dǎo)螞蟻參照非支配解的測試用例排列次序逐步趨近于全局最優(yōu)解。與其他應(yīng)用問題不同，任意兩個測試用例i、 j之間存在兩條有向路徑[i→j]、[j→i]分別代表螞蟻兩種測試用例遍歷次序。下面依次介紹面向MOTCP蟻群算法的三個主要步驟：構(gòu)造解、更新最優(yōu)解集和更新信息素。

1）構(gòu)造解。

當(dāng)螞蟻開始搜索時，隨機(jī)選擇一個測試用例作為初始點，從初始點出發(fā)，根據(jù)路徑上的信息素值和優(yōu)化目標(biāo)的影響逐步選取訪問的下一個測試用例，直至所有測試用例均被訪問過一次時螞蟻終止搜索，得到一個測試用例遍歷序列。待所有螞蟻完成搜索，即蟻群算法完成一次迭代過程。式（3）中表示螞蟻k由測試用例i繼續(xù)訪問測試用例j的概率，是路徑[i→j]上的信息素值，是啟發(fā)式信息，d是優(yōu)化目標(biāo)的個數(shù)，在MOTCP問題中，從測試用例i選擇測試用例j的啟發(fā)式信息分別為：η1ij=Coveragej（測試用例j的語句覆蓋率），η2ij=1/Tvectorj（測試用例j執(zhí)行時間的倒數(shù)），Nk是螞蟻k余下未搜索過的測試用例集合，參數(shù)α、 β是控制信息素τij和啟發(fā)信息ηkij的啟發(fā)因子。

pkij=ταij*∏2d=1[ηdij]λdβ∑l∈Nkταil*∏2d=1[ηdil]λdβ，l∈Nk

0，其他（3）

2）更新最優(yōu)解集。

最優(yōu)解集表示螞蟻整個搜索過程中的全局最優(yōu)解集，每完成一次迭代時更新一次最優(yōu)解集：在完成每一次迭代以后，會采取非支配排序得到本次迭代的非支配解集。然后將本次迭代的非支配解集中的解依次全局最優(yōu)解相比較，判斷支配關(guān)系，若能支配最優(yōu)解，則該解替換掉被支配的最優(yōu)解。

3）更新信息素。

隨著時間的推移，路徑上的信息素是不斷更新和揮發(fā)的過程。每一次迭代后，將非支配解的遍歷路徑信息保留下來參與下一次迭代，而其他路徑上留下來的信息素隨著迭代次數(shù)的增加逐漸揮發(fā)，從而引導(dǎo)螞蟻向更好的方向搜索。圖1表示了一個非支配解的信息素更新過程。圖中每一個節(jié)點代表一個測試用例，測試用例之間的距離設(shè)定為相等距離，依次累加測試用例序列[b→a→i→c→f→h→d→e→g]的路徑中兩兩測試用例之間的信息素值Δτkij。螞蟻完成一次迭代后，用1-ρ（0<ρ<1）表示信息素的消逝程度，虛線表示螞蟻在路徑上留下的信息素，非支配解路徑的信息素值根據(jù)式（4）作調(diào)整：

2基于ETS的信息素更新策略

螞蟻之間通過信息素來實現(xiàn)相互交流，協(xié)同工作，不同的信息素更新策略決定了螞蟻間傳遞的信息不同。優(yōu)質(zhì)的信息對螞蟻的搜索目標(biāo)有促進(jìn)搜索作用，無效的信息對螞蟻的搜索可能產(chǎn)生誤導(dǎo)作用。原始的信息素更新策略提高非支配解集覆蓋路徑上的信息素濃度，但路徑上任意兩個測試用例之間的信息素增量是一個常量（式（4）中的Q/L），沒有考慮測試用例之間的關(guān)系。在本文提出的方法中，我們通過ETS分析測試用例語句覆蓋的能力，使用兩個測試用例之間的額外語句覆蓋信息動態(tài)表示兩者之間的關(guān)系，并替代原有的信息素增量。

2.1方法概述

在一個測試用例序列中，ETS是指首次到達(dá)語句全覆蓋的測試用例序列段，其中最后一個測試用例j是ETS達(dá)到全覆蓋的臨界點，其能覆蓋排列在之前測試用例序列未能覆蓋的語句。選取ETS中的測試用例到測試用例j的路徑更新信息素，保留能促進(jìn)適應(yīng)度提升的測試用例，引導(dǎo)其他螞蟻經(jīng)過該測試用例，即：

Δτkij=

Q*ΔCoverageijTvectorj，當(dāng)螞蟻k得到的測試用例序列為非支配解時i、 j∈T′

0，其他 （5）

其中：T′表示ETS包含的測試用例，j為ETS的最后一個測試用例，ΔCoverageij表示測試用例j對測試用例i之間的額外語句覆蓋。

例如，測試用例序列[a→b→e→c→d]中每個測試用例的語句覆蓋情況如表1所示。[a→b→e→c]能達(dá)到最大語句覆蓋，那么該測試用例序列段是一個ETS，排列在其后的測試用例d對適應(yīng)度不產(chǎn)生影響。在ETS中，測試用例c是ETS的最后一個測試用例，也是序列中達(dá)到語句最大覆蓋的臨界點。測試用例c包含了位于它之前的測試用例a、b和e未能覆蓋的測試語句。按圖2中的信息素更新策略依次在路徑[a→c]、[b→c]、[e→c]上增加信息素值，點劃線表示引導(dǎo)螞蟻前進(jìn)的路徑。測試用例間[a→c]、[b→c]、[e→c]的額外語句覆蓋越高，測試用例c的執(zhí)行時間越小，路徑[a→c]、[b→c]、[e→c]上更新的信息素值就越高。在下次迭代中螞蟻朝著信息素濃度高的方向搜索，優(yōu)先選取測試用例c作為下一個測試用例，從而提升適應(yīng)度值。

在MOTCP問題中，基于APSC優(yōu)化目標(biāo)，由式（1）所見所有程序語句第一次被覆蓋的測試用例在執(zhí)行序列中的位置（TS1，TS2，….，TSN）不一定是連續(xù)分布的數(shù)列，從第一個測試用例至到達(dá)最大語句覆蓋的測試用例之間可能包含沒有額外語句覆蓋的測試用例，基于ETS的信息素更新策略能夠引導(dǎo)螞蟻優(yōu)先選取最后到達(dá)語句全覆蓋的測試用例，排除掉

ETS中的對APSC無促進(jìn)作用的測試用例，從而提升了額外覆蓋語句首次被覆蓋時測試用例的執(zhí)行位置將額外覆蓋語句首次被覆蓋時測試用例的執(zhí)行位置提前。

基于MOTCP問題的另一個優(yōu)化目標(biāo)EET也受ETS影響，由式（2）所示其表示ETS中所有測試用例執(zhí)行時間的累加值。隨著算法迭代次數(shù)的增加，ETS長度逐步縮減，EET趨向于減少。并且在信息素計算式（5）中加入測試用例執(zhí)行時間對信息素值的影響（當(dāng)ΔCoverageij相等時，Tvectorj越小，路徑上的信息素值越大），指導(dǎo)螞蟻的搜索方向。

綜上，具體的信息素更新策略分為兩個步驟：首先，采取精英策略確定信息素更新范圍，在每次迭代后只對非支配解集更新信息素值，將一代中較好的解的搜索信息保留下來指導(dǎo)下一次搜索；其次，采用信息素局部更新策略依次更新ETS中測試用例與最后一個測試用例之間路徑的信息素值，在下次迭代中優(yōu)先選取對適應(yīng)度有促進(jìn)作用的測試用例。根據(jù)信息素的更新策略，螞蟻通過感知路徑上信息素濃度選擇搜索方向，搜索的測試用例序列逐步趨近于全局最優(yōu)解。與原始的信息素更新策略相比較，本文提出的新策略主要有兩點提高：1）采用局部更新策略只更新ETS中部分路徑上的信息素，相比更新螞蟻完整的遍歷測試用例序列，減少了信息采集的次數(shù)，提升了計算效率；2）由傳統(tǒng)計算兩點之間的信息素，改變?yōu)樵u價ETS中的測試用例之間的額外語句覆蓋和測試用例執(zhí)行時間多目標(biāo)影響下的信息素值，保證了螞蟻選取的測試用例能促進(jìn)適應(yīng)度提升，是本文的算法能夠大幅度提高收斂速度的關(guān)鍵。

2.2螞蟻構(gòu)造解過程的優(yōu)化

螞蟻逐步遍歷全部測試用例的過程十分耗時。為了節(jié)省螞蟻構(gòu)造解的時間，提升算法效率，設(shè)定了螞蟻停止搜索條件的位置，即在螞蟻搜索過程中設(shè)置終點，當(dāng)螞蟻達(dá)到該終點時結(jié)束本次迭代的搜索。測試用例集中未被訪問的測試用例隨機(jī)排列在終點之后，完成測試用例排序的過程。

螞蟻搜索終點位置的設(shè)置是本節(jié)的研究重點。如圖3所示，從左至右的線段表示測試用例依次排列的執(zhí)行序列位。終點設(shè)置在序列的前端時，大部分測試用例被隨機(jī)排序；終點設(shè)置在序列后端時，螞蟻已遍歷了大部分的測試用例，算法運算時間并沒有得到有效約減；在序列中部的終點位置為適宜區(qū)間。由于適應(yīng)度只由ETS的影響，因此終點設(shè)置在ETS末端是理想的終點位置。但是在螞蟻構(gòu)造解時，當(dāng)次迭代的ETS長度不能提前預(yù)知，為此參照當(dāng)前最優(yōu)解集合計算得到平均ETS長度，并將ETS末端位置作為本次迭代搜索終點。在實驗中發(fā)現(xiàn)，隨著實驗迭代次數(shù)的增加，最優(yōu)解集的平均ETS的長度逐漸縮短，搜索終點的位置在序列中部區(qū)域內(nèi)從右往左逐步移動。

3實驗結(jié)果與分析

為了驗證基于ETS的信息素更新策略是否能改善蟻群算法在解決MOTCP的效率問題，本章針對如下兩個研究問題進(jìn)行實驗分析。

1）在MOTCP問題中，基于ETS的信息素更新策略的蟻

群算法的求解能力和收斂速度是否優(yōu)于未優(yōu)化的蟻群算法。

2）在MOTCP問題中，優(yōu)化后蟻群算法的效率是否優(yōu)于NSGAⅡ。

3.1實驗環(huán)境和對象

實驗選取SIR庫中三個被測程序和一個開源的V8程序。如表2所示，被測程序包含一個小規(guī)模程序Flex（UNIX詞法分析器）和三個較大規(guī)模程序Space（ADL語言解釋器）、Bash（UNIX shell）、V8（開源JavaScript引擎）。在實驗開始階段，需要對每個被測程序從測試用例池中抽取出達(dá)到語句全覆蓋的測試用例集，實驗所采用的測試用例集平均大小如表2所示。實驗在CodeBlocks13.12平臺上使用C語言實現(xiàn)。實驗程序在Linux服務(wù)器環(huán)境下運行，基本配置為64位CentOS 6.4操作系統(tǒng)，Intel Xeon E562 CPU和24GB內(nèi)存。

由于蟻群參數(shù)是另一個對算法性能影響較大的因素，根據(jù)之前的研究方法[16-17]，采用單一變量法預(yù)先設(shè)置MOTCP中蟻群算法的參數(shù)組合。針對兩個研究問題實驗采用相同的測試用例集規(guī)模分別作了兩組對比實驗，實驗相關(guān)參數(shù)設(shè)置如下：

1）分別對4個被測程序隨機(jī)抽取50組語句全覆蓋的測試用例集合；

2）每組測試用例集獨立重復(fù)實驗10次；

3）蟻群算法中參數(shù)組合為α=1，β=5，ρ=0.1，m=32，其中m表示螞蟻種群大?。?/p>

4）將基于ETS的信息素更新方策略和原始的信息素更新策略相比較，兩組實驗的最大迭代次數(shù)為300；

5）將優(yōu)化后的蟻群算法和NSGAⅡ相比較時，優(yōu)化后的蟻群算法在100次迭代時最優(yōu)解集趨于穩(wěn)定狀態(tài)，所以將對比實驗的最大迭代次數(shù)設(shè)置為100。

3.2實驗結(jié)果分析

1）在MOTCP問題中，兩種信息素更新策略對蟻群算法收斂速度及求解能力的對比分析。

本文將實驗最終能達(dá)到穩(wěn)定狀態(tài)的實驗結(jié)果相比較，比較不同信息素更新策略的蟻群算法取得的適應(yīng)度值、迭代次數(shù)等，來判斷兩種信息素更新策略對算法收斂速度和求解能力的影響。實驗規(guī)定程序在連續(xù)10次迭代后APSC和EET的差值均不大于0.005時，則判定運行的程序達(dá)到穩(wěn)定狀態(tài)。其中，50組測試用例集合10次獨立重復(fù)實驗的最優(yōu)解集的平均值作為對比實驗的評價指標(biāo)：平均APSC、平均EET、平均迭代次數(shù)、平均ETS長度以及一次迭代的平均運行時間。平均APSC和平均EET分別為MOTCP問題中兩種適應(yīng)度值的平均值，其表示穩(wěn)定狀態(tài)時獲取的最優(yōu)解質(zhì)量；平均迭代次數(shù)表示程序在多少次迭代后達(dá)到穩(wěn)定狀態(tài)；平均ETS長度表示穩(wěn)定狀態(tài)時最優(yōu)解ETS的平均長度，每次迭代后的長度變化表示算法的收斂速度；一次迭代的平均運行時間表示程序平均每次迭代的時間消耗。具體的實驗數(shù)據(jù)如表3所示。

如表3所示：表中列出了4個被測程序在不同的信息素更新策略中的評價指標(biāo)?；贓TS的信息素更新策略的優(yōu)化算法得到的適應(yīng)度值較原始算法均得到了有效提升，其解能支配原始算法得到的解，說明提出的信息素更新策略使蟻群算法對MOTCP問題的求解能力得到提升。表中還分別比較了兩種信息素更新策略得到的平均迭代次數(shù)、平均ETS長度和一次迭代的平均運行時間。原始的信息素更新策略在程序規(guī)模較小的Flex程序中在30多次迭代后達(dá)到穩(wěn)定狀態(tài)，ETS長度縮短了92%；程序規(guī)模較大的V8程序大概在60次迭代后達(dá)到穩(wěn)定，ETS長度縮短了92%。表明新的方法ETS長度均大幅度減少，適應(yīng)度值提升，但是迭代次數(shù)也隨之增加。說明原始的更新策略會使算法過早地陷入局部最優(yōu)的狀態(tài)，導(dǎo)致ETS的長度還未收斂到全局最優(yōu)便停止了變化。

為了更直觀地表示兩種信息素更新策略的蟻群算法在收斂速度上的差異，本文抽取了bash程序在某一次獨立實驗中前100次迭代內(nèi)的實驗數(shù)據(jù)，兩種信息素更新策略每隔20次迭代的最優(yōu)解集分布如圖4所示，圖中橫坐標(biāo)為EET，縱坐標(biāo)為APSC，位于上方的散點圖是基于ETS信息素更新策略的實驗結(jié)果，另一張是原始的信息素更新策略的實驗結(jié)果。

縱坐標(biāo)表示APSC值，橫坐標(biāo)表示EET值。

選取不同形狀的散點表示每20代最優(yōu)解集的變化情況，可以看出隨著迭代次數(shù)的增加，代表最優(yōu)解的散點集合向圖的左上方移動?；贓TS的信息素更新策略在前60次迭代中算法收斂速度快，在60次迭代以后得到的最優(yōu)解集的分布大部分重疊，收斂速度減緩。相比之下原始的信息素更新策略的收斂速度明顯低于前者，并且在40次迭代之后收斂速度明顯放緩，算法過早陷入局部最優(yōu)。

信息素的更新策略對蟻群算法的性能有至關(guān)重要的影響，在對MOTCP的研究工作中，通過對比實驗發(fā)現(xiàn)，基于ETS信息素更新策略的蟻群算法的收斂速度明顯高于原始的蟻群算法，能有效提升蟻群算法求解MOTCP的能力。

2）在MOTCP問題中，優(yōu)化后的蟻群算法與NSGAⅡ的比較。

為了驗證優(yōu)化后的蟻群算法能較好地解決MOTCP問題，將優(yōu)化后的蟻群算法與NSGAⅡ算法的實驗結(jié)果相比較。其中基準(zhǔn)方法NSGAⅡ是根據(jù)文獻(xiàn)[6]的方法獨立編碼實現(xiàn)，種群大小及迭代次數(shù)等參數(shù)與優(yōu)化的蟻群算法保持一致。圖5是4個被測程序50組測試用例集合10次獨立重復(fù)實驗在100次迭代內(nèi)兩個算法最優(yōu)解的對比結(jié)果。

圖5中越接近左上角的點表示該解能在有限的迭代次數(shù)之內(nèi)達(dá)到高APSC、低EET的測試目標(biāo)。圖中深色散點代表采用基于ETS信息素更新策略的蟻群算法得到的最優(yōu)解集，淺色散點代表NSGAⅡ算法得到的最優(yōu)解集，如圖5所示蟻群算法得到的最優(yōu)解大部分集中分布在NSGAⅡ最優(yōu)解的左上方，并且分布更為集中，說明優(yōu)化后的蟻群算法在有限的迭代次數(shù)內(nèi)有更好的求解能力。相比之下NSGAⅡ的解分布較為分散，表明在有限的迭代次數(shù)內(nèi)解的分布呈未收斂的狀態(tài)，蟻群算法的收斂速度優(yōu)于NSGAⅡ。綜上，優(yōu)化后的蟻群算法收斂速度更快，能夠在較少的迭代次數(shù)內(nèi)得到較優(yōu)的最優(yōu)解集，并且這種優(yōu)勢在大規(guī)模的V8程序中更為明顯。

4結(jié)語

本文提出了一種基于ETS的信息素更新策略，有效收集了螞蟻遍歷時的有效測試用例信息。根據(jù)測試用例之間信息素值的大小逐步訪問測試用例序列，引導(dǎo)螞蟻優(yōu)先選取促進(jìn)適應(yīng)度值提升的測試用例。其次，基于這種信息素更新策略，優(yōu)化了螞蟻構(gòu)造解的過程，重新設(shè)置了螞蟻的搜索終點，約減了螞蟻逐步搜索測試用例的時間消耗，提升了算法效率。優(yōu)化后的蟻群算法使得螞蟻具有較強(qiáng)的發(fā)掘最優(yōu)解的能力，解決了在MOTCP中螞蟻搜索易陷入局部最優(yōu)、搜索耗時的問題。盡管以上研究能較好地解決蟻群算法應(yīng)用于MOTCP時的問題，但蟻群算法還具有很多研究潛力，比如設(shè)置適宜的蟻群算法參數(shù)，動態(tài)自適應(yīng)的參數(shù)調(diào)整或者并行性研究都是有待研究的方向。

參考文獻(xiàn)：

[1]

SHARMA I， KAUR J， SAHNI M. A test case prioritization approach in regression testing [J]. International Journal of Computer Science & Mobile Computing， 2014， 3（7）： 607-614.

[2]

ROTHERMEL G， UNTCH R H， CHU C， et al. Prioritizing test cases for regression testing [J]. IEEE Transactions on Software Engineering， 2001， 27（10）： 929-948.

[3]

LI Z， HARMAN M， HIERONS R M. Search algorithms for regression test case prioritization [J]. IEEE Transaction on Software Engineering， 2007， 33（4）： 225-237.

[4]

陳翔，陳繼紅，鞠小林，等.回歸測試中的測試用例優(yōu)先排序技術(shù)述評[J].軟件學(xué)報，2013，24（8）：1695-1712.（CHEN X， CHEN J H， JU X L， et al. Survey of test case prioritization techniques for regression testing [J]. Journal of Software， 2013， 24（8）： 1695-1712.）

[5]

EPITROPAKIS M G， YOO S， HARMAN M， et al. Empirical evaluation of Pareto efficient multiobjective regression test case prioritisation [C]// Proceedings of the 2015 International Symposium on Software Testing and Analysis. New York： ACM， 2015： 234-245.

[6]

DEB K， AGRAWAL S， PRATAP A， et al. A fast elitist nondominated sorting genetic algorithm for multiobjective optimization： NSGAⅡ [C]// Proceedings of the 6th International Conference on Parallel Problem Solving from Nature. Berlin： Springer， 2000： 849-858.

[7]

YOO S， HARMAN M. Using hybrid algorithm for Pareto efficient multiobjective test suite minimisation [J]. Journal of Systems and Software， 2010， 83（4）： 689-701.

[8]

SINGH Y， KAUR A， SURI B. Test case prioritization using ant colony optimization [J]. ACM SIGSOFT Software Engineering Notes， 2010， 35（4）： 1-7.

[9]

DORIGO M， MANIEZZO V， COLORNI A. The ant system： optimization by a colony of cooperative Agents [J]. IEEE Transactions on Systems， Man， and Cybernetics， Part B： Cybernetics， 1996， 26（1）： 1-13.

[10]

DORIGO M， BIRATTARI M， STUTZLE T. Ant colony optimization [J]. IEEE Computational Intelligence Magazine， 2006， 1（4）： 28-39.

[11]

顧聰慧，李征，趙瑞蓮.基于 ACO 的測試用例預(yù)優(yōu)化及參數(shù)影響分析[J].計算機(jī)科學(xué)與探索，2014，8（12）：1463-1473.（GU C H， LI Z， ZHAO R L. ACO based test case prioritization and impact analysis of parameters [J]. Journal of Frontiers of Computer Science and Technology， 2014， 8（12）： 1463-1473.）

[12]

朱慶保，楊志軍.基于變異和動態(tài)信息素更新的蟻群優(yōu)化算法[J].軟件學(xué)報，2004，15（2）：185-192.（ZHU Q B， ZHANG Z J. An ant colony optimization algorithm based on mutation and dynamic pheromone updating [J]. Journal of Software， 2004， 15（2）：185-192.）

[13]

STUTZLE T， HOOS H. MAXMIN ant system and local search for the traveling salesman problem [C]// Proceedings of the 1997 IEEE International Conference on Evolutionary Computation. Piscataway， NJ： IEEE， 1997： 309-314.

[14]

DORIGO M， GAMBARDELLA L M. Ant colony system： a cooperative learning approach to the traveling salesman problem [J]. IEEE Transactions on Evolutionary Computation， 1997， 1（1）： 53-66.

[15]

YUAN F， BIAN Y， LI Z， et al. Epistatic genetic algorithm for test case prioritization [M]// BARROS M， LABICHE Y. SearchBased Software Engineering， LNCS 9275. Berlin： Springer， 2015： 109-124.

[16]

PELLEGRINI P， STTZLE T， BIRATTARI M. A critical analysis of parameter adaptation in ant colony optimization [J]. Swarm Intelligence， 2012， 6（1）： 23-48.

[17]

STTZLE T， LPEZIBEZ M， PELLEGRINI P， et al. Parameter adaptation in ant colony optimization [M]// HAMADI Y， MONFROY E， SAUBION F. Autonomous Search. Berlin： Springer， 2012： 191-215.