In the Introduction to Genetic Algorithms video tutorial, we saw how GAs are powerful evolutionary algorithms that are used to synthesize solutions and optimize parameters for problems that are too complex or convoluted for humans to solve on their own.
They work well in cases where semantics isn’t a huge concern. So in the case of the video, each possible step the mouse was able to take was encoded as an integer (gene). Strings of these genes (chromosomes) were built, and we kept evolving them through mutation and crossover until we found a chromosome that got the mouse from the start of the maze over to the cheese at the end.
We weren’t concerned about what order the integers were in a chromosome, or if any of the states were “invalid”. Sure, there were some chromosomes that had a lot of noise or useless actions, but nothing that inherently didn’t make sense. This is what I mean by “semantics”.
So what happens if we wanted to use GA to evolve a mathematical expression? An area where semantics does matter.
The goal here will be to find a Mathematical expression that will yield the following outputs from inputs:
When input = 2, Output = 9
When Input = 0, Output = 5
When Input = 1, Output = 6
When Input = .5, Output = 5.125
The exact expression we’re looking for the computer to find is y = x^2 + 5.
We could encode each mathematical operation as an integer:
0: x
1: ^
2: *
3: +
4: -
5 through 9: (can be a number/digit in the range 0 to 5)
A few possible states we could generate:
701846 (would be 2x^3 - 1)
601846 (would be x^3 - 1)
031111 (would be x+^^^^)
222223 (would be *****+)
434343 (would be -+-+-+)
The first two states aren’t exactly the winning expression that we want, but they’re valid. The last 3 though are completely bogus.
Even if we started with a proper string, a slight alteration during the mutation process can have a drastic result on the offspring. A generated expression such as 701846 undergoing a mutation could result in 101846, which now results in the expression ^x^3 - 1 — which doesn’t make much sense, does it?
In order to deal with these invalid states, we'd need to include mechanisms into the parser that would repair or the damaged expressions prior to evaluating their fitness. It's certainly doable, but not very practical, and it’s definitely not scalable as we advance to building more complicated expressions. In theory, we’d need to manually code in more and more rules on how the computer should repair/handle invalid states.
Enter Genetic Programming
Genetic programming has qualities that naturally safeguards it from spitting out faulty states like above.
Unlike GA, genetic programs are typically represented as a structure of “nodes” connected to each other somehow in memory. One of the more common structures used to represent them are trees.
The math function (4 + (X/25) - (9 * sqrt(X)) represented by a tree structure:
But the nice thing here is that the restrictions are built directly into the tree, so we don’t need to deal with invalid states.
The root node, and also the internal nodes (nodes with child nodes) can only be operators. The terminal nodes (those without child nodes) can only contain constants or variables. We don’t connect an operator to a constant or variable node. Connecting nodes in this manner prevents us from generating a state like +X/-9+6.
It’s possible we could run into divide by zero errors, but these can be easily dealt with during the fitness evaluation stage of the GP.
The bottom line
Practically speaking, there’s a fine line between what constitutes as a “genetic algorithm” or “genetic program”. At the end of the day — it really comes down to the classification and context of the problem you’re solving, the particular mechanics you’re using, and the format of the states that you’re generating.
In general, the primary differences come down to this:
Genetic Algorithms are traditionally built using strings of bits, integers, or characters that represent the genes that make up a chromosome. While this can make it pretty easy to manage and and evolve a GA, it can make evaluating them more cumbersome when they are applied to applications where they have a propensity to generate invalid states. Additionally, the fact that GA chromosomes are typically restricted by a fixed length results in decreased flexibility in the ability to scale as a problem becomes more complex.
With Genetic Programs, we adopt the same underlying evolutionary concepts and foundation from GA, but encode the individuals with a tree (or similar) structure rather than a string or list of genes. A consequence of this is that the overhead required to grow and maintain these structures is significantly increased. On the positive side, we have more control to enforce limits directly into the programs we build which greatly decreases the occurrence of invalid states. Due to the variable size of this type of representation, GP individuals are inherently more flexible than GA chromosomes, and can grow and scale as needed according to a problem's complexity — while efficiently preserving limits and rules throughout the tree.
