Abstraction-Based Genetic Programming

title = "Abstraction-Based Genetic Programming",

school = "Ottawa-Carleton Institute for Computer Science, School of Information Technology and Engineering, Faculty of Engineering, University of Ottawa",

year = "2009",

address = "Ottawa, Canada",

keywords = "genetic algorithms, genetic programming",

URL = "

http://www.site.uottawa.ca/~fbinard/Articles/FranckBinardPhDThesisLastVersion.pdf",

URL = "

http://hdl.handle.net/10393/29805",

DOI = "

doi:10.20381/ruor-13147",

size = "178 pages",

abstract = "This thesis describes a novel method for representing and automatically generating computer programs in an evolutionary computation context. Abstraction-Based Genetic Programming (ABGP) is a typed Genetic Programming representation system that uses System F, an expressive lambda-calculus, to represent the computational components from which the evolved programs are assembled. ABGP is based on the manipulation of closed, independent modules expressing computations with effects that have the ability to affect the whole genotype . These modules are plugged into other modules according to precisely defined rules to form complete computer programs. The use of System F allows the straightforward representation and use of many typical computational structures and behaviours (such as iteration, recursion, lists and trees) in modular form. This is done without introducing additional external symbols in the set of predefined functions and terminals of the system. In fact, programming structures typically included in GP terminal sets, such as if then else, may be removed and represented as abstractions in ABGP for the same problems. ABGP also provides a search space partitioning system based on the structure of the genotypes, similar to the species partitioning system of living organisms and derived from the Curry-Howard isomorphism. This thesis also presents the results obtained by applying this method to a set of problems.",

notes = "Supervisor: Amy Felty",