- title = "Computational complexity and the genetic algorithm",
- author = "Bart Rylander",
- year = "2001",
- school = "University of Idaho",
- address = "USA",
- month = "7 " # jun,
- keywords = "genetic algorithms, genetic programming, computational complexity, Quantum evolutionary programming",
- description = "Thesis (Ph. D.)--University of Idaho, 2001.; Includes bibliographical references (leaves 104-108).",
- oai = "oai:xtcat.oclc.org:OCLCNo/ocm48450722",
-
URL = "
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.101.1016.pdf",
-
URL = "
https://www.mathgenealogy.org/id.php?id=189738",
-
URL = "https://www.proquest.com/openview/36f99044dae865d4a16f1c6eb11873ea/1",
- size = "117 pages",
-
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.
ProQuest Dissertations Publishing, 2001. 3022336. Major professor: James A. Foster",
