As I will be applying GEP (really PGEP) to the 3-SAT problem, I have had to look into fitness evaluation for satisfiability problems. The SAW method seems very common, and the only other method that I can think of is co-evolution, which would be pretty cool but unnecessarily complicated. Instead I will implement a very simple version of the stepwise adaptation of weights.
This method is really pretty trivial as far as I can tell. All you have to do it keep a vector of the weight for each clause in the boolean expression, starting each weight at 1, and for each n generations (n=5 in the literature that I found), modify the weights. The modification process involves taking the best individual and applying the formula wi = wi + abs(fi(x) - gi(x)) where fi is the value of the best individual at clause i, and gi is the weight at position i, which updates the value of the ith weight. This means that if the best individual can't solve that clause, we will get wi + abs(0-1), which will increase the value of solving that clause by one.
This means that the more difficultly the best individual has with a clause the more likely an individual that does solve that clause will propagate. Hopefully this individual will cross with the best and produce an individual that solves all the ones the best does as well as that one the best was having problems with.
One interesting thing that happens here is that after the best has gained the ability to solve that clause, its weight doesn't just go down to 0, but gradually decreases. This means that the population may have time to converge on being able to solve that clause before it stops asserting noticeable selection pressure. Thats pretty cool.
I think this method may even be especially good with GEP as elitism ensure that we do not lose good individuals, so there is some additional emphasis on this best individual, with lots of disruptive mutations and so on exploring the area around it.
Sunday, March 28, 2010
Tuesday, March 23, 2010
SAT Fitness Function
Given a solution to a satisfiability problem, we can easily check whether or not it evaluates to true by evaluating the boolean expression with the values for the variables from the solution. But how do we determine how close a partial solution was to evaluating to true? I've read of a method called SAW, but I haven't found the original paper yet, so I don't know exactly how it can be used to come up with fitness, but I will probably end up using it for my capstone as it seems to be used in other research on evolutionary computing and SAT problems.
The other way to do this is of course to evolve weights for each clause through co-evolution. I imagine that a regular GA evolving weights that emphasis those clauses that are satisfied by the fewest individuals would be a reasonable way to determine fitness. There have been some nice results in the literature of co-evolution increasing the efficiency of GAs (measured by the quality of the solutions, not the amount of time taken to run the algorithm.
The main problem with this is that there seems to be a simpler method out there (SAW) and it may be difficult to set up the experiment correctly with my framework. I will probably at least try to do it just for fun, as it will be a good test of the framework to see how well it supports a different way of doing this from the regular individual in, fitness out sort of evaluation.
The other way to do this is of course to evolve weights for each clause through co-evolution. I imagine that a regular GA evolving weights that emphasis those clauses that are satisfied by the fewest individuals would be a reasonable way to determine fitness. There have been some nice results in the literature of co-evolution increasing the efficiency of GAs (measured by the quality of the solutions, not the amount of time taken to run the algorithm.
The main problem with this is that there seems to be a simpler method out there (SAW) and it may be difficult to set up the experiment correctly with my framework. I will probably at least try to do it just for fun, as it will be a good test of the framework to see how well it supports a different way of doing this from the regular individual in, fitness out sort of evaluation.
Dealing with Invalid Individuals
My adviser suggested a nice clean way to deal with invalid symbols, such as in BGEP, and with invalid chromosomes, such as in GEP or PGEP where we do not specify a head and tail.
He suggested that a new element be added to the terminal set, and any bit string that does not map to a symbol or any operators that causes an individual to be invalid be interpreted as this terminal. In the case of set members, this would be a set containing some new element. After evaluating to the set that the expression tree represents, we would simply remove this element.
This avoids favoring some terminals or operators more then others. In some cases it may be easy to identify some identity terminal, but for my purposes this works very nicely.
I am about to add this idea to my GEP framework, and to make it easy to add new experiments with GEP or PGEP with as little new code as possible.
He suggested that a new element be added to the terminal set, and any bit string that does not map to a symbol or any operators that causes an individual to be invalid be interpreted as this terminal. In the case of set members, this would be a set containing some new element. After evaluating to the set that the expression tree represents, we would simply remove this element.
This avoids favoring some terminals or operators more then others. In some cases it may be easy to identify some identity terminal, but for my purposes this works very nicely.
I am about to add this idea to my GEP framework, and to make it easy to add new experiments with GEP or PGEP with as little new code as possible.
Saturday, March 20, 2010
Head/Tail and Ignoring Problems
I have just read though the paper "Gene Expression Programming and Rule Induction
for Domain Knowledge Discovery and Management" and found out that the method for using the whole gene that is used in PGEP is really just not allowing invalid chromosomes to exist. How exactly this happens is not laid out clearly in the paper, but I think that he just disallows operations that detect that they will create invalid individuals (or throws out individuals that are problematic).
I think we can do better then that. For one thing, invalid individuals goes against the spirit of the original GEP paper, which makes a point of how no time is wasted on checking validity of genes. I think that there are several ways to keep this nice property.
1. I would be easy to identify which operators at the end of the gene are causing problems, and these could simply be ignored in fitness evaluation.
2. In BGEP, with its binary representation, the first bit of a symbol determines whether it is a operator or terminal. This means we could just flip a couple of bits in the operators that were causing problems, and end up with a gene that has the same genetic material but is valid.
There may even be other ways to do this. I can't think of any right now, and I don't think there is too much need for any thing else, as these two are fairly good and clean.
I plan on developing a variation of GEP as a research project this summer, so this will definitely be covered, along with solutions to other problems in BGEP and GEP in general.
for Domain Knowledge Discovery and Management" and found out that the method for using the whole gene that is used in PGEP is really just not allowing invalid chromosomes to exist. How exactly this happens is not laid out clearly in the paper, but I think that he just disallows operations that detect that they will create invalid individuals (or throws out individuals that are problematic).
I think we can do better then that. For one thing, invalid individuals goes against the spirit of the original GEP paper, which makes a point of how no time is wasted on checking validity of genes. I think that there are several ways to keep this nice property.
1. I would be easy to identify which operators at the end of the gene are causing problems, and these could simply be ignored in fitness evaluation.
2. In BGEP, with its binary representation, the first bit of a symbol determines whether it is a operator or terminal. This means we could just flip a couple of bits in the operators that were causing problems, and end up with a gene that has the same genetic material but is valid.
There may even be other ways to do this. I can't think of any right now, and I don't think there is too much need for any thing else, as these two are fairly good and clean.
I plan on developing a variation of GEP as a research project this summer, so this will definitely be covered, along with solutions to other problems in BGEP and GEP in general.
Sunday, March 7, 2010
Messyness
How does one evaluate partial solutions? The original method involves finding a solution by hill climbing such that the solution cannot be improved by any single bit change. Then partial solutions are found (the idea is that each solution is a schema) and these solutions are overlayed on the hill climbed solution. A fit solution fill be able to improve the fitness of the hill climbed solution.
The problem that I have with this is that it focuses the algorithm on the solution found while hill climbing. There is no way to know how good the neighborhood around the solution is, and partial solutions that would be good in one run could be bad in another (and vice versa) if the solution they are compared against is different. One way to fix this could be to use many hill climbed solutions or a GA with high niching penalties. The solutions to the GA could even be hill climbed to ensure the "no single change improves fitness" condition. Then the partial solutions fitness could be based on their ability to improve any solution, meaning they would search the area around many local optima. The problem of course is increased processing time (the entire other GA run for example) and the difficulty of what is essentially a multi-objective problem (the solutions can't be reasonably compared). This means that the algorithm could spend a lot of time search local optima that are easy to improve, not ones that produce good results. It is possible that this could be adjusted for, but we are going into messy ground here, and I'm not convinced that this will lead anywhere.
In another post I will go into how partial solutions could be evaluated in a Messy GEP (which doesn't exist as far as I know. I'm planning to look into that as a masters thesis).
The problem that I have with this is that it focuses the algorithm on the solution found while hill climbing. There is no way to know how good the neighborhood around the solution is, and partial solutions that would be good in one run could be bad in another (and vice versa) if the solution they are compared against is different. One way to fix this could be to use many hill climbed solutions or a GA with high niching penalties. The solutions to the GA could even be hill climbed to ensure the "no single change improves fitness" condition. Then the partial solutions fitness could be based on their ability to improve any solution, meaning they would search the area around many local optima. The problem of course is increased processing time (the entire other GA run for example) and the difficulty of what is essentially a multi-objective problem (the solutions can't be reasonably compared). This means that the algorithm could spend a lot of time search local optima that are easy to improve, not ones that produce good results. It is possible that this could be adjusted for, but we are going into messy ground here, and I'm not convinced that this will lead anywhere.
In another post I will go into how partial solutions could be evaluated in a Messy GEP (which doesn't exist as far as I know. I'm planning to look into that as a masters thesis).
Subscribe to:
Posts (Atom)