Monday, January 24, 2011

Reverse Polish Gene Expression Programming

I've recently realized that Robust Gene Expression Programming could just as well be called Reverse Polish Gene Expression Programming. When I read the original PGEP paper I immediately wanted to define my own GEP using postfix notation, but I found that there where problems that made it messier than I would like. I gave up on that idea and instead started designing a GEP that was more to my liking, ending up with RGEP. During this process I came up with an editing scheme to correct invalid individuals so that they could be evaluated in prefix notation even if they did not encode an expression tree. At some point I realized that the most direct way of performing this edit was to cut the non-coding region (if it exists) and evaluate the individual as a postfix expression while ignoring operators that would cause an underflow.
By ignoring such operators we are sure to end up with one of three cases- an empty stack (very unlikely but possible), a singleton stack, or a stack of depth > 1. The last case can only happen if at least one operator has greater than 2 arguments, which is fairly uncommon. In that case we simple take the top of stack as the result.
I happen to like postfix notation from my experience with Forth, and it is a niche not explored (as far as I know) in GEP literature, so I'm glad to have found a reasonable (and even well justified) way to perform a postfix evaluation in GEP.
I am suggesting in my thesis that a GEP that uses this notation but not the rest of RGEP, which I think is reasonable as I'm making a lot of changes and some people might like the notation but not the rest of it, refer to GEP with reverse polish notation as RPNGEP. I would love if someone took me up on this and used it in a paper.

No comments:

Post a Comment