演化的元胞自动机

Source: Dev.to

引言

你好，充满好奇的读者！让我们一起探索细胞自动机与遗传算法交叉的奇妙世界，揭示其中涌现的模式与行为。

本文是我 2019 年那篇文章的翻译与改编，原文最初以俄文发表在 Habr。本文将深入细胞自动机的机制，使用遗传算法对其进行进化，并展示一些有趣的结果。

代码仓库

细胞自动机规则

最简单的细胞自动机形式是一维变体。在一维细胞自动机中，我们从一个表示初始状态的数组开始，每个细胞保存一个二进制值（0 或 1）。每个细胞的下一状态取决于它自身以及两个相邻细胞的当前状态，由预定义的规则决定。

对于三个细胞（自身加两个邻居）共有 (2^3 = 8) 种可能的配置：

对每种配置我们定义细胞的下一状态（0 或 1），形成一个 8 位规则，也称为 Wolfram 代码。这产生了 (2^8 = 256) 种可能的一维细胞自动机。

手动检查所有 256 条规则是可行的，但让我们把视野扩大到二维细胞自动机，复杂度会呈指数级增长。

在二维自动机中我们使用网格（矩阵）而不是数组。每个细胞在 Moore 邻域中有八个邻居（水平、垂直和对角）。为保持一致，我们按如下顺序排列邻居：

对于一个细胞及其八个邻居，共有 (2^9 = 512) 种可能的配置，因此规则被编码为 512 位字符串。这产生了约 (2^{512} \approx 1.34 \times 10^{154}) 种可能的二维自动机——一个远远超过可观测宇宙中约 (10^{80}) 个原子的数字。

手动探索所有这些规则几乎是不可能的。如果你从宇宙大爆炸以来每秒检查一条规则，只能覆盖约 (4.35 \times 10^{17}) 条。于是遗传算法登场，它让我们能够高效搜索满足特定标准的自动机。

二维细胞自动机

生成随机规则

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

初始化网格

// 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);
    }
}

计算下一状态（周期性边界条件）

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;
}

使用随机规则运行该自动机时，往往会产生类似白噪声的混沌行为，宛如未调频的电视画面：

遗传算法

把遗传算法想象成调电视以寻找清晰信号的过程。我们不需要手动调节旋钮，而是定义期望的属性，算法会搜索满足这些属性的规则。（实现细节请参见原文。）