What is Genetic Programming?
Spending as much time as I do working on Genetic Programming, I get this question a lot from my friends and family. Every time I am asked the question, I have to gauge how interested somebody really is to determine how long of an explanation I should give them. Unfortunately, the quick description of what GP is doesn't sufficiently capture the elegance of it, and longer explanations tend to lose most people's interest about half of the way through (some people still think I'm a bio major). Still, over the years I have gathered a great deal of experience explaining GP to people who aren't computer science majors. So this page should sum it all up pretty nicely.
In so few words, Genetic Programming is a method of solving problems using computers through an analogue of natural selection. It is a way to have computers automatically solve problems, without having to define or even know the form or structure of the optimal solution ahead of time. You simply provide genetic programming with basic building blocks of the solution and some method of analyzing how well a proposed solution solves the problem and GP does the rest.
The simplified flowchart to the left shows what this process looks like from the outside. What is amazing about this is that from this outside perspective, this would really seem like an intelligent system performing the task. Though it would certainly be a stretch to call it artificial intelligence, it very well could be artificial creativity. You might expect that inside the little GP box, there is an intelligent programmer working on a solution through logic and design, but in reality, no such programmer exists!
You may notice that in the simplified flowchart to the left that there is a U-shaped arrow connecting the Genetic Programming box to itself. This is to indicate that the GP process is an iterative one. GP begins with some initial guess at a solution and successively attempts to improve the solution over time. Once some criterion for termination (either an ideal individual or some predefined run time), GP returns the best individual so far. That individual is deemed the result of GP.
To understand what is going on inside the Genetic Programming box, refer to the diagram below:
Here we begin to see how GP actually operates. It begins by generating some initial population. The fitness of all individuals in the population is then assessed. It is unlikely that this initial generation will contain an ideal individual, but some will likely be better than others. We begin the GP loop by selecting the individuals that solve the problem best and allowing them to reproduce, making small random changes to their construction. As this process repeats numerous times, we find that on average, the fitness of the population tends to increase. Don't be scared if you're a little confused; this guide will explain everything in more detail.
To understand the basics of Genetic Programming, we should first explore the basics of Natural Selection.