- author = "Amashini Naidoo",
- title = "Evolving Automata Using Genetic Programming",
- school = "School of Computer Science, University of KwaZulu-Natal",
- year = "2008",
- address = "Durban, South Africa",
- month = feb,
- keywords = "genetic algorithms, genetic programming",
-
URL = "
http://www.cs.ucl.ac.uk/staff/W.Langdon/ftp/papers/naidoo_masters.pdf",
- size = "306 pages",
-
abstract = "Automata have played a significant role in the field
of computer science. The idea of automatically inducing
automata has been the object of the computer science
community for a number of years. Genetic programming
(GP) is an evolutionary algorithm modelled on the
Darwinian idea of natural selection and genetic
recombination, where individuals are typically
represented as tree-structures.
This thesis investigates genetic programming as a method to automatically evolve various classes of automata including finite acceptors, pushdown automata, finite state transducers and Turing machines for benchmark sets of problems. A new approach to evolving automata is introduced whereby each individual in the GP population is represented directly as a graph as opposed to a tree. The methods for evaluation, standard and advanced GP characteristics, and the GP parameters are identified.
Genetic programming proves to be an effective method for inducing automata. The GP systems presented in this thesis successfully induce solutions for finite acceptors; pushdown automata, finite state transducer and Turing machine languages. Furthermore, it is shown that using non-destructive operators and multiple iterations improve the success rate of the GP system.",
- notes = "Supervisor: Dr. Nelishia Pillay",
