A qualitative model of evolutionary algorithms
Francois Fagan · SUNScholar (Stellenbosch University) · 2014
ENGLISH ABSTRACT: Evolutionary Algorithms (EAs) are stochastic techniques, based on the idea of biological evolution, for finding near-optimal solutions to optimisation problems. Due to their generality and computational speed, they have been applied very successfully in a wide range of disciplines. However, as a consequence of their stochasticity and generality, very little has been rigorously established about their performance. Developing models for explaining and predicting algorithmic performance is, in fact, one of the most important challenges facing the field of optimisation. A qualitative version of such a model of EAs is developed in this thesis. There are two paradigms for explaining why EAs are expected to converge toward an optimum. The traditional explanation is that of Universal Darwinism, but an alternative explanation is that they are hill climbing algorithms which utilise all possible escape strategies — restarting local search, stochastic search and acceptance of non-improving solutions. The combination of the hill climbing property and the above escape strategies leads to a fast algorithm that is able to avoid premature convergence. Due to the difficulty in mathematically or empirically explaining the performance of EAs, terms such as exploitation, exploration, intensity and diversity are routinely employed for this purpose. Six prevalent views on exploitation and exploration are identified in the literature, each expressing a different facet of these notions. The coherence of these views is substantiated by their deducibility from the proposed novel definitions of exploitation and exploration. This substantiation is based on a novel hypothetical construct, namely that of a Probable Fitness Landscape (PFL), which both unifies and clarifies the surrounding terminology and our understanding of the performance of EAs. The PFL is developed into a qualitative model of EAs by extending it to the notion of an Ideal Probability Distribution (IPD). This notion, along with the criteria of diversity and computational speed, forms a method for judging the performance of EA operators. It is used to explain why the principal operators of EAs, namely mutation and selection, are effective. There are three main types of EAs, namely Genetic Algorithms (GAs), Evolution Strategies and Evolutionary Programming, each of which employ their own unique operators. Important facets of the crossover operator (which is particular to GAs) are identified, such as: opposite step vectors, genetic drift and ellipsoidal parent-centred probability distributions with variance proportional to the distance between parents. The shape of the crossover probability distribution motivates a comparison with a novel continuous approximation of mutation, which reveals very similar underlying distributions, although for crossover the distribution is adaptive whereas for mutation it is fixed. The PFL and IPD are used to analyse the crossover operator, the results of which are contrasted with the traditional explanations of the Schema Theorem and Building Block Hypothesis as well as the Evolutionary Progress Principle and Genetic Repair Hypothesis. It emerges that the facetwise nature of the PFL extracts more sound conclusions than the other explanations which, falsely, attempt to prove GAs to be superior.