基于多目标协同进化的测试用例优先排序

摘要/Abstract

摘要： 测试用例优先排序是一种有效的降低回归测试开销的技术,通过对测试用例按照其重要程度排序后可获得更高的测试效率。针对传统多目标遗传算法在测试用例优化排序中存在的收敛较慢、易陷入局部最优、缺乏对不同测试准则的综合权衡等缺点,提出一种基于竞争模式的多目标协同进化算法。该方法采用平均代码覆盖率以及平均变异杀死率作为多个约束目标的测试准则来进行适应度度量,提高算法的错误检测率；使用个体绝对适应度与相对适应度对个体生存能力进行评价,衡量个体优秀程度,利用竞争性的协同进化思想加快算法收敛速度;通过剔除“老年”个体控制个体生存周期来避免陷入局部最优问题。同时,在影响算法执行效率的因素方面也进行了一系列的实验,结果表明该算法能够加快收敛速度,加强了局部搜索能力,相对于传统的优化算法来说具有更好的搜索效率和更高的错误检测率,从而验证了算法的有效性和可行性,证明了该算法具有一定的现实意义。

关键词: 协同进化,测试用例优化排序,多目标

Abstract: Test case prioritization is an effective method to significantly reduce costs of regression test.According to some certain aim of test purpose,the main idea of test case prioritization is to rearrange the permutation of the test suite in order to execute the test case with higher priority preferentially.Aiming at the defect of single object genetic algorithm in test case prioritization,such as slow convergence speed,easy to be trapped in local optimum and lacking of the trade-off between multiple testing criteria,a new competitive co-evolutionary approach was adopted to resolve these problems.In this new approach,multi metrics of fitness are used,including the absolute fitness which evaluates the survival ability of an individual and the relative fitness which estimates the number of defeated opponents of each individual.The outstanding individuals who defeat more opponents can join the elite set for further evolution.By eliminating “old” individuals,this approach can control the individual’s survival time to avoid the local optimum.To improve the efficiency of error detection,we introduced the average percentage of mutation kill rate as a new multi-objective optimization criterion.Comparing to the classical search algorithm,the co-evolutionary algorithm can improve the search efficiency and local search ability,and experiment verified the validity of the new approach.

Key words: Co-evolution,Test case prioritization,Multi-objective

石宇楠,李征,龚沛. 基于多目标协同进化的测试用例优先排序[J]. 计算机科学, 2015, 42(12): 124-129. https://doi.org/

SHI Yu-nan, LI Zheng and GONG Pei. Multi-objective Coevolutionary Test Case Prioritization[J]. Computer Science, 2015, 42(12): 124-129. https://doi.org/

参考文献

[1] Li Z,Harman M,Hierons R M.Search algorithms for regression test case prioritization [J].IEEE Transactions on Software Engineering,2007,33(4):225-237
[2] Zhang L,Hou S S,Guo C.Time-aware test-case prioritizationusing integer linear programming[C]∥Proceedings of the Eighteenth International Symposium on Software Testing and Ana-lysis.ACM,2009:213-224
[3] Durillo J J,Zhang Y,Alba E,et al.A study of the bi-objective next release problem [J].Empirical Software Engineering,2011,16(1):29-60
[4] Srinivas M,Patnaik L M.Genetic algorithms:A survey [J].Computer,1994,27(6):17-26
[5] AlRashidi M R,El-Hawary M E.A survey of particle swarm optimization applications in electric power systems [J].IEEE Transactions on Evolutionary Computation,2009,13(4):913-918
[6] Suman B,Kumar P.A survey of simulated annealing as a tool for single and multi-objective optimization [J].Journal of the Operational Research Society,2006,57(10):1143-1160
[7] Zhou A,Qu B Y,Li H,et al.Multi-objective evolutionary algorithms:A survey of the state of the art [J].Swarm and Evolutionary Computation,2011,1(1):32-49
[8] Horn J,Nafpliotis N.A niched Pareto genetic algorithm formulti-objective optimization[C]∥Proceedings of the First IEEE Conference on Evolutionary Computation,1994.IEEE World Congress on Computational Intelligence,IEEE,1994:82-87
[9] Deb K,Agrawal S,Pratap A,et al.A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization:NSGA-II [M]∥Parallel Problem Solving from Nature PPSN VI.2000:849-858
[10] Rothermel G,Untch R H,Chu C.Prioritizing test cases for regression testing[J].IEEE Transactions on Software Enginee-ring,2001,27(10):929-948
[11] Jeffrey D,Gupta R.Test case prioritization using relevant slices[C]∥30th Annual International.Computer Software and Applications Conference,2006(COMPSAC’06).IEEE,2006:411-420
[12] Delamaro M E,Maldonado J C.Proteum-A Tool for the Assessment of Test Adequacy for C Programs User’s guide[C]∥Proceedings of the Conference on Performability in Computing Systems.1996:79-95
[13] de Jong E D,Stanley K O,Wiegand R P.Introductory tutorial on coevolution[C]∥Proceedings of the 2007 GECCO Conference Companion on Genetic and Evolutionary Computation.ACM,2007:3133-3157
[14] Rosin C D,Belew R K.New methods for competitive co-evolution [J].Evolutionary Computation,1997,5(1):1-29
[15] Tan K C,Yang Y J,Goh C K.A distributed cooperative co-evolutionary algorithm for multi-objective optimization [J].IEEE Transactions on Evolutionary Computation,2006,10(5):527-549
[16] Konak A,Coit D W.Multi-objective optimization using genetic algorithms:A tutorial [J].Reliability Engineering & System Safety,2006,91(9):992-1007
[17] Shang R,Wang Y,Wang J,et al.A multi-population cooperative co-evolutionary algorithm for multi-objective capacitated arc routing problem[J].Information Sciences,2014,277:609-642
[18] Nguyen S,Zhang M,Johnston M.Automatic design of scheduling policies for dynamic multi-objective JSS via coevolution genetic programming[J].IEEE Transactions on Evolutionary Computation,2014,8(2):193
[19] 李碧,林土胜.基于竞争协同进化的改进遗传算法[J].深圳大学学报(理工版),2009,26(1):24-29 Li Bi,Lin Tu-sheng.Modified genetic algorithm based on competitive coevolution[J].Journal of Shenzhen University(Science &Engineering),2009,6(1):24-29
[20] Hillis W D.Co-evolving parasites improve simulated evolution as an optimization procedure [J].Physica D:Nonlinear Phenomena,1990,42(1):228-234

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed