面向多目标测试用例优先排序的蚁群算法信息素更新策略

邢行　尚颖　赵瑞莲　李征

摘要：

针对蚁群算法在求解多目标测试用例优先排序（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.