Abstraction-Based Genetic Programming: An Application Of The Polymorphically-Typed Lambda Calculus To Genetic Programming

Abstraction-Based Genetic Programming (ABGP) is a novel Genetic Programming (GP) system in which the set of all possible genotypes is partitioned by the proofs to which each program is linked via the Curry- Howard isomorphism. In the context of ABGP, proofs are related to computer programs in the same way as species are related to organisms in the biological world. They can be seen as patterns into which alleles of genes may be plugged in. In this analogy, genes are types and an allele of a gene is a closed typed computational block that may be combined with other blocks to form an organism. The type of an allele is the gene to which it corresponds.