求解测试用例自动生成问题的多因子回溯搜索优化算法

Multifactorial backtracking search optimization algorithm for solving automated test case generation problem

路径覆盖测试用例自动生成(ATCG-PC)问题是自动化软件测试领域的热点。ATCG-PC问题中群智能进化算法常用的适应度函数之间具有高度的相似性,然而现有的解决ATCG-PC问题的群智能进化算法尚未考虑这一相似性特征。受相似性特征启发,将两个相似的适应度函数看作两个任务,从而将ATCG-PC问题转化为多任务ATCGPC问题,并提出了一种新的解决多任务ATCG-PC问题的群智能进化算法,即多因子回溯搜索优化算法(MFBSA)。所提算法通过多因子选择Ⅰ的记忆种群功能提高全局搜索能力,并通过选型记忆交配使得相似任务之间能够通过知识转移提高彼此的优化效率。在6个雾计算测试程序和6个自然语言处理测试程序上对所提算法性能进行了评价。与回溯搜索优化算法(BSA)、免疫遗传算法(IGA)、收敛速度控制器粒子群优化(PSO-CSC)算法、自适应粒子群优化(APSO)算法和超立方体差分进化(DE-H)算法相比,MFBSA覆盖12个测试程序上的路径所使用的测试用例总数分别减少了64.46%、66.64%、67.99%、74.15%和61.97%。实验结果表明,所提算法能够有效降低测试成本。

Automated Test Case Generation for Path Coverage(ATCG-PC)problem is a hot topic in the field of automated software testing.The fitness functions commonly used by swarm intelligence evolutionary algorithms in ATCG-PC problem are highly similar with each other,but the existing swarm intelligence evolutionary algorithms for solving ATCG-PC problem do not consider this similarity feature yet.Inspired by the similarity feature,the two similar fitness functions were treated as two tasks,so that ATCG-PC problem was transformed into a multi-task ATCG-PC problem,and a new swarm intelligence evolutionary algorithm called Multifactorial Backtracking Search optimization Algorithm(MFBSA)was proposed to solve multi-task ATCG-PC problem.In the proposed algorithm,the memory population function of multifactorial selectionⅠwas used to improve the global search ability,and the similar tasks were able to improve each other’s optimization efficiency through knowledge transfer by assortative memory mating.The performance of MFBSA was evaluated on six fog computing test programs and six natural language processing test programs.Compared with Backtracking Search optimization Algorithm(BSA),Immune Genetic Algorithm(IGA),Particle Swarm Optimization with Convergence Speed Controller(PSO-CSC)algorithm,Adaptive Particle Swarm Optimization(APSO)algorithm and Differential Evolution with Hypercubebased learning strategies(DE-H)algorithm,MFBSA has the total test cases used to cover the paths on 12 test programs reduced by 64.46%,66.64%,67.99%,74.15%,and 61.97%,respectively.Experimental results show that the proposed algorithm can effectively reduce testing cost.