Messy GA Time?

After reading about messy GAs and how they can be applied to combinatorial optimization problems, I think something like this may help GEPs. Since my capstone project deals specifically with combinatorial optimization, this could be something to investigate.
The idea of messyness in genetic algorithms is (briefly) that small solutions can be combined to make complete solutions. The small solutions will, hopefully, represent building blocks (as per the building block hypothesis) and the full solution found at the end will be composed of all these great little blocks. This is especially cool as the blocks are made in order to cover any schema, so they are represented not as a group of contiguous loci, but as a list of locus positions and their values. This allows the blocks to fall in any schema possible, while the unspecified positions are seen as # (the unspecified character).
This of course requires some way to evaluate partial solutions. This is particularity difficult because of non-linear interactions between parts of a chromosome. The only reasonable method that I am aware of is to apply the partial solutions to some known solution that can be found through hill climbing, for example. If the partial solution "overlayed" on the given solution creates a better solution then the original, that it may be a good schema to keep in the population. This relies on another problem solving method, and I suspect it reduces the ability of the messy GA to search the full problem space, as only schemas that improve the local optima are considered fit, and not ones that move the solution towards another (possibly better) optima.

Next post I will explain how this can be extended and possibly applied to GEPs, and why we might want apply it in the first place.