Strutured Populations

One GA technique that has not been applied to GEPs yet, as far as I am aware, is the idea of a structure population. In GA literature these are call cGA or cellular genetic algorithms. The idea is very nice and seems natural, appears to perform well, and has some good work done in studying the effects of different topologies. One of my professors is even doing something with a structure that is very cool, and I may post about when he publishes his paper on it.

The most obvious thing to do would be to just check if cGEPs are better performing then GEPs, but it would also be interesting to find some interesting shape or strategy to contribute to the research, as well as extend it to GEP at the same time.

There are so many cool things to do with GEPs! A young method and a small community has its advantages sometimes.

Fitness Functions For Long Distance Relationships

One fitness function that ties distant indices is the sum of the xor (or the complement of the xor) of the index's value and the value of the index that is its inverse mod p in the field mod p where p is prime (p is also the number of bits in the vector btw). Hopefully some indices will have inverses that are close to themselves and some that are distant. If I include 0 it will trivially be its own inverse.
The cool thing about this is that the indices are tied to each other in a predictable way that is well known. This way someone (possibly me) could conduct an experiment to see if this property of GEP that I've talked about in other posts is true (its ability to encode knowledge about distantly related bits in a bit vector). Obviously it can do some encoding of knowledge, but I've come across this one a couple of times in papers and I think that GEP may have some luck with it.
I could possibly prove something about GEP this way. I have an interest in formalizing GEP and studying its dynamics, and if nothing else that would be a really cool paper. More likely it will be just one small part of my masters thesis if I include it (because it is related to the types of problems I think BPGEP can solve well), maybe as part of the justification.

Encoding Knowledge

I suspect that there is real power in the ability of GEP to encode knowledge as a tree, which allows the expression of relationships in tree form.
I'm thinking of a GEP with union (and maybe 'not') as the functions and indices as the terminals. The expression tree evaluates to a set of indices to be set as 1 in a bit vector. The final bit vectors is evaluated for fitness. The cool thing about such a setup is that it creates the object most GAs are concerned with (a bit vector), yet it encodes this as a string.
It is well known that related loci should be close to each other so good configurations will not be disrupted by crossover easily. With GAs we have the problem that we don't know the relationship, so we don't know the best order of bits, and even with inversion trying to evolve a good ordering (not that many people use inversion) a bit can only be related to a small number of other bits because it can only be next to 2, and near a small number.
The power of the expression tree is that it it not limited to the relations it can express this way (or it is not as restricted). I would like to know if the relationships can be used to improve performance, and I think I have the perfect problem to test this out..
Next post I guess.

MGEP

So, I finally understand monads, both mathematically (though I'm not so strong on category theory) and as a language construct. Enlightenment finally came while reading the article
http://blog.sigfpe.com/2006/08/you-could-have-invented-monads-and.html

In my normal fashion, I wanted to link what I had just learned to some project or immediate use. What occurred to me was that there is that the concept may be helpful in certain GEP problems. In particular problems that do not exhibit the normal closure property. This would allow a wider range of problems to be solved by GEP. I'm yet to think of a situation in which this would be helpful, but it opens up a world of possibilities for operators as functions with a different return type and params.
Monadic Gene Expression Programming!

Inversion Only

I presented by capstone project on the application of GEP to combinatorial optimization problems today. It went well, and some people may have even understood what I was saying (understandably very few though). One professor that I like a great deal told me that it was my responsibility to present my findings in a paper so the GEP community is aware of the problems I found, the changes I made, and my conclusions about the future applications of this method.
While I would like to do this, I'm not really sure how this would work. I would have to complete the statistical analysis so I could make a strong claim, and do some more analysis of these problems.
I would certainly like to have some papers to my name, but I'm not sure anyone is really interested. It looks to me like I'm the only person thats ever taken this modification of GEP seriously. In fact, I've never heard of anyone using anything but the original and new variations of it, never any of the variations mentioned in the original book.

I guess I'll just see how this plays out.

Satisfiability is Hard

I'm been looking into applying PGEP to SAT problems (3-SAT in particular) but my results so far are not good at all. Most individuals end up encoding for only one variable or none to be true, and yet the problem ends up satisfying almost every single clause. The unsatisfied ones are hard to correct for, even with SAW. I think this is because the subexpressions that should be combined to make individuals that satisfy all clauses aren't being created, as the important genetic material (the stuff that is involved in fitness) is just one terminal in the beginning of the chromosome. I'm not sure how to get more complex trees and richer structures out of the population.
It is possible that the easiness of the problem is encouraging individuals that aren't complex, but I'm seeing a similar problem in what should be a much more difficult problem.
Looks like its back to the SATLIB site to find something difficult to see if I can get some real diversity of structure going.

Evolutionary Dynamics

Ferriera has shown that the dynamics of GEP are different from that of a GA in her book, Gene Expression Programming- Mathematical Modeling by an Artificial Intelligence. The best fitness predictably is pretty consistent (as elitism is in use) but the average fitness skips around quite a lot. It is pretty clear that this is because the operators defined by Ferreira are very disruptive, so that the algorithm explores more then exploits. It can produce huge variations in a single mutation, if the structure of the tree is changed enough. This is fine in a way- elitism ensures we have at least a pretty good solution, and selection will ensure it has a good presence in the population, and most of the operators will search a wide area of the solution space around this individual.
The problem is that there are so many operators, and they are so disruptive that we end up with little more than a random search (at worst). The problems that the technique is applied to in the book are mostly fairly simple, and I wonder if the randomness of the search is just ensuring that good solutions are found because of the smallish size of the solution space. For much larger solution spaces, that randomness may result in a lot of wasted effort (exploring when we should be exploiting what we know is good).
Other operators have simplified GEP since it was created (rotation and point mutation as the only mutations, and single and double cross as the only crosses) and PGEP seems to be better able to keep a subexpressions structure even after small changes to the individual. I'm wondering if the population dynamics have changed when applying this operations and variations of GEP. If I learn anything about this in the remaining part of my capstone I'll definitely post it here.