Genetic Programming

Date: 2015-10-07; view: 504.

In his textbook, John Koza presented a large number of sample problems that can be solved with genetic programming. He developed a systematic way of relating particular problems to a canonical set of design decisions that a developer uses to model a problem.

One step is the selection of what he calls terminals and functions. The ant will be controlled by behavior expressions, which are tree-like structures of terminals and functions. Terminals are primitive operations or literals that cannot be decomposed further. Functions are higher-level operations that use other functions or terminals. In our case, the artificial ant has terminals Left, Right, and Move. One member of the function set is the FacingFood Boolean, which takes two terminal or function arguments. The statement "if FacingFood, then Left else Right" is an example of an expression that has the function FacingFood and two children: the terminals Left and Right. I'll also generate two other functions. The first, which I'll call P2, has two clauses which are themselves either terminals or functions. An example of this is the expression "Right;Move". A second function that I'll add is P3. This is just like P2, except that it has three clauses. An example of P3 is the expression "Move; Right; if FacingFood then Right else Move".

The GP algorithm begins by generating a population of random expressions. One parameter that controls the algorithm is population size; this is one of the parameters that the user can set in the UI. These expressions are then executed and evaluated, using a fitness measure. Designing this fitness measure is another step in the canonical GP design fitness criteria. I want to select efficient ants, those that gather a lot of food with few steps, so the fitness measure weighs both food gathered and the number of steps used. In my implementation, I subtract the steps from the food gathered and add 1000, so that fitness is always positive. Hence an ant with a higher fitness measure is going to be more successful than an ant with a lower measure.

When the initial, random first generation is completed, the real work of GP begins. The first step is selection, which is choosing the best ants and copying them to the next generation. Most GP implementations use one of a number of sophisticated selection techniques, but for the sake of simplicity this implementation copies the best 10 percent, as measured by our fitness criteria. These selected ants will be the "parents" of all the remaining ants in the subsequent generation.

Subsequent generations begin with the pool of parents that were replicated from the prior generation. Since this is only 10 percent of the available population, I need to fill the remaining slots by selecting parents and breeding them to create the next generation. Pairs of parents are selected, and each pair of parents yields a pair of children, each of which combines elements of both parents. Parents are selected according to fitness. In general, fitter parents are more likely to be selected to breed.

The crossover algorithm (see Figure 5) is used to breed a pair of children from a pair of parents. A random crossover point is chosen in each parent, and the subtree beneath these crossover points is swapped between the parents, creating the two offspring.

Most GP algorithms also implement mutation. This involves making a random change in a small number of offspring in order to maintain diversity in the population. Mutation is essential because otherwise the population becomes completely dominated by a few good bloodlines, which makes it difficult to continue progress beyond a certain point. This implementation performs a simple mutation step during the crossover operation to introduce randomness. When a terminal node is copied, a random terminal is substituted two percent of the time.

Figure 5 Crossover (Breeding) Operation