Spatial Competitive Evolution

Okay, time to post some (semi-)tangible stuff.  The philosophical discussions have their place, sure... but that is mostly based on opinions and biases from past experiences.  Experience and empirical observation is, in my opinion, what this blog should be all about. (There I go again with philosophy... sorry, dear reader.) 

Ok, I am going to assume that you are familiar with Evolutionary Algorithms (EAs).  If not, where have you been? :-) No worries, have a look at http://en.wikipedia.org/wiki/Evolutionary_algorithm.

Some of the problems that I currently experience with the run-of-the-mill EA includes the following:

1. The populations are simply too small.  Evolution does not work effectively with anything under a 1,000 individuals. The biological metaphor on which EAs are based, operates on hundreds of thousands or even millions of individuals.  Small populations tend to cause a dramatic drop in diversity with a high occurrence of genetic drift.  Representing a large population (say, 100k+) tends to be too expensive in terms of processor and memory requirements and problems which do allow large populations are typically simple, trivial problems.
2. Selection tends to operate on the entire population space.  Again, this is unnatural and tends to produce algorithms with a higher selective pressure.  Do you really date someone from Japan, Jamaica and Portugal at the same time? ...and if you do, how do address the language barrier? 
3. Most fitness functions are one-dimensional in nature.  Several characteristics are measured on a like-for-like basis (very similar to the zero-sum games of classical AI.)  What I mean by this is that a feature is identified (by the creator!) and individuals are measured in exactly the same way against that feature.  The evaluation is therefore rigid and static - and limited by some predefined bias.  This, in my opinion, is the true ball-and-chain of classical EAs. This often result in an "unfit" individual, with a small, yet break-through component in its genetic make-up (the super-genius in the wheel-chair) to become extinct.  Furthermore, a high selective pressure coupled with this, short-sighted fitness function really tends towards a hill-climbing rather than true evolution.

I am fully aware that many people with disagree with me on many of these points.  Thank you, you're more than welcome (please share why)... I am currently experimenting with a new idea (I think) that I call "SCE" or "Spatial Competitive Evolution", which tries to address these issues to some extent.  It has not been as successful (yet!) as I hoped, but I am continuing fiddling with it.  Here's the main ideas:

1. The algorithm operates on a 2d grid (for now), where each cell represents an individual. Individuals can only reproduce and compete with its eight neighbouring cells (extending this beyond is of course also possible). This increases diversity remarkably well and take-over time takes much longer.  Unfortunately, genetic drift still occurs and larger populations are still required.  This is very similar to the "lbest" algorithm of Particle Swarm Optimisation.
2. The fitness function is relative-based (that is, in competition with its neighbours).  The function varies in that only a specific evaluation region of the fitness function is applied during evaluation.  The fitness function itself evolves with the individual and has the ability to include all evaluation regions.  This allows different sub-sets of the population to excel at different aspects then elsewhere on the grid.  Eventually take-over will occur and the fitness function will evaluate all regions.  This is true evolution, where the environment change (the lion runs faster) and you have to adapt (as the gazelle, you better learn some camouflage... and if the trees disappear? ...well then you better learn to run faster!).
3. Except for the fitness function and population representation, the standard EA is followed with standard mutation and cross-over functions.  Some changes come into play with the 2D grid, but these are rather intuitive.

Results... well... not that well at this point.  I've used the algorithm to evolve pieces of text that resembles a predefined line of text (text-writing Shakespearean monkeys comes to mind).  The fitness function starts off by evaluating a single letter and this then expands over time with the individual.  It takes significantly longer to find the final solution (compared to a vanilla GA), but it does eventually get there...

I often keep things like this secret... but I realise that sharing it on this blog will help in determining if this approach has any merit (especially with all these smart people on this blog!).  I will submit what I have on Github soon (and details to follow on this blog).  You're welcome to clone the repository, play with it and let us know if you find a working set of parameters.