Does Chomsky complexity affect genetic programming computational requirements?
Created by W.Langdon from
gp-bibliography.bib Revision:1.8098
- @InProceedings{Burger:2011:SAICSIT,
-
author = "Clayton Burger and Mathys C. {Du Plessis}",
-
title = "Does Chomsky complexity affect genetic programming
computational requirements?",
-
booktitle = "Proceedings of the South African Institute of Computer
Scientists and Information Technologists Conference on
Knowledge, Innovation and Leadership in a Diverse,
Multidisciplinary Environment",
-
year = "2011",
-
pages = "31--39",
-
address = "Cape Town, South Africa",
-
publisher = "ACM",
-
keywords = "genetic algorithms, genetic programming, theory of
computation, Turing machines",
-
isbn13 = "978-1-4503-0878-6",
-
DOI = "doi:10.1145/2072221.2072226",
-
size = "9 page",
-
abstract = "This paper presents an exploration into the
relationship between Chomsky problem complexity, as
defined by Theory of Computation, and the computational
requirements to evolve solutions to these problems.
Genetic programming is used to explore these
computational requirements by evolving Turing machines
that accept the languages posed. Quantifiable results
are obtained by applying various metrics to the
evolutionary success of these evolved Turing machines.
The languages posed are samples out of three language
classes from the Chomsky hierarchy, with each class
having increasing levels of complexity based on the
hierarchy. These languages are evolved on a two-tape
Turing machine representation by making use of genetic
operators found to be effective in the literature. By
exploring the effects of the genetic programming
algorithm population sizes and coupled genetic operator
rates, it was found that the evolutionary success rates
of the classes of Regular and Context-Sensitive
problems have no statistical difference in
computational requirements, while the Context-Free
class was found to be more difficult than the other two
Chomsky problem classes through the statistical
significance discovered when compared to the other
classes.",
-
notes = "SAICSIT '11",
-
acmid = "2072226",
- }
Genetic Programming entries for
Clayton Burger
Mathys C Du Plessis
Citations