Genetic algorithms, annealing, and dimension alleles

Abstract

The purpose of this thesis is to use theory and practical examples to show that genetic algorithms can be successfully applied to contexts beyond the standard genetic algorithm theory (particularly to problems with real coded solutions). Part of this process will involve defining Annealing, a general global optimization strategy, and seeing how genetic algorithms obey the annealing procedures. Annealing is the process of continually finding, testing, and converging within partitions on unconverged solution space (thereby operating on a recursive partition set on the solution space). The idea originates from the observation of how the simulated annealing can be seen as viewing a problem's payoff surface. The annealing perspective allows the discussion of new aspects of a range of genetic algorithm topics (including convergence issues such as the use of niche methods). An important issue discussed is that of alphabet cardinality and the use of dimension alleles. Genetic algorithm experimentation on the linear and nonlinear transportation is presented as a case study of the application of richer genetic algorithms. The results indicate that richer data structures and genetic operators are valuable extensions to the genetic algorithm when solving more sophisticated problems. Theoretical discussions about the use of dimension alleles and other such genetic algorithm extensions appear later in the thesis (making use of the annealing perspective). A conclusion is that dimension alleles can be used in a genetic algorithm subject to a careful design of genetic operators. An early chapter in the thesis presents genetic algorithms and standard genetic algorithm theory. Following this is a chapter used to illustrate genetic algorithms by: discussing computer implementation options, detailing an animation system for a simple genetic algorithm, and using a specially designed artificial problem to illustrate a genetic algorithm in use (and informally raise certain convergence issues in advance of the later theoretical discussions).