Next: , Up: Other Biologically-Inspired Approaches


1.4.1 Genetic Programming

Genetic programming is one of many different computational approaches which attempt to harness the power of mathematical algorithm of evolution to solve problems. Many of these approaches have met with great success. The creative power of evolution has been amply demonstrated. Most evolutionary techniques require a very precise fit between between the problem space and the solution search space. This is no different for the particular subfield of genetic programming. However, there solutions are represented by actual executable computer programs, which are executed to calculate their fitness. The program may take many different forms, such as trees or linear sequences of instructions.

The programs are evolved by repeatedly applying to them a number of evolutionary operators according to a particular algorithm (there are many such possible algorithms). These operators include: a mutation operator, which changes the solution more of less randomly; a crossover operator, which combines many different solutions to create new ones; an evaluation operator, which calculates the fitness of the many different solutions — that is, how well they solve the problem at hand; a selection operator, which chooses a number of solutions from the present generation to participate in the next one. These operators are combined and sequenced according to many different, personal recipes. An exposition is presented in [Banzhaf et al. 1998].

Genetic programming has seen many successes. It has been used successfully in image and pattern recognition, robot control and data mining, for example.

Nevertheless, many aspects of genetic programming have been disappointing to even its proponents. Perhaps the most important ones have to do with the amount of tailoring that needs to be done to the evolutionary operators listed above (more specifically, mutation and crossover) to make them apply to computer programs. In particular, the crossover operator is the subject of intense scrutiny. A chapter in [Banzhaf et al. 1998] is titled “Chapter 6: Crossover — The Center of the Storm”. From this chapter:

In nature, most crossover events are successful — that is, they result in viable offspring. This is a shart contrast to GP crossover, where over 75% of the crossover events are what would be termed in biology “lethal” [Banzhaf et al. 1998, p. 157].
Among the differences noted between biological crossover and GP crossover are the following three (also from the same source): The last property is often appealed to as a source of the creative power of crossover. While GP crossover lacks these three properties, in the Monod Cell the operator can easily accomodate them. This is because a Monod Cell program is defined by a genome consisting of a set of separate Monod genes, each defining an individual programlet or Monod protein. By adopting a computational approach explicitly inspired by the biology of the cell, we obtain, for free, powerful extra properties.

Another essential distinguishing factor between GP and Monod is that, by its definition, Monod creates parallelizable programs.

FIXME: More here.