An Empirical Analysis Through the Time Complexity of GE Problems

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

  author =       "Gopinath Chennupati and Conor Ryan and 
                 Raja Muhammad Atif Azad",
  title =        "An Empirical Analysis Through the Time Complexity of
                 GE Problems",
  booktitle =    "19th International Conference on Soft Computing,
                 MENDEL 2013",
  year =         "2013",
  editor =       "Radomil Matousek",
  pages =        "37--44",
  address =      "Brno, Czech Republic",
  month =        jun # " 26-28, Brno",
  organisation = "Brno University of Technology",
  keywords =     "genetic algorithms, genetic programming, grammatical
  isbn13 =       "978-80-214-4755-4",
  URL =          "",
  abstract =     "Computational complexity analysis on Evolutionary
                 Algorithms can provide crucial insight into how they
                 work. While relatively straight forward for fixed
                 length structures, it is less so for variable length
                 structures, although initial work has already been
                 conducted on tree based Genetic Programming (GP)
                 algorithms. Grammatical Evolution (GE) is a variable
                 length string based Evolutionary Algorithm (EA) that
                 evolves arbitrarily complex programs through complex
                 gene interactions, but thus far, no such analysis has
                 been conducted. We empirically analyse the time
                 complexity of GE on two well known GP problems: the
                 Santa Fe Ant Trail and a Symbolic Regression problem.
                 Using a power law, we analyse the time complexity of GE
                 in terms of population size. As a result of this,
                 several observations are made estimating the average
                 terminating generation, actual length and effective
                 lengths of individuals based on the quality of the
                 solution. We show that even with the extra layer of
                 complexity of GE, time increases linearly for GE on
                 Santa Fe Ant Trail problem and quadratic in nature on a
                 symbolic regression problem as the size of simulations
                 (i.e. population size) increase. To the best of our
                 knowledge, this is the first attempt measuring the
                 run-time complexity of GE. This analysis provides a way
                 to produce a reasonably good prediction system of how a
                 particular run will perform, and we provide details of
                 how one can leverage this data to predict the success
                 or otherwise of a GE run in the early generations. with
                 the amount of data collected.",
  notes =        "",

Genetic Programming entries for Gopinath Chennupati Conor Ryan R Muhammad Atif Azad