I am currently in the process of adding Genetic Programming to Encog. At their most simple level, a Genetic Programs can be used to create a formula from training data. A neural network or support vector machine is a black box. You really cannot see into how either of these two algorithms is actually providing the values that they are computing. However, with a Genetic Program, you are left with a formula. The formula will likely give you more understanding into the nature of the data than a neural network or SVM.
To implement Genetic Programming I must have a way to represent formulas in a program. There are many different ways of doing this. Consider the following formula.
In Encog, I refer to the above formula as the “Common Form” of the equation. Encog can parse the above formula and store it internally. Internally Encog stores these expressions in an opcode format based on Reverse Polish Notation (RPN).
RPN does not require parenthesis. This is a very nice feature of RPN. There are no rules of precedence. Everything is non-ambiguous. Consider a very simple expression, such as 2+4. In RPN this would be stored as follows.
The above basically says to push 2 and 4 onto a stack. Then once we hit the + operator, we pop 2 values off the stack and add them. We know to pop two values off the stack because the plus operator requires two operands. The result of the addition, which is 6, is placed back on the sack. Once the entire expression is evaluated, the answer is the last value on the stack. Now consider a slightly more complex expression.
Written in RPN, this expression would be as follows.
There we start off just as before. 2 and 4 are added and the resulting 6 is on the stack. But now we push another 2 onto the stack. The division now pops 6 and 2 from the stack and divides, resulting in 3.
Recall the slightly more complex equation from earlier in this article?
This can be expressed in RPN as well. The above expression in RPN is as follows.
RPN also lends itself nicely to trees. The above expression could be rendered as the following tree.
The Encog Workbench rendered the above tree. You can see that the operands for each operator and function are represented by its leaf nodes. Encog is also capable of rendering the expression as a mathematical formula. To render as a formula, LaTex is used. Here you can see the above expression rendered as a formula.