面向多目標測試用例優先排序的蟻群算法信息素更新策略

邢行　尚穎　趙瑞蓮　李征

摘要：

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

關鍵詞：

蟻群算法； 信息素更新； 多目標的測試用例優先排序； 回歸測試； 上位基因段

中圖分類號：

TP311.5

文獻標志碼：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.

英文關鍵詞Key words：

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

0引言

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

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

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

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

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

1相關研究

1.1MOTCP相關問題描述

MOTCP是在測試用例集中尋找同時滿足多個優化目標的最優測試用例執行序列的過程。通常使用非支配排序技術對測試用例進行多目標排序，其中對于兩個優化目標的非支配排序規則定義如下：

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

1）當f1 （T′） ≥ f1 （T ″）且f2 （T′） ≥ f2（T ″）或者f1 （T′） ≤ f1 （T ″）且f2 （T′） ≤ f2 （T ″）時，稱T′對于兩個優化目標能支配T ″或者被T ″支配。

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

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

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

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

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

1.2面向MOTCP的蟻群算法

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

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

1）構造解。

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

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

0，其他（3）

2）更新最優解集。

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

3）更新信息素。

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

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

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

2.1方法概述

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

Δτkij=

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

0，其他 （5）

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

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

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

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

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

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

2.2螞蟻構造解過程的優化

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

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

3實驗結果與分析

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

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

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

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

3.1實驗環境和對象

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

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

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

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

3）蟻群算法中參數組合為α=1，β=5，ρ=0.1，m=32，其中m表示螞蟻種群大小；

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

5）將優化后的蟻群算法和NSGAⅡ相比較時，優化后的蟻群算法在100次迭代時最優解集趨于穩定狀態，所以將對比實驗的最大迭代次數設置為100。

3.2實驗結果分析

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

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

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

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

縱坐標表示APSC值，橫坐標表示EET值。

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

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

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

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

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

4結語

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

參考文獻：

[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]

陳翔，陳繼紅，鞠小林，等.回歸測試中的測試用例優先排序技術述評[J].軟件學報，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 的測試用例預優化及參數影響分析[J].計算機科學與探索，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]

朱慶保，楊志軍.基于變異和動態信息素更新的蟻群優化算法[J].軟件學報，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.