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.
No comments:
Post a Comment