A generation perturbative hyper-heuristic for combinatorial optimization problems

Abstract

Perturbative heuristics or move operators are problem dependent operators commonly used by search techniques to solve computationally hard problems such as combinatorial optimization problems. These operators are generally derived manually by problem domain experts but this process is extremely challenging and time consuming. Hence, some initiatives aimed at automating the derivation process using search methodologies such as hyper-heuristics have been proposed in recent years. However, most of the proposed hyper-heuristic approaches generate new perturbative heuristics by recombining already existing and human-derived perturbative heuristics or components with various move acceptance criteria instead of generating the heuristics from scratch. As a result, these approaches cannot be easily applied to other problem domains where the human-derived heuristics are not available. In addition, the few hyper-heuristic approaches that have been proposed to generate perturbative heuristics from scratch are either designed for a single problem domain or applicable only to specific types of problems such as those that can be represented as graphs. The research presented in this dissertation addresses these issues by proposing a novel approach that can be used to automatically generate perturbative heuristics for any combinatorial optimization problem. In the proposed approach, perturbative heuristics are defined in terms of a set of basic operations (e.g. move and swap) and components of the solution (e.g. exam, period and room for the examination timetabling problem). Grammatical evolution, a well-known Evolutionary Algorithm, is used to combine the basic operations and components of the solution into perturbative heuristics. The generality of the proposed approach is tested by applying it to benchmark sets from three different problem domains, namely examination timetabling, vehicle routing and Boolean satisfiability. In addition, the performance of the perturbative heuristics generated by the proposed approach on the benchmark sets is compared to that of the commonly-used human-derived perturbative heuristics as well as the perturbative heuristics generated by other hyper-heuristic approaches in the literature. The experimental results show that the perturbative heuristics evolved by the proposed approach, specifically the grammatical evolution extended approach, outperformed the human-derived perturbative heuristics on all benchmark sets from the three problem domains. When compared to existing hyper-heuristic approaches, the proposed approach obtained solutions that were superior to those obtained by most hyper-heuristic approaches on the examination timetabling problem and only slightly inferior to those obtained by the best performing hyper-heuristic approaches on the vehicle routing and Boolean satisfiability problems. This performance of the proposed approach can be attributed to the fact that the generated perturbative heuristics were applied as is with no optimization as is commonly done with most hyper-heuristic approaches. Overall, the experimental results demonstrated success in developing an approach that can be used to automatically generate perturbative heuristics from scratch. Future work will consider incorporating optimization techniques during problem solving as well as performing a fitness landscape analysis in order to further improve the quality of solutions and have a better understanding of the proposed approach.