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).