Search and selection methods for hyper-heuristics.
Loading...
Date
2018
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
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.
Description
Doctoral Degree. University of KwaZulu-Natal, Durban.