邢行　尚穎　趙瑞蓮　李征

摘要：

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

關(guān)鍵詞：

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

中圖分類號(hào)：

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引言

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

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

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

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

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

1相關(guān)研究

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

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

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

1）當(dāng)f1 （T′） ≥ f1 （T ″）且f2 （T′） ≥ f2（T ″）或者f1 （T′） ≤ f1 （T ″）且f2 （T′） ≤ f2 （T ″）時(shí)，稱T′對(duì)于兩個(gè)優(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 ″）時(shí)，稱T′和T ″互不支配。

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

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

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

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

1.2面向MOTCP的蟻群算法

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

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

1）構(gòu)造解。

當(dāng)螞蟻開始搜索時(shí)，隨機(jī)選擇一個(gè)測(cè)試用例作為初始點(diǎn)，從初始點(diǎn)出發(fā)，根據(jù)路徑上的信息素值和優(yōu)化目標(biāo)的影響逐步選取訪問的下一個(gè)測(cè)試用例，直至所有測(cè)試用例均被訪問過一次時(shí)螞蟻終止搜索，得到一個(gè)測(cè)試用例遍歷序列。待所有螞蟻完成搜索，即蟻群算法完成一次迭代過程。式（3）中表示螞蟻k由測(cè)試用例i繼續(xù)訪問測(cè)試用例j的概率，是路徑[i→j]上的信息素值，是啟發(fā)式信息，d是優(yōu)化目標(biāo)的個(gè)數(shù)，在MOTCP問題中，從測(cè)試用例i選擇測(cè)試用例j的啟發(fā)式信息分別為：η1ij=Coveragej（測(cè)試用例j的語句覆蓋率），η2ij=1/Tvectorj（測(cè)試用例j執(zhí)行時(shí)間的倒數(shù)），Nk是螞蟻k余下未搜索過的測(cè)試用例集合，參數(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)解集表示螞蟻整個(gè)搜索過程中的全局最優(yōu)解集，每完成一次迭代時(shí)更新一次最優(yōu)解集：在完成每一次迭代以后，會(huì)采取非支配排序得到本次迭代的非支配解集。然后將本次迭代的非支配解集中的解依次全局最優(yōu)解相比較，判斷支配關(guān)系，若能支配最優(yōu)解，則該解替換掉被支配的最優(yōu)解。

3）更新信息素。

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

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

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

2.1方法概述

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

Δτkij=

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

0，其他 （5）

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

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

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

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

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

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

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

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

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

3實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

3.1實(shí)驗(yàn)環(huán)境和對(duì)象

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

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

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

2）每組測(cè)試用例集獨(dú)立重復(fù)實(shí)驗(yàn)10次；

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

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

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

3.2實(shí)驗(yàn)結(jié)果分析

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

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

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

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

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

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

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

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

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

圖5中越接近左上角的點(diǎn)表示該解能在有限的迭代次數(shù)之內(nèi)達(dá)到高APSC、低EET的測(cè)試目標(biāo)。圖中深色散點(diǎn)代表采用基于ETS信息素更新策略的蟻群算法得到的最優(yōu)解集，淺色散點(diǎn)代表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)勢(shì)在大規(guī)模的V8程序中更為明顯。

4結(jié)語

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

陳翔，陳繼紅，鞠小林，等.回歸測(cè)試中的測(cè)試用例優(yōu)先排序技術(shù)述評(píng)[J].軟件學(xué)報(bào)，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 的測(cè)試用例預(yù)優(yōu)化及參數(shù)影響分析[J].計(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]

朱慶保，楊志軍.基于變異和動(dòng)態(tài)信息素更新的蟻群優(yōu)化算法[J].軟件學(xué)報(bào)，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.