Evolving Cellular Automata

Source: Dev.to

Introduction

Hello, curious minds! Let’s explore the fascinating intersection of cellular automata and genetic algorithms to uncover emergent patterns and behaviors.

This article is a translation and adaptation of my 2019 piece, originally published in Russian on Habr. Here, we’ll dive into the mechanics of cellular automata, evolve them using genetic algorithms, and showcase some intriguing results.

Repository

Cellular Automata Rules

The simplest form of cellular automata is the one‑dimensional variant. In a one‑dimensional cellular automaton we start with a single array representing the initial state, where each cell holds a binary value (0 or 1). The next state of each cell depends on its current state and those of its two immediate neighbors, determined by a predefined rule.

With three cells (the cell itself and its two neighbors) there are (2^3 = 8) possible configurations:

For each configuration we define the cell’s next state (0 or 1), forming an 8‑bit rule, known as the Wolfram code. This yields (2^8 = 256) possible one‑dimensional cellular automata.

Manually inspecting all 256 rules is feasible, but let’s scale up to two‑dimensional cellular automata, where things get exponentially more complex.

In a two‑dimensional automaton we use a grid (matrix) instead of an array. Each cell has eight neighbors in a Moore neighborhood (horizontal, vertical, and diagonal). For consistency we order the neighbors as follows:

With a cell and its eight neighbors there are (2^9 = 512) possible configurations, so the rules are encoded as a 512‑bit string. This yields (2^{512} \approx 1.34 \times 10^{154}) possible two‑dimensional automata—a number far exceeding the estimated (10^{80}) atoms in the observable universe.

Exploring all these rules manually is impossible. If you checked one rule per second since the Big Bang, you’d have covered only about (4.35 \times 10^{17}) rules. Enter genetic algorithms, which allow us to search for automata that meet specific criteria efficiently.

Two‑Dimensional Cellular Automata

Generating a Random Rule

// 512‑bit rule
const rulesize = 512;
const rule = new Array(rulesize).fill(0).map(() => Math.round(Math.random()));

Initializing the Grid

// 89×89 grid (odd dimensions help keep dynamics interesting)
const sizex = 89;
const sizey = 89;
const size = 2;          // pixel size for drawing
let a = [];

for (let x = 0; x < sizex; x++) {
    a[x] = [];
    for (let y = 0; y < sizey; y++) {
        a[x][y] = Math.round(Math.random());
        if (a[x][y]) context.fillRect(x * size, y * size, size, size);
    }
}

Computing the Next State (periodic boundary conditions)

function step() {
    const temp = new Array(sizex);
    for (let x = 0; x < sizex; x++) {
        temp[x] = new Array(sizey);
        const xm = (x - 1 + sizex) % sizex; // left neighbor (wrap)
        const xp = (x + 1) % sizex;          // right neighbor (wrap)

        for (let y = 0; y < sizey; y++) {
            const ym = (y - 1 + sizey) % sizey; // top neighbor (wrap)
            const yp = (y + 1) % sizey;          // bottom neighbor (wrap)

            // Build 9‑bit mask from the Moore neighborhood
            const q = (
                (a[xm][ym] << 8) |
                (a[x][ym]  << 7) |
                (a[xp][ym] << 6) |
                (a[xm][y]  << 5) |
                (a[x][y]   << 4) |
                (a[xp][y]  << 3) |
                (a[xm][yp] << 2) |
                (a[x][yp]  << 1) |
                a[xp][yp]
            );

            temp[x][y] = rule[q];
            if (temp[x][y]) context.fillRect(x * size, y * size, size, size);
        }
    }
    a = temp;
}

Running this automaton with a random rule often produces chaotic, white‑noise‑like behavior, akin to static on an untuned TV:

Genetic Algorithm

Think of the genetic algorithm as tuning a TV to find a clear signal. Instead of manually adjusting knobs, we define desired properties, and the algorithm searches for rules that exhibit those properties. (The implementation details continue in the original source.)