| A genetic algorithm is a biologically inspired method for function optimization that is loosely based on the theory of evolution. It is typically used when there is little knowledge of the solution space or when the search space is prohibitively large. Despite years of successful application to a variety of problems ranging from superstructure design to simulation of bacteria, little has been done to characterize the complexity of problems as they relate to this method.; Complexity is critical however. Though the metaphor is seductive, the genetic algorithm is only a simulation of evolution. The accuracy of this simulation changes daily as more knowledge is gained from the biological communities and as computer researchers find better methods for solving problems regardless of the strict adherence to the biological inspiration. In the end, the genetic algorithm is a search method that must be implemented as a program consisting of loops and if statements. Given this, it seems reasonable to evaluate whether programs developed using this method provide any advantage in terms of efficiency over other methods. To do this, there must first be a way for evaluating the complexity of problems specifically for the genetic algorithm. This technique must enable a direct comparison between the GA-complexity of problems and what is already known about the complexity of problems. In this way it is possible to evaluate whether there is a “gain” in using genetic algorithms beyond programmer ergonomics.; This dissertation describes a method for evaluating the complexity of a problem specifically for genetic algorithms. The method is used to define two specific genetic algorithm complexity classes. GA-hardness is defined as well as a method for GA reduction. In addition, the complexity of problems specifically for Genetic Programming (GP) is analyzed. Finally, the impact of quantum computers upon the complexity classes for evolutionary computation is examined. All of these areas are presented as peer-reviewed publications that have been developed as part of this research. |
