Thursday, September 16, 2010

Messy GEP Again

I'm back at the possibility of a Messy Binary Prefix Gene Expression Programming. The idea is to have small individuals that encode small, partial solutions to a problem. Then we save some of the subtrees of these solutions and add them as terminals (or more generally as operators with some number of "holes" in them if the subtrees are allows to be partial (partial=not all leaves are terminals)). These never terminals are available to be added by mutation and will enter into the population. Every so often (every n generations for example) this extraction of substructures would take place, potentially replacing some previously extracted substructures (or maybe even regular terminals!). The individuals would get more and more complex as they combined and recombined substructures into increasingly complex expression trees.

While it would be nice to include an "expansion" operator like that in the paper on self-emergence of substructures in PGEP, I'm not sure that I would add it. In real genetics, very complex creatures have a lot of parts of their DNA that do not change very much at all, and small changes often prove fatal when they occur. What I want is the emergence of complexity out of simple trees.

We would almost certainly have to bound the length of these extracted trees, or somehow ensure that they don't just grow to arbitrary length.

I'm not sure I'll ever actually do this research, but it seems like a neat little idea- modeling the increase in complexity of individuals through time to find very large and complex solutions to problems.

1 comment:

  1. I should mention that while I've posted about this before, the idea of a substructure library (here just the terminal set) makes this method very reasonable. Small partial solutions can have well defined fitness' and be easy to add complexity to (by allowing the extracted substructures to occur as part of mutation).

    ReplyDelete