Friday, April 9, 2010

Bitwise Knowledge

I believe that there is an important and poorly investigated aspect of GEP that may be allow
it to outperform GAs in particular, as well as some other methods.
The main idea is that if the GEP is used for parametric optimization (as discussed by its creator) it creates a value out of more then just bits, but rather encodes knowledge about the value in the form of a tree. While this idea is well known, what it interesting is if this is applied on a bit level.
BPGEP will be a bit vector which will create an expression tree out of groups of bits, which in turn will be evaluated into possibly a third structure which will be evaluated for fitness. The relationship with biological genes will be discussed in a future post (its pretty cool). The third structure may be another bit vector, which may be longer or shorter than the first (depending on the problem). This means that we are then encoding knowledge about a bit vector and the relations between the bits. This has been a problem for GAs traditionally, as there effectiveness (in crossover particularly) is limited when the bits that are close in the individual are not closely tied in meaning, but the truly meaningful relations are hard to determine. You can do thing like inversion, but even so, a bit is limited in its ability to relate to other bits because it can only be next to so many at once. This is interesting especially in problems with high interrelations like cryptography, where each bit intentionally affects as many others as possible. This may make GEP ideal for breaking cryptographic methods, or at least more effective than GAs.
I really hope to investigate this, perhaps as part of my thesis on BPGEP.

3 comments:

  1. dude, I'm not getting this. So the cops knew that internal affairs was setting them up?

    ReplyDelete
  2. I should mention that the way an expression tree encodes knowledge about a bit vector is by viewing it as a set membership type problem. The operators are things like union, intersection, complement, and difference (remove), and the terminals are sets containing an index. The resulting set is the indices in the bit vector that should be set.

    ReplyDelete
  3. In other words, the cops did indeed know that internal affairs was setting them up.

    ReplyDelete