I recently read a cool paper from GECCO 2012 called “Spatial Co-Evolution: Quicker, Fitter and Less Bloated”  by Robin Harper. This paper explores some benefits of the Spatial Co-evolution in Age-Layered Planes (SCALP) algorithm, originally described by Harper in a previous paper (paywall) . In SCALP, the population lives in a three-dimensional grid of cells. Each cell is inhabited by both a solver (the “host”) and a test case (the “parasite”). Solvers try to find the right answer for each test case that is either next to or below them. They gain fitness by more closely approximating the desired answer. Test cases, on the other hand, gain fitness by being hard to get right – fitter test cases are those for which solvers have higher error.
That explains the “spatial co-evolution” part of the algorithm, but what about the age-layered planes? That’s what the z-axis in the three-dimensional grid controls. Just like in Hornby’s ALPS algorithm , the age of the lineage controls which XY plane a given solver or test case lives on. As lineages get older, their members move up. The bottom layer is periodically randomly restarted. This ensures that diversity keeps getting added to the population, and that new solutions aren’t immediately wiped out by well established ones.
So why do I think this paper is particularly cool? SCALP turns out to be great at avoiding code bloat, which tends to be a big problem in genetic programming. It even outperforms Operator Equalization, a very popular technique for reducing bloat. Perhaps as a result, SCALP achieves higher fitness than any of the algorithms it was compared to.
But then things get stranger and more interesting. On the more complex of the test problems used in the paper, SCALP achieves the worst fitness on the training data set of the three algorithms tested. But on the test data set, it achieves the best. Somehow, SCALP is avoiding overfitting. This seems to have something to do with the rapidly cycling host-parasite dynamics. Once a test case has been in a given area for a while, the nearby solvers are likely to have gotten good at solving it. This makes it easy for other test cases to invade. As a result, solvers in SCALP are in a quickly changing environment, never seeing all of the test data at once.
These dynamics may avoid bloat by creating a selection pressure for more evolvable solvers. Bloat is thought to reduce evolvability by making genotypes unwieldy and hard to quickly adjust. Perhaps this pressure also forces some amount of generalization to occur – the successful solvers are those that don’t account for a bunch of special cases that are in reality just noise in the data. On the downside, as Harper points out, this suggests that SCALP may be unable to fit data as precisely as the other two algorithms tested. After all, if the training set and the test set had been identical it would clearly have under-performed.
Nevertheless, SCALP definitely exhibits some fascinating evolutionary dynamics and I will be curious to see future results.