Selection Strategies Of Hyper-heuristic For Multi-objective Test Case Prioritization

The test case prioritization technique aims to find the optimal test case execution sequence for the tested programs.With the increasing demand for software regression testing technology,multi-objective test case prioritization technology has been widely studied in recent years.Many multi-objective evolutionary algorithms are used to solve the problem of MOTCP.In different test scenarios,the results of different algorithms are also different.There is no a general multi-objective evolutionary algor:hmhaving the best performance in various test scenarios.To solve the algorithm scheduling problem in different test scenarios,a general search-based hyper-heuristic framework which is dynamically adaptiveis applied to solve the multi-objective test case prioritization problem,which is called HH-MOTCP framework.This framework consists of two parts:the low level and the hyperlevel.The low level encapsulates multiple multi-objective evolutionary algorithms which are called low level heuristics,while the hyperlevel has a selection strategy to adaptively select the low-level heuristics during iteration.Although theHH-MOTCP framework shows relatively good effectiveness and efficiency,there is still a lot of space for improvingthe selection strategy in the hyper level.Besides,an appropriatehyper levelselection strategywill help to obtain solutions that better meet the test optimization objectives,andfurther improve the performance of the HH-MOTCP framework.This paper studies the HH-MOTCP framework from two aspects:one is based on the idea of "exploitation" and "exploration",the other is based on the method of reinforcement learning.Through the research of the selection strategies in the hyper level of HH-MOTCP framework,this paper:(1)improves the evaluation metricbased on the instant and historical execution information of low-level heuristics and study various selection methods,then combines different evaluation metrics with selection methods to obtain 18 selection strategies based on "exploitation" and "exploration",(2)among the 18 selection strategies based on "exploitation" and "exploration",the optimal one with good performance for all test objects is obtained,which outperforms the existing selection strategy and improves the performance of HH-MOTCP framework,(3)tworeinforcement learning methods based on learning automata and action-value are used in the hyper level to dynamically select low level heuristics.The reward and probability update measures in reinforcement learning are defined according to the characteristics ofHH-MOTCP framework.The experimental result shows that theaction-valuemethod can obtain solutions with better quality and cost less overhead than another method.Besides,the quality of solutions acquired by this method is statistically equal with the optimal selection strategy based on "exploitation" and "exploration",and the action-value method can further improve the efficiency of HH-MOTCP framework for the test objects with large test suites.