This paper argues that the Genetic Algorithm and Genetic Programming are pretty much the same - at least in as far as the differentiating features are considered:
GA or GP? That is not the question
Woodward, J.R.
Evolutionary Computation, 2003. CEC apos;03. The 2003 Congress on
Volume 2, Issue , 8-12 Dec. 2003 Page(s): 1056 - 1063 Vol.2
Key points emerging from the paper:
- The greatest distinction between GAs and GP is that of fixed or variable length. In some cases, the size of the required solution sought may be known beforehand, but in other cases, such as evolution of trading rules, imposing a fixed size could reduce the search space hence neglecting optimal solutions.
- GAs do not necessarily represent the evolution of algorithms, but rather a subset of all possible algorithms. GP typically does not evolve computer programs as we would expect, but typically logical or mathematical expressions are evolved, or if then type rules of a classifier system.
- In GAs, the mutation of bit strings takes the form of flipping a single bit. Two main crossover operators have been used; uniform crossover uniformly selects a bit from each position from one of the two parents, one point crossover selects a point at random along the genome of two parents
and takes the left part of parent one and combines this with the right part parent two. In GP, mutation takes the form of replacing a randomly selected sub tree in a program with a randomly generated sub tree. Crossover swaps randomly selected sub trees of two programs.
Essentially the paper states that the differences are unimportant because whether we are considering GAs or GP, whatever the high level representation is, it will ultimately be stored in the computer’s memory as a bit string. I think it’s a fair enough argument but really does not really our day to day understanding and application of the of the two algorithm variants. Because even more “artificial” forms of the algorithm such as Grammatical Evolution (GE) use bit string at lower levels, but this is irrelevant to the problem solver.
Trees in GP
It might be worth hinting at tree representation in GP here. I have shown two examples of tree representations with their equivalent expression:
You might want to try drawing trees for the following two expressions. Note that there is a comma at the end of the first line of each expression:
1.
times(times(times(X1,plus(cos(cos(X1)),X1)), sin(plus(cos(X1),sin(plus(cos(X1),X1))))),plus(cos(minus(X1,X1)),X1))
2.
nor(nor(nor(or(X2,X2),or(X2,X3)),and(nand(X2,X3),X1)), and(nand(and(X1,X1),X3),and(nand(X2,X1),or(X3,X1))))
You can find the tree representations for 1 here and for 2 here.
I shall be using such representations in future posts so this post serves as a reference for any unfamiliarities with tree representations/expressions that may emerge.
