A VNS-based Hyper-heuristic with Adaptive Computational Budget of Local Search

Hyper-heuristics solve problems by manipulating low-level domain-specific heuristics. The aim is to raise the level of generality of the algorithm to solve problems in different domains. In this paper we propose a hyper-heuristic based on Variable Neighborhood Search (VNS), which consists of two main steps: shaking and local search. Shaking disturbs solutions, and then local search seeks for the local optima. In our algorithm, we propose a mechanism to adjust the computational budget of local search periodically based on the search status. We also use a dynamically-sized population to store good solutions during the search process. Performance of the proposed algorithm is compared with four benchmark algorithms by four kinds of problems, Max-SAT, bin packing, flow shop scheduling, and personnel scheduling. Our algorithm finds the best solutions for around 90% of the tested instances.