Evolutionary Algorithms and Genetic Programming [4]


The Mechanics of Genetic Programming

Having gone through the necessary background, let’s go into the actual mechanics of how genetic programming works. The basic mechanics of GP are very similar to those of genetic algorithms (of which GP is really an offshoot). The algorithm for GP can be summarized as:

  1. Randomly generate an initial population P.
  2. Repeat the following sub-steps until an acceptable solution is found or the maximum number of generations is reached:
    • Execute each program in the population and assign it a fitness value indicating how good a solution to the problem it is.
    • Create a new population by selecting members with a bias towards the fitter programs, and then applying crossover and mutation to produce new P.
  3. The program found to give the best solution to the problem is designated as the result of this run of genetic programming.

For any particular problem it is necessary to specify the list of functions and terminals that shall be used to create the P. These in effect constitute the language to be used to solve the problem. The terminals will form the leaf nodes of each tree, since they take no arguments, and the functions will form all other nodes – having one branch for each argument they require.
So for example, lets say we are attempting to solve a problem which requires finding a boolean function that takes the input from three data lines and returns true if an even number of them are true and false otherwise (the even-3-parity rule). We might use the terminal set:

T = { A, B, C }

And the function set:

F = { AND, OR, NOT }

How do we produce the random trees in the initial population? How do we perform crossover and mutation on them later on during reproduction?

Creation

Creating random trees is easily done by a recursive process:

  1. For the root node select a random primitive from the combined set of functions and terminals.
  2. If a terminal is selected the process ends there.
  3. Otherwise for each of the functions arguments produce a random sub-tree by repeating the same process.

Figure 3 : Randomly created program trees

In practice it is necessary to set a limit on the size to which the tree can grow by only selecting from the list of terminals after reaching a certain depth. Also, since trees consisting of only a single terminal are not likely to be very interesting they are usually excluded by forcing the choice of primitive at the root of the tree to be a function.

Recombination/Crossover

Crossover is the random exchange of genetic material between two parents to produce a unique offspring. In GP this is easily done by selecting a random sub-tree from within each of the parent trees, and then swapping them over. For example:

Figure 4 : Recombination/Crossover

(a) and (b) are the parents. Subtree 1 and subtree 2 are the randomly selected sub-trees. After the sub-trees have been swapped (c) and (d) are the resulting children.

Mutation

Mutation is random changes to the genetic material of a single individual. In GP this is again easily performed by deleting a randomly chosen sub-tree and replacing it with a newly created one. For example:

Figure 5 : Mutation

The program tree is now mutated. The original sub-tree is removed and replaced by a new subtree (which has been randomly generated) to produce the final program tree.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s