Putting It All Together
By now, you have a solid understanding of how GP works. You have learned about several aspects of GP in isolation, but to this point you only have a vague understanding of how all these aspects interact with one another. This page describes a commonly used GP process, very similar to the one described by Koza in his 1992 Book.
The flowchart shown below describes the process in detail (click the image to see full-size):
This flowchart really simplifies the GP process. The important thing to remember is that GP is a highly iterative process. It involves nested loops of procedures. The goal is to evolve successively better individuals with every generation. Theoretically, we might want to run GP indefinitely, but due to limited computational power, we need to define some kind of termination criteria.
Generally the termination criteria has two parts, a successful fitness or a maximum number of generations. We provide GP with some number and say, if you evolve an individual with fitness better than or equal to that number, accept it and stop the run. This means that we have found a solution that is good enough.
Alternatively, we want to stop GP from running too long if it is not progressing. We find that the probability of making further progress drops with number of generations passed, so we define some maximum number of generations. If we haven't succeeded by so many generations, it might be time to stop and try again. There are many reasons a run can stop progressing, which we will discuss further in the next section.
There might be some other termination criteria in place. Ultimately, you want to define some way for GP to make a decision whether to keep trying or to call it quits. This is the termination criteria.
We begin our run by generating the initial population. The population will have some predefined size. Depending on the complexity of the problem, smaller or larger populations might be ideal. For problems like the cart-centering problem, population sizes of 500 might be sufficient. For problems like the automatic invention of electric circuits, huge populations might be necessary.
Once we have the initial population, the first assessment is taken. Though unlikely for most problems, it is possible that an ideal individual was created in the initial population, so the termination criteria is checked after the first assessment. In this step, we apply our fitness calculation to all individuals in the population and store them in some data structure for quick retrieval during processing.
We then enter the genetic programming loop. We begin the loop by choosing a genetic operation-- reproduction, mutation or crossover. We then select the individual(s) to participate in the genetic operation using either tournament selection or fitness proporrtional selection. If we are doing reproduction or mutation, we only select one individual. For crossover, two individuals need to be selected. The genetic operation is then performed and a new offspring individual is created.
The offspring is then placed into a new population, called the limbo population. The limbo population is separate from the main population. It holds individuals created by the genetic operations until the generation has completed. Individuals in the limbo population do not participate in genetic operations yet, so it is not necessary to assess their fitness.
We repeat this process of selecting, copying and modifying until the limbo population is full (until it reaches the population size parameter). Once it is full, we move individuals from the limbo population to the main population and asssess their fitness. This whole process repeats until the termination criteria is satisfied.
With any luck, this process will produce an individual that solves the problem at hand. The simple program flow described here can solve most simple problems, and can be implemented relatively easily. More practical problems usually require modifications to this flowchart, but the idea remains the same: select individuals based on fitness and make minor changes. I recommend playing around with a published GP implementation, or even better implementing your own! Experience is the best teacher.
Congratulations, you have finished reading the Beginner's Guide to Genetic Programming. But don't stop here. If you are seriously interested in GP, read as much as you can on the subject. For more information on GP, see Further Reading.