The Essence of Evolutionary Algorithms

I've been thinking about the essence of evolutionary algorithms, trying to get the right structure for my framework- general enough to use in any project I want to do, but easy to set up and apply to common problems.
The structures involved seem to be- a population of individuals that are strings of symbols that gets exposed to an environment. The individuals learn from their exposure, a set of terminating conditions are checked, and if none are met, start from step 1.
This would looks really nice as haskell code (or really any functional language, I just happen to like haskell right now) , but I'm not familiar enough with it to write a framework that I will be using for a project that starts pretty soon.
Therefore, I will just hope to redo it all in haskell one day, and for now consider building the functional abstractions that I want to use into Java. This would be an interesting learning experience, and may end up improving the architecture of the program a lot.
On the other hand, I will almost certainly end up with only some of the cool stuff built into a functional language, the program will be verbose and incomplete, and may end up getting thrown out. I'm okay with that, cause if it works well enough for now, maybe I can get it right later, and if nothing else it will motivate me to deepen my understanding of certain aspects of functional languages. I will basically be making a little language in Java, and nothing teaches you a concept like having to implement it, and getting it to work correctly.

Modeling Substructures

The number of substructures in a tree is always <= the number of schema of its linear representation. In all but the most trivial case, it is much less.
This is interesting because since the original schema theory doesn't make so much sense for GEP, it also appears that GEP is sampling fewer schema. This is exacerbated by the fact that a substructure that appears in two forms or in different places could be considered the same structure (because we do not could the context of the structure as being part of it, only the structure itself).

There are a couple of things to note here though. One is that we are not searching the normal solution space, but rather the space of strings whose trees map to the space, so there are a lot of complications in relating the spaces directly and saying that we are searching one more or less efficiently than a GA might.

Also, the idea behind substructures is to sample them in different places and hope their effects are overall positive. In other words, while there are fewer of them, they can each have many effects in both their part of the tree and (if they are "open") the trees that complete them.

Overall they are really very different from the schemata of GAs. They have only the properties inherent in the idea of classifying parts of a string. They have different dynamics, meaning, and structure. They share other things, like the ideas of defining length, but I'm not sure if they should share notation or not- as I would like to be able to capture the actual vs smallest size of a substructure somehow.
An example of that btw is +-##1 could also be +1-## with no change in the resulting value. Are these the same? They have the same meaning (since + is commutative), but different defining lengths. And really the # could be of any size, and still match the 1 with the plus, like
+-####1 could be +-*23451. Maybe the # denote any subtree? This complicates the defining length, but would mean that I would probably define structures that look different as different, just so I could give them a length of some sort without resorting to a vague "minimal length when completed with minimal subtrees" or something.

All of this reminds me of my idea to introduce a "defining length reduction" operator. I'm still not sure if there is such a thing, but it might help, and hopefully one day we will have a model that would predict the effect of such a thing.

Schema Theory for GEP

I would love one day to come up with a satisfactory model for GEP that captured possibilities, its distinction between geno and pheno types, and the sampling of incomplete (I think of them as being "open") substructures or subtrees within an expression tree. I want it to be aware of the impossibility of saying how good a sequence of symbols is and rather to capture the essence of the structures along with their actual representation. It would have to include the idea that there are many possible linear sequences with the same evaluated meaning, the same structure, different defining lengths (which I'm borrowing from schema theory) and all sort of other things.

I'll post some haskell code related to this soon.

Preservation of Substructures

I've convinced myself that one of the most important parts of GEP is the ability to encode knowledge about a problem domain in the form of a tree. While knowledge can be potentially encoded in many ways, and trees may be unable to encode some forms of knowledge (potentially limiting the ability of GEP to solve problems when there is no mapping (or maybe no easy or convenient mapping) between the solution space and a space of expressions encoded in trees), they are very nice for many things and have a nice notation (such as prefix or karva) that allow the whole genotype->phenotype thing that is also one of the most important parts of GEP.

I've been thinking of the different types of things one can do with trees and the ways trees can evaluate to solutions to different combinatorial optimization problems, and I've realized that I would like to be able to improve the ability of GEP to preserve structures (that is to say, subtrees). PGEP does this already, but I'm sure there are some other things we can do, such as saving useful substructures and making them terminal (which has already been done (Direct Evolution of Hierarchical Solutions with Self-Emergent Substructures by Xin Li)), or some other mechanism.

At the moment, I can't think of any new or interesting mechanism to try out, but I think there are a couple of forms that such a mechanism might take:
1. A new structure (like PGEP) that tends towards preserving subtrees in the presence of small disruptions to the linear structure of the gene.
2. A new operator that reorganizes the gene or otherwise tends to help substructures survive. I've been trying to think of a reorganizing operator for a while that would transform trees (especially ones made of commutative operators) into ones whose linear representation has the minimal overall length of substructures. I may have to talk about this more in another post.
Another example is Xin Li's (et all) operator that makes successful subtrees into new terminals.
3. A change to current operators to make them more aware of the structure of the genes. I plan to introduce a rotational mutation in BPGEP that does this sort of thing.

I may have more to say about making subtrees into terminals later, as the increased size of the terminal set may be offset by BGEP, making that a particularly effective strategy in BPGEP.

Architecture Of Programs

I have been thinking a lot about the structure of the framework I'm writing to do my GEP experiments in. Its gone through several iterations so far, and what I've found is that the most important thing for me to do is find the right abstraction with which to explain what is going on, so that the rest of the program flows logically out of that one source of authority.

My most recent idea is to have a population of individuals, which knows its own structure in case I want to do cellular algorithms at some point, and an environment. Execution involves repeatedly exposing the individuals to the environment, which may modify either participants, until the terminating condition is met. I decided that this is really the essence of AI in a way (learning from exposure to an enviroment) and that a program should be written to mirror the way the idea would be explained to a novice in the field.

Hopefully this will turn out to make any sense and my framework will be more logically consistent and easier to use because of it.