An Empirical Analysis Through the Time Complexity of GE Problems

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

@InProceedings{Chennupati:2013:mendel,

• 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 evolution",
• isbn13 = "978-80-214-4755-4",
• URL = "https://www.researchgate.net/publication/264464282_An_empirical_analysis_through_the_time_complexity_of_GE_problems",
• 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 = "http://www.mendel-conference.org/",

}

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

Citations