A brief overview of genetic programming

This section treats GP as a specialization of the genetic algorithm (GA) technique [Holland, 1975]. This is complementary to the perspective in Advances II, which showed how GP relates to Evolutionary Programming [Angeline, 1996]. The basic procedure of a GA can be abbreviated as follows:

1.

Create an initial population of random individuals.

2.

Test the ``fitness'' of each individual.

3.

If an individual is sufficiently good then stop and report success.

4.

Otherwise create a new population from the more fit individuals, using ``genetic operators'' such as reproduction, mutation, and crossover.

5.

Replace the old population with the new population and return to Step 2.

This algorithm characterizes GAs in general, and one can view GP as a specialization of GA for the evolution of executable programs. The primary differences between GP systems and other GA systems are:

In a GP system individuals are generally executable structures such as computer programs, while in other GA systems individuals take various forms (typically bit or character strings).

In a GP system fitness is normally assessed by executing the individuals, while in other GA systems fitness is assessed in ways that depend on the structure of individuals and the problem being solved.

To apply GP to a particular problem one must first specify a set of primitive elements, called functions and terminals, out of which candidate and complete solutions may be constructed. In the simplest case one chooses these elements in a way that ensures that every possible combination of elements will execute without generating an error condition, typically by restricting all values to be of a single data type. One must then provide a fitness function that assesses the quality of individuals in the population, and set values for a range of parameters covering details of structure representation, selection method, initialization procedures, genetic operators, and so on. Once these preparatory steps are taken one can run the genetic programming system to start the algorithm outlined above, producing, in the best case, a program that accomplishes the required task in a short amount of time. Variations are possible and in many cases advantageous; many of these are described in detail in this and earlier volumes of this series [Kinnear, Jr., 1994,Angeline and Kinnear, Jr., 1996].