Complex is just lots of Simple (Part 1)

~ Sean Nolan

This is part one of a two-part series; part two is here.

Our world feels increasingly magic — I can have normal adult conversations with a computer; feel very much “in person” with my far-flung family playing VR minigolf; and sit back comfortably while my car drives me to California. Every once in awhile, we stupid, fallible humans build incredible, beautiful things.

But “magic” is also dangerous. When you rely on something that you don’t understand, you’re an easy mark. This annoys me every time I have to call in an expert to work on the house because I don’t know how to test (just a random example, not something that happened last month, but if it did happen, the guy was totally cool, I just don’t like being in that position) the pressure switch assemblies in my HVAC system.

Of course, the world is way too complex for us all to understand everything. But the good news is, complex things are just lots of simple things put together — and often understanding the simple version is good enough. If you know a bit about how real and fake neurons work, you can develop a pretty solid intuition for what LLMs are and aren’t good at. If you build a treehouse, you’ll gain some appreciation for how real houses work. And, the point of this article, if you code up a really simple genetic algorithm, full-blown evolution seems a little less supernatural (but a lot more awesome).

Evolution & Genetic Algorithms

The only honest knock on Darwin is just basic incredulity. “Come on, do you really believe that all the complexity of the human mind and body just spontaneously popped up, by random chance?” Often these are perfectly intelligent folks that believe evolution can do little things, like maybe select for sharper teeth in wolves — they just can’t buy the admittedly huge leap to a modern human.

And I get it, I guess. But the history of our species is basically just a long parade of thinking that things are magic or supernatural, figuring out that they’re not, and levelling up the magic another click until we figure that out too. So why are we always sure that this time is the one? Seems unlikely.

Watching simple evolution in action helps me buy that real evolution is comfortably up to the task of shaping the world we live in. And it turns out that building a digital environment in which to do that isn’t all that hard. It’s also super-fun, so let’s give it a try.

Genetic algorithms use digital versions of evolutionary concepts like crossover, mutation and fitness to iteratively solve problems. There are tons of ways to put them together; I wanted to start from scratch and build things up one step at a time. If you’re so inclined, I hope you’ll build and run the code yourself — it’s all open source and up on Github.

I should mention up front that I have basically no formal background in this stuff — I played with GA’s a bit in college but that’s it. So we’re truly exploring together here; apologies in advance if I do or say something stupid.

2D Cellular Automata

Before we get into the “genetic” part of all this, we have to create the world our evolving organisms will inhabit. For reasons that will become clear later, two-dimensional cellular automata provide a lot of advantages, so we’ll use that.

These worlds are two-dimensional grids of squares, where each square is “on” (black, true, or alive) or “off” (white, false, or dead). As time passes, the squares change value based on their current value and those of their neighbors (the cells surrounding them) according to some set of rules.

The most famous set of 2DCA rules is called “The Game of Life” — a surprisingly simple configuration devised by John Conway that generates satisfyingly rich behaviors. Life considers the cell itself and each of its eight neighbors (N, NE, E, SE, S, SW, W, NW):

  • If the cell is alive and
    • has 2 or 3 live neighbors, it lives on to the next cycle,
    • otherwise it dies.
  • If the cell is dead and has exactly 3 neighbors,
    • it comes to life in the next cycle,
    • otherwise it stays dead.

The only tricky thing about this is what happens at the edges of the grid, where there are no “neighbors” on one side or the other. Typically implementations “wrap” the grid around itself so that, for example, the neighbor to the west of square (0,0) is (dx-1,0) where dx is the width of the grid.

Life rules generate some pretty neat patterns — shapes that blink or oscillate, others that move across the grid, some that stay static, etc. The animation below shows a few common patterns in action; follow through to the Wikipedia page for an interactive version you can play with.

OK, back to business. Life rules generate some visually cool stuff, but they’re only one example of the tons of possible rule sets we could apply. That’s the crux of what we’re going to do here — use evolutionary processes to discover rule sets that accomplish something we’re interested in. The general approach is this:

  1. Establish a goal state for the world (grid). A very simple example of this might be “All squares of the grid are black.”
  2. Create a bunch of organisms (rule sets) at random.
  3. Let each organism exist for awhile and then measure how close it is to the goal.
  4. Kill off the worst and mate the best to replenish the population.
  5. Repeat.

In this model, each “organism” inhabits its own “world” — there is no direct organism-to-organism competition for resources or space. Obviously this is a departure from natural evolution, in which organisms typically go head-to-head. But there is still performance-based competition for mates, so it works out.

We’ll see this again and again — there are infinite ways to tweak an evolutionary process. The real world is so wide, and so basically eternal, that nature just tries them all. We have to be a bit more judicious, but there are still a ton of different levers to pull.

Concepts and Code

Bitmaps, Edge Strategies and Neighborhoods

The Bitmap class is the workhorse of this whole system. Space and speed are important, and we do pretty well at both by cramming the bits into an array of longs. Also as we’ll see later, the array-of-longs approach helps with some other evolution-y stuff.

This class also defines the EdgeStrategy enum, which defines how the class should respond when asked about a coordinate that is off the grid. We use the “Wrap” strategy almost exclusively, but the alternatives might be useful in specific cases.

The Neighborhood class encapsulates approaches to identifying the relevant context for a particular square in the grid. The rules of “Life” which we saw earlier use a Moore Neighborhood, which is basically the 3×3 grid centered on each square. The Von Neumann Neighborhood is also common, which excludes the diagonal corners of Moore. There are others as well.

The neighborhood defines everything that a square “knows” about its environment at a given point in time, so it’s obviously super-important to the learning process. We’ll see this in action in part two of the series.

Organisms, rules and “DNA”

Unpacked, real DNA is basically a sequential chain of four nucleotide bases (A, C, G and T). In order to apply genetic algorithms to digital organisms, their digital DNA must also be representable by a chain of primitive building blocks.

Digital DNA must also be resilient to random mix-and-match operations during reproduction. A single mutation in an organism’s genes can be:

  1. Irrelevant. Much of our DNA is “non-coding” and a mutation within these regions may be pretty much unnoticeable (ok it’s a bit more complicated than this, but close enough).
  2. Advantageous. A mutation may make the organism more fit for its environment — maybe the shark’s teeth angle back a little more to hold onto prey.
  3. Disadvantageous. Perhaps it makes the organism unable to create a particular enzyme, like the lactase that helps us digest dairy products.
  4. Catastrophic. A mutation may render the organism completely unviable due to a structural problem that stops the DNA from functioning at all.

Evolution doesn’t work very well if #4 happens with any real frequency.

This is a major design challenge for GAs, but manageable for our particular problem. The NeighborhoodRulesProcessor class uses our array-of-longs Bitmap approach to create a sequence of bits that can be easily manipulated, perhaps to advantage or disadvantage, but without damaging their viability.

This next bit is a little hairy; bear with me. Or just skip to the next section, understanding that our rule sets are represented by a resilient array of long integers. Here goes. Neighborhoods are stored as arrays of relative coordinates: e.g., (0,0) is the target square itself, while (-1,0) represents one position to the West. Neighborhood Rules assign each of these relative coordinates to a bit in an integer. For a Neighborhood that looks at X squares, this results in 2x possible integers: 32 for Von Neumann, 512 for Moore.

The “outcome” for each of these integers is either “black” or “white”, which we represent using a one-dimensional bitmap indexed on the integer itself. The array of longs underlying this bitmap is our DNA, which is pretty cool. Any bit in the rule set can be altered and we will still have a viable outcome — maybe better or worse, but never catastrophic. Sweet.

Fitness

Once our population of organisms has run for awhile, we need to asses how “well” each one did, so we know who should die off and who should hook up.

This is the job of the Fitness class. The simplest type is MostOn, which simply counts the number of black squares and reports it as a fraction of the total. The best possible fitness score in this case is 1.0 — solid black.

Fitness can really be anything measurable — in part two we’ll look at vertical stripes, alternating black and white one-pixel wide vertical lines. We’ll also see how different ways of measuring Vertical Stripes fitness can make a huge difference.

Selection

The Reproduction class sorts the population by fitness and uses that ordering to decide which organisms should reproduce (the best two-thirds) and which should die off (the bottom third).

The reproducing population is paired up using a strategy defined in the PairingType enum. The default is “Prom,” which pairs the organisms ranked #1 with #2, #3 with #4, and so on. Random mixes this up so anyone can pair with anyone. There are other ways to do this too — March Madness-style bracket seeding, anyone? It also might be interesting to change the proportions and allow some or all of the winners to have multiple offspring.

Again, this isn’t exactly the way it happens in real life. But it’s close enough — and we get more levers to play with along the way.

Crossover and Mutation

The last bit we need to code up is the actual reproduction between two organisms — combining the DNA of each parent into a brand new, novel offspring. This happens in two steps:

  1. Crossover takes subsections of each parent’s DNA to create a new sequence by picking a random set of indices to be “swap” points. Bits are taken from parent #1 up to the first index, then we start taking bits from parent #2 until we hit the next one, we swap again, and so on. The number of crossovers is random but subject to a configured maximum.
  2. Mutation takes the new DNA strand and twiddles a few bits at random, again subject to a configured minimum and maximum rate of mutation.

The new organism takes the places of one that didn’t make the cut, and we start the whole process over again. If things go the way we hope, maximum and average fitness for the population goes up and up until we, seemingly by magic, have found our answer.

Putting it all together: Evolving a blackout

Our first run will be a 25-cycle evolution of 200 organisms trying to turn all squares in their environments black. Each cycle will run for 200 iterations over a 100×100 grid initialized with a random pattern. (Fun fact: it’s a very poor choice to start with an empty (all white) environment for this challenge — can you guess why?)

We’ll use the same Moore neighborhood as we did for Life. We’ll use Prom-style pairing, allow a maximum of 10 crossover points, and mutate at a rate between 2.5% and 7.5%. This mutation rate is way higher than in nature, and while it can create some chaos, it also introduces novel configurations more quickly, which can reduce the number of cycles required to progress.

TLDR: the results are here.

…and it’s pretty cool! Now to be clear, this is an easy task. The single rule “no matter what is in my neighborhood, turn me on” will accomplish it in a single iteration. But our organisms didn’t know that. They each started with a totally random set of rules, and all we did is measure how that random set did, pick the best and mix/mate them together, and try again. This graph shows the best, worst and average fitness scores over each of the 25 cycles; by cycle 17 we’d found rules that seem to work perfectly:

Another fun way to look at this progression is to look at the best-performing result at key points along the way:

The results page for this run has a lot more detail — be sure to check it out. You can see the outcomes for every organism at each cycle, which really hammers home the trend of getting better over time. Clicking on any block will show you the history of the organism that created it, including its parents. These can be quite surprising — for example, the overall winner was born from two parents that each performed just barely better than random.

We’ll see more of this next time, but you can also get a sense for the different strategies that can emerge. In cycle 18 for example, there are dots and lines and blobs and all sorts of mechanisms at work.

Success is Usually Messy

The last thing I’ll call out from the blackout run is that evolutionary success is rarely what you’d expect. I pointed out above that you can achieve a blackout in one iteration with a single rule — but that’s not what our evolution produced.

Moore neighborhoods generate 512 individual rules, and that’s just hard to look at. So I ran the blackout evolution again using a Von Neumann neighborhood of 32 rules. Results for that run are here — similar except in this case we got really lucky and one organism hit perfect fitness on the very first run.

Anyway, the rules for the winning organism in this run look like this; the top section are rules that turn their cell white, and the bottom turn their cell black:

This is a super-effective rule; the organism ran for five cycles and was perfect every time. Looking at the rules visually, a few things pop out:

  • There are significantly more black rules than white.
  • Only four rules (highlighted in red) make the grid “whiter” — all others are either neutral or black.
  • Progress reinforces progress — ignoring the center value, all of the rules with three or more black inputs have a black outcome.

Run over 200 iterations, these rules are basically guaranteed to get us to a blackout. But it sure is a roundabout trip compared to the “optimal” rule (I’ve put an animation of our winning rule going through just 12 iterations at the end of the article). However, it’s important to understand that, given our fitness rules and environment, our evolved rule is exactly as good as that “optimal” one. As long as the blackout was attained by iteration #200, it did the job perfectly. Nothing about our world indicated that speed mattered — only the final outcome.

OK, that’s enough for this session. We’ve done a lot — learned about 2D Cellular Automata, wrote code that lets us mimic evolution in digital form, and even saw the first glimmers of some pretty cool outcomes. Next time I’ll get deeper into the weeds so we can really see how this machine ticks. There are just unlimited cool things in the world.