Search and selection methods for hyper-heuristics.

Abstract

Hyper-heuristics (HHs) search from a search space of heuristics for an optimal heuristic that can be mapped onto a problem to generate good solutions. One of the heuristic selection methods used by hyper-heuristics is a choice function (CF) which assigns scores to heuristics according to their performance. An investigation is conducted on a choice function for single-point selective hyper-heuristics. The drawbacks of the existing choice function are: discarding heuristics due to poor performance on a problem when they could exhibit good performance on another problem and premature convergence in the heuristic search space. In order to address the drawbacks of a choice function, a new selection method called an efficient choice function (ECF) is introduced, based on a three-pronged improvement approach. Firstly, a new element is introduced, which collects previously poor-performing heuris- tics. The best heuristic of the poorly performing heuristics is obtained and compared with the best heuristic from the general pool of heuristics. Secondly, the pairwise comparison of the best heuristics from both the poorly performing heuristics and the general pool of heuristics is applied at every point in the iteration to maintain competition through- out the search process and generate high-quality outcomes. Thirdly, another element is introduced that randomly divides heuristics into different groups, ranks the collective performance of each group and makes performance comparisons between disparate groups of heuristics. The proposed heuristic selection method is tested on several well-known combinatorial optimization problems which include, the vehicle routing problem, the bin packing problem, the permutation ow shop problem, the personnel scheduling problem and the patient transportation problem. Results show a better performance of an efficient choice function than the existing methods. The second contribution of this thesis is to enhance searching for optima in dynamic search spaces. An investigation of dynamic selection hyper-heuristics is performed and a new non-stationary covariance function is introduced. The Gaussian process regression is used as a predictive measure for moving optima in dynamic search environments and the proposed method is applied to the dynamic traveling salesman problem, which yields better performance than the existing approach. The third contribution is a spy search method (SSM) for a memetic algorithm (MA) in dynamic environments. Given that the proposed efficient choice function for hyper- heuristics is based on a memetic to perform the search for an optimal heuristic, improving a MA search enhances the capacity of the efficient choice function to nd good solutions. The proposed SSM shows a better performance than the nine existing methods on a set of different dynamic problems.