Evolutionary algorithms and hyper-heuristics for orthogonal packing problems

This thesis investigates two major classes of Evolutionary Algorithms, Genetic Algorithms (GAs) and Evolution Strategies (ESs), and their application to the Orthogonal Packing Problems (OPP). OPP are canonical models for NP-hard problems, the class of problems widely conceived to be unsolvable on a polynomial deterministic Turing machine, although they underlie many optimisation problems in the real world. With the increasing power of modern computers, GAs and ESs have been developed in the past decades to provide high quality solutions for a wide range of optimisation and learning problems. These algorithms are inspired by Darwinian nature selection mechanism that iteratively select better solutions in populations derived from recombining and mutating existing solutions. The algorithms have gained huge success in many areas, however, being stochastic processes, the algorithms' behaviour on different problems is still far from being fully understood. The work of this thesis provides insights to better understand both the algorithms and the problems. The thesis begins with an investigation of hyper-heuristics as a more gen-' eral search paradigm based on standard EAs. Hyper-heuristics are shown to be able to overcome the difficulty of many standard approaches which only search in partial solution space. The thesis also looks into the fundamental theory of GAs, the schemata theorem and the building block hypothesis, by developing the Grouping Genetic Algorithms (OdA) for high dimensional problems and provid- ing supportive yet qualified emp'iL~al evidences for the hypothesis. Realising the difficulties of genetic encoding over combinatorial search domains, the thesis pro- poses a phenotype representation together with Evolution Strategies that operates on such representation. ESs were previously applied mainly to continuous numer- ical optimisation, therefore being less understood when searching in combinatorial domains. The work in this thesis develops highly competent ES algorithms for OPP and opens the door for future research in this area.EThOS - Electronic Theses Online ServiceGBUnited Kingdo