An Analysis of the Genetic Algorithm and Abstract Search Space Visualisation

Abstract

The Genetic Algorithm (Holland, 1975) is a powerful search technique based upon the principles of Darwinian evolution. In its simplest form the GA consists of three main operators - crossover, mutation and selection. The principal theoretical treatment of the Genetic Algorithm (GA) is provided by the Schema Theorem and building block hypothesis (Holland, 1975). The building block hypothesis describes the GA search process as the combination, sampling and recombination of fragments of solutions known as building blocks. The crossover operator is responsible for the combination of building blocks, whilst the selection operator allocates increasing numbers of samples to good building blocks. Thus the GA constructs the optimal (or near-optimal) solution from those fragments of solutions which are, in some sense, optimal. The first part of this thesis documents the development of a technique for the isolation of building blocks from the populations of the GA. This technique is shown to extract exactly those building blocks of interest - those which are sampled most regularly by the GA. These building blocks are used to empirically investigate the validity of the building block hypothesis. It is shown that good building blocks do not combine to form significantly better solution fragments than those resulting from the addition of randomly generated building blocks to good building blocks. This results casts some doubt onto the value of the building block hypothesis as an account of the GA search process (at least for the functions used during these experiments). The second part of this thesis describes an alternative account of the action of crossover. This account is an approximation of the geometric effect of crossover upon the population of samples maintained by the GA. It is shown that, for a simple function, this description of the crossover operator is sufficiently accurate to warrant further investigation. A pair of performance models for the GA upon this function are derived and shown to be accurate for a wide range of crossover schemes. Finally, the GA search process is described in terms of this account of the crossover operator and parallels are drawn with the search process of the simulated annealing algorithm (Kirkpatrick et al, 1983). The third and final part of this thesis describes a technique for the visualisation of high dimensional surfaces, such as are defined by functions of many parameters. This technique is compared to the statistical technique of projection pursuit regression (Friedman & Tukey, 1974) and is shown to compare favourably both in terms of computational expense and quantitative accuracy upon a wide range of test functions. A fundamental flaw of this technique is that it may produce poor visualisations when applied to functions with a small high frequency (or order) components.