The Research On Construction Of The Hyper-heuristic Library For Test Case Prioritization

The hyper-heuristic algorithm is a heuristic search method that provides a high-level strategy to solve a large scale of search problems by creatively selecting,combining,and generating some heuristic algorithms.The framework of hyper-heuristic algorithm consists of high-level strategy layer and low-level algorithm layer.The high-level strategy layer provides methods to manage and manipulate different algorithms,while the low-level algorithm library is usually composed of different algorithms for specific problems.Scholars have studied the high-level strategy layer very deeply,but for the low-level algorithm layer,a fixed number of the same type algorithm is usually used to build algorithm library.There is a lack of in-depth research on the number of algorithms or whether different type of algorithms can be allowed to build algorithm library together.As an important part of the hyper-heuristic algorithm,the construction method of the low-level algorithm library has an important influence on the overall performance of the hyper-heuristic algorithm.On the one hand,the increase in the number of algorithms in the algorithm library enhances the ability of the hyper-heuristic algorithm to solve different problems,at the same time,it also brings pressure to the scheduling of the high-level layer and the performance of the hyper-heuristic algorithm is affected.On the other hand,the same type of algorithm has limitations in solving specific problems.For example,the global optimization algorithm can find the global approximate optimal solution,but its search efficiency is slow because it is oriented to the whole search space.It is an urgent problem to be solved whether the algorithm library can be constructed by fusing different type of algorithms to overcome the limitation of single type algorithm and improve the performance of hyper-heuristic algorithm.Based on the above two parts,this paper has fully studied the construction method of the low-level algorithm library.We study the complexity of algorithm library and the hybrid pattern of algorithms in algorithm library.In the study of the complexity of algorithm library,HH-NSGA,HH-TAEA,HH-SPEA and HH-ALL are constructed to explore the influence of different complexity algorithm libraries on the overall performance of the hyper-heuristic algorithm.In the study of hybrid pattern of algorithm library,the global optimization algorithm combined with local optimization algorithm is used to accelerate the overall convergence performance of the hyper-heuristic algorithm.In order to verify the experimental results of different construction methods of algorithm library,this paper adopts nine open-source tested programs to solve the multi-objective test case prioritization problem and conduct experiments on four research problems under two research contents.The experimental results show that:(1)With the increase of the number and types of algorithms in the low-level algorithm library of the hyper-heuristic algorithm,the complexity of the algorithm library increases,but the overall performance of the hyper-heuristic algorithm does not increase.(2)The overall convergence of the hyper-heuristic algorithm is effectively enhanced by using the algorithm library combined with the global optimization algorithm and the local optimization algorithm to construct the algorithm library.(3)The validity of the experimental results was further verified under a variety of programs of different scales and types.