Hyper-heuristics for the automated design of black-box search algorithms.

摘要

Within the field of Black-Box Search Algorithms (BBSAs), there is a focus on improving algorithm performance over increasingly diversified problem classes. However, these general purpose problem solvers have no guarantee to perform well on an arbitrary problem class that a practitioner needs to solve. The problem classes that the research in this thesis most applies to are difficult problems that are going to be solved multiple times. BBSAs tailored to one of these problem class can be expected to significantly outperform the more general purpose problem solvers, including canonical Evolutionary Algorithms (EAs). The first paper in this thesis explores a novel method in which these BBSAs can be created through the use of hyper-heuristics.;Hyper-heuristics have the tendency to over-specialize on the problem configuration that it is given rather than generalizing to the problem class. The evolved BBSA should be robust to changes in problem configuration. The second paper in this thesis presents a multi-sample approach geared towards increasing the robustness of the resulting BBSAs.;As with other CI techniques, such as Genetic Programming, hyper-heuristics are affected by the size of the search space. If the hyper-heuristic has too much genetic material, it could cause the search space to be too large to effectively traverse. However if the hyper-heuristic has too little genetic material, it may not be capable of creating a high quality BBSA. The third paper in this thesis explores the scalability of hyper-heuristics as the amount of genetic material is increased. Additionally, this paper explores the impact that the nature of the added primitives have on the performance of the hyper-heuristic. These papers show that hyper-heuristics can be used to evolve BBSAs that perform well on a problem of indiscriminate type.