Computational complexity and the genetic algorithm

Created by W.Langdon from gp-bibliography.bib Revision:1.4549

  title =        "Computational complexity and the genetic algorithm",
  author =       "Bart Rylander",
  year =         "2001",
  school =       "University of Idaho",
  address =      "USA",
  month =        jun,
  keywords =     "genetic algorithms, genetic programming, computational
                 complexity, Quantum evolutionary programming",
  URL =          "",
  size =         "117 pages",
  description =  "Thesis (Ph. D.)--University of Idaho, 2001.; Includes
                 bibliographical references (leaves 104-108).",
  oai =          "",
  abstract =     "A genetic algorithm is a biologically inspired method
                 for function optimisation 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 characterise 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 analysed. 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.",
  notes =        "Includes the text of four previously published papers:
                 Computational complexity and genetic algorithms --
                 Genetic algorithms and hardness -- Computational
                 complexity, genetic programming, and implications --
                 Quantum evolutionary programming.

                 Major professor: James A. Foster",

Genetic Programming entries for Bart I Rylander