Abstract: Test case prioritization is an advanced software regression testing technique. Compared to the techniques of regression test selection and test suite minimization, it is more flexible to adapt the changes occurred in regression testing iterations. The multi-objective test case prioritization has become a hot spot recently, and for selected optimal objects, algorithm is the key for the achievement of multi-objective optimization. This paper proposes an ant colony optimization (ACO) based multi-objective test case prioritization technique, with two optimal objects, average percentage of statement coverage (APSC) and effective execution time (EET), and improves the evaluation formula of multi-objective sets. This paper also empirically studies the impact of parameters used in ACO, especially pheromone evaporation factor ρ,heuristic factors α,β and ant colony size m. The programs under test are from software-artifact infrastructure repository (SIR) and an open source program of V8 that is JavaScript engine published by Google. The results show that when α=1,4≤β≤6,ρ=0.1,m=32, the algorithm can obtain optimal sets for the small programs, while m becomes larger with the increase of the size of programs that is demonstrated by the results for flex and V8.

Key words: regression testing, test case prioritization, multi-objective optimization, ant colony optimization, parameter analysis

摘要： 测试用例预优化是一种先进的软件回归测试用例集优化技术。相比测试用例选择和测试用例集约简技术，它具有更好的灵活性，更容易适应实际软件回归测试过程中的迭代与变化。基于多目标的测试用例预优化技术是当前研究的热点，针对选定的多个优化目标，算法是多目标测试用例集优化的关键。提出了一种基于蚁群优化算法（ant colony optimization，ACO）的多目标测试用例预优化方法，针对平均语句覆盖率和有效执行时间两个优化目标，实现了测试用例集的预优化，并针对多目标解集优劣评价方法进行了改进。同时对蚁群优化算法中的信息素挥发因子ρ、启发因子α和β、蚁群规模m等相关参数对多目标测试用例预优化结果的影响进行了实验分析。实验中使用的被测程序既包括广泛使用的软件测试样本库SIR（software-artifact infrastructure repository）中的程序，也包括Google发布的大规模开源程序JavaScript引擎V8。实验结果表明，当参数α=1,4≤β≤6,ρ=0.1时，针对小规模程序，蚁群规模[m=32]时，算法求得较优解；针对较大规模程序flex和V8，则需要适当增大蚁群的规模以获得较优解集。

关键词: 回归测试, 测试用例预优化, 多目标优化, 蚁群优化算法, 参数分析