Error Thresholds and Optimal Mutation Rates in Genetic Algorithms

Citation

Ochoa G (2000) Error Thresholds and Optimal Mutation Rates in Genetic Algorithms. Doctor of Philosophy. University of Sussex.

Abstract
When applying a genetic algorithm to solve a given problem, the designer faces a large number of choices, with little theoretical guidance and few rules of thumb about how to proceed. Among these choices, the setting of evolutionary parameters (e.g. mutation rate, recombination rate, population size and selection parameters) is important since their values determine the performance of the algorithm to a great extent. However, finding a good combination of parameters is not an easy task since they interact with one another non-linearly and cannot be optimised one at a time. Moreover, ‘optimal' parameter settings are believed to be problem-dependent. Themutation rate is acknowledged as one of the most sensitive parameters, so good heuristics for setting the mutation rate are welcomed. This thesis brings the fundamental notion of the error thresholds of replication from molecular evolution into the field of evolutionary computation. Error thresholds are intuitively related to the idea of an optimal balance between exploration and exploitation in genetic search. So, it is hypothesised and empirically demonstrated here, that error thresholds are related to the more familiar notion of optimal mutation rates in GAs. This finding sheds new light on the sensitivity of the mutation rate and points toward useful heuristics for setting this parameter. Some results on the effects and usefulness of recombination are also presented. This dissertation also introduces consensus sequence plots, which are adapted from theoretical biology, as a new visualisation tool to the genetic algorithms community. They are used for locating error thresholds on general landscapes, and are shown to reveal several features of the landscape structure. The insights and empirical evidence gathered here support a heuristic that sets a rate based on one mutation per genotype, to be scaled according to the selection pressure and also potentially modified for very redundant genotypes. However, since the selection pressure can be controlled, this rule is shown to hold over a wide range of problem types.

People

Professor Gabriela Ochoa

Professor, Computing Science