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.
Sunday, May 16, 2010
Saturday, May 15, 2010
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.
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.
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.
Subscribe to:
Posts (Atom)