Genetic programming is a computer science method, inspired by evolutionary biology, for automatically solving problems, without having to know or define the form or structure of the optimum problem structure beforehand. You define the basic building blocks (functions, constants, and variables) of the problem and then the component does the rest. Genetic programming solves problems by evolving a group or population of candidate individuals through successive generations, selecting fitter (or better) child individuals for each generation, until a solution is found. It uses evolutionary biology techniques such as inheritance, mutation, selection, and crossover (also called recombination).
Similar to genetic algorithms, in genetic programming (TRSGeneticProgramming component), there is a population of individuals (TRSGPPopulation<TGAFloat>). Genetic programming works by evolving your population towards the solution of the problem. The difference in Genetic Programming is in the representation of the DNA of the individuals. Instead of the bits in genetic algorithms, Genetic Programming allows you to design the problem more naturally by specifying basic building blocks of a program: functions, constants, and variables. GP combines these building blocks to create a program for each individual, expressed as a tree structure.
 |
| Genetic Programming Tree for the equation X + Y * 2 |
The building blocks in RiverSoftAVG Genetic Algorithms & Programming Component Library (GACL) are called Instructions:
| • | Instructions are a shared set of functions, constants and variables (i.e., every individual has access to the complete set) |
| • | Functions define their Arity, which means the number of sub-instructions they can accept. |
| • | Functions may have an arity of 0 or more. |
| • | Functions have a OnExecute event defined to control what they do |
| • | Constants and Variables always have an arity of 0. |
| • | Constants, Variables, and Functions of Arity = 0 are called Terminals. |
| • | Constants return the value of their constant, which may be different for each individual and for each instance of the constant in the individual if the value has been mutated. |
| • | Variables return the value of the variable as it is passed in when executing a genetic program |
From these building blocks, RiverSoftAVG Genetic Algorithms & Programming Component Library (GACL) builds the GP Program Trees, which are unique to each individual. GP Trees have the following characteristics:
| • | Trees are made up of 1 or more nodes with an associated Instruction, representing functions, constants, and variables |
| • | Every node, except the root node, has 1 parent |
| • | Function nodes may have 0 or more children, which equals the Arity of its associated Instruction |
| • | Any genetic operations (reproduction, mutation, inversion) that transform a GP Tree will preserve the Arity of the associated Instruction, i.e., a terminal node cannot have children or a function requiring 2 children cannot have less than that |
| • | The string representation of a tree in the RiverSoftAVG Genetic Algorithms & Programming Component Library (GACL) is in prefix notation similar to Lisp, e.g., the tree to the right would be represented as "(+ X (* Y 2))". |
 |
| Genetic Program Tree for the Santa Fe Ant Trail problem |
Just like genetic algorithms, your population of individuals is bred to find the fittest individuals for a problem. Parents are selected from the current generation to reproduce the children of the next generation. Evolving a new generation involves:
| • | Selecting 2 parents to reproduce |
| • | Splicing the DNA trees (crossover or recombination) of the 2 parents together to make a child (the child inherits the parents DNA trees) |
 |
| Reproduction and Crossover of 2 Parents to make a Child |
| • | Optionally Mutating and Inverting the DNA trees of the child to provide randomness |
| • | Repeating the above steps until the population of the new generation has been produced. |
After the new generation is bred, genetic programming looks at the new population to see if any of the individuals solve the problem. In genetic programming terms, this usually means executing the GP tree to evaluating the "fitness" of each individual (a numeric score that measures the ability of the individual). If any individual is "fit enough", the evolutionary search can stop.
Genetic Programming is an incredibly powerful technique for automatically solving problems. However, it is not a panacea. Genetic programming requires careful crafting of the building block instructions and the fitness evaluation to properly guide the genetic programming components. It is highly recommended that you examine the demo applications provided. There is a good little tutorial on genetic programming at www.geneticprogramming.us. For more in-depth information about genetic programming, "A Field Guide to Genetic Programming" by Poli et al is available for free (or to buy) from http://www.gp-field-guide.org.uk/ . Finally, obtaining the original book on genetic programming, "Genetic Programming: ON the Programming of Computers by Means of Natural Selection" by John R. Koza is highly recommended.