Strongly Typed Genetic Programming
Genetic Programming [Koza, 1992] is a technique which enables the construction of programs using
Darwinistic principles. Traditional GP evolve populations of program trees, where each successive generation
is produced from the previous one using an operation called "crossover".
For more on GP and solving problems using GPs, see the sources listed at the bottom of the page.
Genetic Programs traditionaly work by evolving computer programs to solve problems by executing the following three steps:
- Generate an initial population of random compositions of the functions and terminals of the problem (computer programs).
- Iteratively perform the following sub-steps until the termination criterion has been satisfied:
- Execute each program in the population and assign it a fitness value according to how well it solves the problem.
- Create a new population of computer programs by applying the following three operations. The operations are applied to computer program(s) in the population chosen with a Darwinian probability based on fitness.
- Copy existing computer programs to the new population.
- Create new computer programs by genetically recombining randomly chosen parts of two existing programs.
- Mutate the new computer programs by randomly modifying (with small probability) either the structure or the set of leaves of the program
- The single best computer program in the population at the time of termination is designated as the result of the genetic programming paradigm. This result may be a solution (or approximate solution) to the problem.
[Goldberg, ...]
Each program in the population is evaluated in a dynamical environment. Over a period of generations, the individuals in the population tend to exhibit increasing average fitness in dealing with their environment.
The Sufficiency Requirement
The need for the available primitives to be powerful enough so that a solution to the problem can be expressed using them is called the sufficiency requirement [Koza, 1992, page 86]
Closure
Traditional GP contains a limitation known as "closure". All the variables, constants, arguments for functions and values returned from functions must be of the same data type.
Strongly Typed Genetic Programming
Strongly Typed Genetic Programming is a extension of the basic genetic programming approach. It was
first proposed by Montana in 94. Click
here for the original article.
STGP evolve parse trees of typed terms. Types are used to constrain the evaluation results.
Polymorphically Typed Genetic Programming
In [Montana 94, pg 12], the author recognizes the need to specify multiple functions which perform
the same operations on different types. For example, the function IF-THEN-ELSE has to be defined polymorphically
(as a generic function in the text). The first argument is of type BOOLEAN, but the second and third can be any type,
as long as they are the same.
The Curry Howard ismorphism is used to control program breeds at higher levels than it is possible with
a fitness function.
Sources:
- "Genetic Programming and Data Structures", William B Langdon, Springer, May 1, 1998
