Introduction
Genetic Programming (GP) is an enhancement to Genetic Algorithms (GA) and is a subclass of the Evolutionary Algorithms (EA). GP has been invented by John Koza. He and his collegues were able to re-invent solutions human beings developed on their own with the power of their brains. These inventions includes mainly the field of electric circuits, which is not surprising. As I wrote in my weblog entry Genetic Algorithms: The Darwinian Way, P-SPICE is a powerful simulator for related problems. It should not be overseen that a re-invention was somehow forced by the applier of an evolutionary approach, as Koza did with his new concept of GP. But it shows that a GP has the potential of finding solutions to NP-hard problems a human could only solve by chance. With the open source genetic algorithms Java framework JGAP you are even able to execute Genetic Programs as well as classic evolutionary algorithms.
Main concepts
The difference between GP and GA is the representation of the internal state of the population. For GA's static data types like fixed-length strings will be used. GP's encode the population's state in the form of a program. The program is seen as a tree with a root element and each element having zero to two children. There are of course no back-references between the elements, which means a child cannot have his parent or an element from another subtree as a child.
As with GA's the genetical operations mutation, crossing-over and replication exist. They will be applied similarly for GP-populations as this is the case with GA-populations. Instead of randomly modifying characters within a string in GA in a mutation step we randomly substitute subtrees in GP. The subtitute can either be generated randomly from scratch. Or an existing subtree can be used as template, maybe modified before inserted maybe kept in its original state.
Applicability
GP's can be used to solve problems wherever GA's can be applied. Furthermore, GP's are more powerful than GA's because of them allowing for more dynamic constructs to represent individuals of a population.
If, for instance, you would like to simulate a robot and evolutionary builkd up his brain being able to run thru a maze gathering food then a GP would be best to use. A GA would be too simple to use, althouh possible either. As I like to say: With assembler you can do anything possoble with 4th GL's (or ever nth GL's). But it is more likely to use an algorithm or a concept being more capable for a certain problem.
Popular example for maze-based problems is the Ant-trail (e.g. the Santa Fe Ant-trail).
Conclusion
GP's are a powerful mechanism extending GA's capabilities. As always with EA's the crux is to represent the problem accordingly. If able to do the representation solutions can be found easily. Then, CPU time would be the main constraint.
