SAW

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.