A Hyper-heuristic Using GRASP With Path-Relinking

The goal of hyper-heuristics is to design heuristics to choose heuristics for solving complex problems. The primary motivation behind the hyper-heuristics is to generalize the solving ability of the heuristics. As one kind of heuristics, most of hyper-heuristics draw on the experiments from the existing meta-heuristics, e.g., a simulated annealing based hyper-heuristic and a genetic algorithm based hyper-heuristic. However, the kinds of hyper-heuristics are much fewer than those of meta-heuristics. The insufficiency of hyper-heuristics has limited the development of hyper-heuristics. In this paper, we propose a Hyper-heuristic using GRASP with Path-Relinking (HyGrasPr). HyGrasPr generates heuristic sequences to produce solutions within an iterative procedure. The procedure of HyGrasPr consists of three phases, namely the construction phase, the local search phase, and the Path-Relinking phase. The solution generated by HyGrasPr is an LLH sequence, which can be applied to the problem instance in order to obtain the final solution to the problem. The LLH sequence is generated by an iterative procedure of GRASP with the Path-Relinking phase. In HyGrasPr, we first build an LLH sequence with the fixed length in GRASP construction phase. Then, we search the neighborhood of the LLH sequence for obtaining the local optimal LLH sequence. Next, we use the current best LLH sequence and the local optimal LLH sequence to conduct the Path-Relinking phase. To show the performance of our HyGrasPr, we take the nurse rostering problem and Bin-Packing as the case study. We employ an existing simulated annealing based hyper-heuristic as a baseline. The experimental results indicate that HyGrasPr can achieve better solutions than SAHH within the same running time and the Path-Relinking phase is effective for the framework of HyGrasPr. This work can show the generalization ability of our HyGrasPr.