Self-Evolving Cellular Automata

We start with a grid of cells, which are updated in steps.

All cells are computed in parallel, but let's look at the progression from the perspective of a single cell, which we'll call the focal cell for clarity. Each cell interacts with its 8 immediate neighbors, forming a group of 9. We'll index the cells according to the image to the left.

At each step $t$ for the focal cell (index 1) we have two important variables: a non-negative energy scalar $E_1^{(t)}\in\mathbb{R}_+$ and a transfer matrix $\mathbf{W}_1^{(t)}\in\mathbb{R}^{9\times 9}.$

The transfer matrix $\mathbf{W}_1^{(t)}$ defines how energy spreads from the cell to its neighborhood. To calculate the spread, the 9 values of all adjacent cells are stacked into a vector $\mathbf{e}^{(t)}$, where each entry corresponds to one neighborhood position $k.$ The relative spread from the focal cell to all 9 cells in the neighborhood is then calculated according to:

We add a very small epsilon to account for situations where the spread would be all zeros - the spread will then be uniform instead. In this first step, we leave the spread like this, noting that the transfer matrix would need to be constrained to positive values, $W_1^{(t)}\in\mathbb{R}_+$, to avoid "negative spread of energy".

To compute how the energy is redistributed from the focal cell to the neighborhood while the total energy remains constant, we turn the spread $\tilde{\mathbf{s}}_1^{(t)}$ into a probability-like proportion vector $\mathbf{p}^{(t)}$ by normalizing it, and then we multiply by $E_1^{(t)}$ to obtain the neighborhood energy vector at the next time step $\mathbf{e}^{(t+1)}$:

When this is done in parallel for all cells in the grid, taking into account things like energy not spreading into certain cells (e.g. walls), we then sum all of these together to get the energy in the whole grid for the next time step.

When energy flows from one cell to another, we also assume that the mechanism of that cell flows with it. For the next time step, the transfer matrix is thus also updated. Let's also consider that from the perspective of the focal cell.

The transfer matrix update is proportional to the energy flow: if no energy were flowing to the focal cell from any other cell except the focal cell itself, the transfer matrix would not change. But since energy will also be flowing in from other cells in varying amounts, we weight all of the neighboring transfer matrices relative to the energy flow as follows:

We square the energy when weighting, which puts a lot of weight on directions with higher energy flow (note: you do get interesting results also with other powers than 2 here). We again add a small epsilon to account for situations where the energy might be zero.

So, the one thing remaining before we can take our first steps is to figure out how we initialize $E$ and $\mathbf{W}$. Let's initialize $\mathbf{W}$ at random with positive values and put a chunk of energy in the middle.

Even though we initialized the weights with random values, when the energy starts flowing and the weights affect each other, the simulation very quickly stabilizes into a kind of numerical diffusion model. As one might expect with diffusion, over time, it leads to the energy being evenly spread throughout the container.

It's perhaps not that surprising that the previous simulation quickly started converging towards a stable solution. We basically had a completely sealed container where we introduce a bunch of energy and allow it to spread out with no constraints or outside influences whatsoever.

Again, let's look at this from the perspective of a single cell, the focal cell.

In the previous step, the mechanism was defined by energy flow; the mechanisms flow with energy. But what if the cell has no energy at all?

If the cell had no energy, it would make sense to define the mechanism as random. But the more energy a cell has, the more the mechanisms will be carried by that energy, and the less this randomness would be.

I'm sure there are other ways to define this, but I chose to define it as follows:

It might look a bit complex, but we are essentially just adding randomness whose strength decreases as the energy of the cell increases.

Here $\tilde{\mathbf{W}}_1^{(t+1)}$ is the weighted-average transfer matrix from the previous step (computed from incoming energy flows into the focal cell). We then form the next transfer matrix $\mathbf{W}_1^{(t+1)}$ by blending it with random noise. $\beta$ sets the overall noise scale, $\boldsymbol{\xi}$ is an elementwise standard normal noise matrix.

So, let's add some randomness to see what it looks like:

The result resembles boiling. Interestingly, it also leads to the energy piling up at the corners over time.

This is where nonlinear effects start to dominate.

We're still looking at things from the perspective of a single cell (the focal cell).

Let's introduce a new vector, $\mathbf{b}$, in addition to the transfer matrix $\mathbf{W}$. You could pretty much say it is part of the transfer matrix, since we'll make it behave identically in many ways: it will flow with the energy, it will be weighted and updated in the same way. This turns the transformation into an affine transformation.

Note that in the previous step the transfer matrix was assumed to stay positive. Here it's actually important that we remove that constraint and allow it to change freely.

We feed the transformation through an arbitrary nonlinear function $f.$:

This may look familiar if you've seen neural-network style transformations. This part is heavily inspired by neural networks. I've tried a bunch of different nonlinearities (activation functions) here. I got the best results by omitting all negative values (rectified linearity) or feeding it through a step-function (positive values giving the value 1, and other values giving the value 0). Here, we use rectified linearity:

Let's try out the same thing with our nonlinear transformations:

In practice, this produces "mechanisms" that appear as the energy spreads. If you reset the simulation a few times, you'll notice different structures forming now and then, sometimes resembling small organisms moving around the grid.

I made a few additional changes that introduce a wider range of behaviors.

• I tried adding a little bit of energy everywhere at each time step
• The energy is also slowly dissipated, to avoid too much energy building up
• The randomness is applied locally, not uniformly in the simulation

The slider controls where the randomness is applied. You'll notice that new mechanisms primarily form where randomness is introduced, and quickly spread out to the area where there is no randomness.

When the mechanisms spread, they automatically start "competing" with each other, since the mechanisms that effectively gather the most energy to occupy the cells will remain and replace the ones that are less effective. Every now and then, these mechanisms can be quite complex. This is less apparent in this small simulation than in the complete Python one.

Hosted on GitHub is a repository with the Python script I used to test the ideas outlined on this page, along with a bunch of additional stuff as well. You get a lot more complexity by running this with multiple parallel channels instead of just one, as I do here. It's all there in the repository. I included a very minimal version of the script as well, which is more closely aligned with the version I run on this page.