Research On Evaluation Strategy Of Hyper-heuristic Framework For Test Case Prioritization

Test case prioritization aims to find the optimal execution sequences of test cases to achieve testing objectives as soon as possible,which is considered as the most crucial test suite optimization technique.A large number of search based algorithms have been applied to optimize test case execution order.However,there is no general applicable algorithm for different testing scenarios.Hyper-heuristic algorithm is applied to test case prioritization,which can select the appropriate algorithm execution sequence dynamically for different scenarios with strong versatility.There are two levels in the hyper-heuristic framework.The low level includes a set of multi-objective optimization algorithms.In the high level,the learning agent strategy can evaluate and select the appropriate algorithms dynamically for different testing scenarios.The learning agent uses Hierarchical Distribution(HD)strategy to evaluate the execution results of the current algorithm and then selects the appropriate algorithm for the next iteration based on the current and historical evaluation results.The HD strategy evaluates the execution results of the low-level algorithms based on the dominance relationship between the individuals from the present and last generations,but cannot distinguish the individuals in the same non-dominated solution set.In practice,the non-dominated individuals can be further distinguished according to various metrics to evaluate the execution results of the low-level algorithms more accurately and select the optimal algorithm execution sequence.In our study,the convergence ability of the individuals is further considered in the design of the evaluation strategy,in which Pareto Dominance and Convergence Information are adopted to assess the convergence ability of the individuals in the execution results of the low-level algorithms.Three convergence based evaluation strategies are proposed,which are ESPD,ESPC-1 and ESPC-2,respectively.In order to verify the effectiveness of the proposed evaluation strategies,experiments are conducted on five Java programs and three C++programs to compare the effectiveness and efficiency of different evaluation strategies.The results indicate that:(1)The hyper-heuristic algorithms with the convergence based evaluation strategies can obtain higher quality test case execution sequences;(2)The convergence based evaluation strategies can reduce the time cost mostly.For few programs under test,the hyper-heuristic algorithms with the proposed evaluation strategies have longer execution time,but which does not affect the test efficiency;(3)Among the three convergence based evaluation strategies,the ESPC-2 strategy performs best overall followed by the ESPC-1 and ESPD strategies.