Configuring the Perturbation Operations of an Iterated Local Search Algorithm for Cross-domain Search: A Probabilistic Learning Approach

Hyper-heuristics are general-purpose heuristic search methodologies for solving combinatorial optimization problems (COPs). Research findings have revealed that hyper-heuristics still suffer generalization issues as different strategies vary in performance from an instance of a COP to another. In this paper, an approach based on Iterated Local Search (ILS) is proposed to raise the level of generality of hyper-heuristics on the problem domains of the HyFlex framework. The proposed approach utilizes a probabilistic learning technique to automatically configure the behavior of the ILS algorithm during the perturbation stage of the optimization process. In the proposed method, the mutation and ruin-recreate heuristics are treated as distinct entities and the learning layer automatically determines the level of utilization of these heuristic categories depending on the problem domain being solved. The concept of double shaking is also presented where a solution can be perturbed twice before the intensification phase. Experimental results reveal the level of generality achieved by the proposed method as it recorded a minimum formula one score of 30.0 on each tested problem domain. Direct comparison with a state-of-the-art ILS-based approach also establishes the significance of the learning layer added to the perturbation stage of the ILS metaheuristic. Finally, analysis of the perturbation behavior of the hyper-heuristic leads to an interesting conclusion concerning the type of low-level heuristics that are highly beneficial and non-beneficial to a given problem domain.